Topics covered:

  • What is Recursion?
  • Calculating Factorial Recursively
  • Generating All 0/1 Vectors Recursively
  • Finding All Paths in a Labyrinth Recursively
  • Recursion or Iteration?
    • Harmful Recursion
    • Optimizing Bad Recursion

Video (in Bulgarian)

Presentation Content

What is Recursion?

  • Recursion is when a methods calls itself
    • Very powerful technique for implementing combinatorial and other algorithms
  • Recursion should have
    • Direct or indirect recursive call
      • The method calls itself directly
      • Оr through other methods
    • Exit criteria (bottom)
      • Prevents infinite recursion

Recursive Factorial – Example

  • Recursive definition of n! (n factorial):
n! = n x (n–1)! for n >= 0
0! = 1
  • 5! = 5 x 4! = 5 x 4 x 3 x 2 x 1 x 1 = 120
  • 4! = 4 x 3! = 4 x 3 x 2 x 1 x 1 = 24
  • 3! = 3 x 2! = 3 x 2 x 1 x 1 = 6
  • 2! = 2 x 1! = 2 x 1 x 1 = 2
  • 1! = 1 x 0! = 1 x 1 = 1
  • 0! = 1

Recursive Factorial – Example

  • Calculating factorial:
    • 0! = 1
    • n! = nx (n-1)!, n>0
static decimal Factorial(decimal num)
{
    if (num == 0) 
        return 1;
    else
        return num * Factorial(num - 1);
} 
  • Don’t try this at home!
    • Use iteration instead

Generating 0/1 Vectors

  • How to generate all 8-bit vectors recursively?
    • 00000000
    • 00000001
    • 01111111
    • 10000000
    • 11111110
    • 11111111
  • How to generate all n-bit vectors?

Generating 0/1 Vectors (2)

  • Algorithm Gen01(n): put 0 and 1 at the last position n and call Gen01(n-1) for the rest:

Generating 0/1 Vectors (3)

static void Gen01(int index, int[] vector)
{
   if (index == -1)
      Print(vector);
   else
      for (int i=0; i<=1; i++)
      {
         vector[index] = i;
         Gen01(index-1, vector);
      }
}
static void Main()
{
   int size = 8;
   int[] vector = new int[size];
   Gen01(size-1, vector);
}

Generating Combinations

  • Combinations are give the ways to select a subset of larger set of elements
    • Select k members from a set of n elements
    • Example: there are 10 ways to select 3 different elements from the set {4,5,6,7,8}:
      • (4, 5, 6) (4, 5, 7) (4, 5, 8) (4, 6, 7) (4, 6, 8)<br/>(4, 7, 8) (5, 6, 7) (5, 6, 8) (5, 7, 8) (6, 7, 8)
  • Combinations with and without repetitions can be easily generated with recursion
  • Algorithm GenCombs(k): put the numbers [1…n] at position k the and call GenCombs(k+1) recursively for the rest of the elements:

Backtracking

  • What is backtracking?
    • Backtracking is a class of algorithms for finding all solutions to some computational problem
    • E.g. find all paths from Sofia to Varna
  • How does backtracking work?
    • Usually implemented recursively
    • At each step we try all perspective possibilities to generate a solution
  • Backtracking has exponential running time!

The 8 Queens Problem

Solving The 8 Queens Problem

  • Backtracking algorithm for finding all solutions to the “8 Queens Puzzle”
static void PutQueens(int count)
{
  if (count > 8)
    PrintSolution();
  else
    for (row = 0; row < 8; row++)
      for (col = 0; col < 8; col++)
        if (CanPlaceQueen(row, col))
        {
          MarkAllAttackedPositions(row, cow);
          PutQueens(count + 1);
          UnmarkAllAttackedPositions(row, cow);
        }
}

Finding All Paths in a Labyrinth

  • We are given a labyrinth
    • Represented as matrix of cells of size M x N
    • Empty cells are passable, the others (*) are not
  • We start from the top left corner and can move in the all 4 directions: left, right, up, down
  • We need to find all paths to the bottom right corner
  • There are 3 different paths from the top left corner to the bottom right corner:
  • Suppose we have an algorithm FindExit(x,y) that finds and prints all paths to the exit (bottom right corner) starting from position (x,y)
  • If (x,y) is not passable, no paths are found
  • If (x,y) is already visited, no paths are found
  • Otherwise:
    • Mark position (x,y) as visited (to avoid cycles)
    • Find recursively all paths to the exit from all neighbor cells: (x-1,y) ,(x+1,y) ,(x,y+1) ,(x,y-1)
    • Mark position (x,y) as free (can be visited again)

Find All Paths: Algorithm

  • Representing the labyrinth as matrix of characters (in this example 5 rows and 7 columns):
static char[,] lab = 
{
    {' ', ' ', ' ', 'x', ' ', ' ', ' '},
    {'x', 'x', ' ', 'x', ' ', 'x', ' '},
    {' ', ' ', ' ', ' ', ' ', ' ', ' '},
    {' ', 'x', 'x', 'x', 'x', 'x', ' '},
    {' ', ' ', ' ', ' ', ' ', ' ', 'е'},
};
    • Spaces (’') are passable cells
    • Asterisks (’x') are not passable cells
    • The symbol ’e’ is the exit (can occur multiple times)
static void FindExit(int row, int col)
{
    if ((col < 0) || (row < 0) || (col >= lab.GetLength(1))
        || (row >= lab.GetLength(0)))
    {
        // We are out of the labyrinth -> can't find a path
        return;
    }
    // Check if we have found the exit
    if (lab[row, col] == 'е') 
    {
        Console.WriteLine("Found the exit!");
    }
    if (lab[row, col] != ' ')
    {
        // The current cell is not free -> can't find a path
        return;
    }
// (example continues)
    // Temporary mark the current cell as visited
    lab[row, col] = 's';

    // Invoke recursion to explore all possible directions
    FindExit(row, col-1); // left
    FindExit(row-1, col); // up
    FindExit(row, col+1); // right
    FindExit(row+1, col); // down

    // Mark back the current cell as free
    lab[row, col] = ' ';
}

static void Main()
{
    FindExit(0, 0);
}

Find All Paths and Print Them

  • How to print all paths found by our recursive algorithm?
    • Each move’s direction can be stored in a list
    • Need to pass the movement direction at each recursive call (L, R, U, or D)
    • At the start of each recursive call the current direction is appended to the list
    • At the end of each recursive call the last direction is removed from the list
static List<char> path = new List<char>();
static void FindPathToExit(int row, int col, char direction)
{
    ...
    // Append the current direction to the path
    path.Add(direction);
    if (lab[row, col] == 'е')
    {
        // The exit is found -> print the current path
    }
    ...
    // Recursively explore all possible directions
    FindPathToExit(row, col - 1, 'L'); // left
    FindPathToExit(row - 1, col, 'U'); // up
    FindPathToExit(row, col + 1, 'R'); // right
    FindPathToExit(row + 1, col, 'D'); // down
    ...
    // Remove the last direction from the path
    path.RemoveAt(path.Count - 1);
}

Recursion Can be Harmful!

  • When used incorrectly the recursion could take too much memory and computing power
    • Example:
static decimal Fibonacci(int n)
{
    if ((n == 1) || (n == 2))
        return 1;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

static void Main()
{
    Console.WriteLine(Fibonacci(10)); // 89
    Console.WriteLine(Fibonacci(50)); // This will hang!
}

How the Recursive Fibonacci Calculation Works?

  • fib(n) makes about fib(n) recursive calls
  • The same value is calculated many, many times!

Fast Recursive Fibonacci

  • Each Fibonacci sequence member can be remembered once it is calculated
    • Can be returned directly when needed again
static decimal[] fib = new decimal[MAX_FIB];
static decimal Fibonacci(int n)
{
    if (fib[n] == 0)
    {
        // The value of fib[n] is still not calculated
        if ((n == 1) || (n == 2))
            fib[n] = 1;
        else
            fib[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
    }
    return fib[n];
}

When to Use Recursion?

  • Avoid recursion when an obvious iterative algorithm exists
    • Examples: factorial, Fibonacci numbers
  • Use recursion for combinatorial algorithm where at each step you need to recursively explore more than one possible continuation
    • Examples: permutations, all paths in labyrinth
    • If you have only one recursive call in the body of a recursive method, it can directly become iterative (like calculating factorial)

Summary

  • Recursion means to call a method from itself
    • It should always have a bottom at which recursive calls stop
  • Very powerful technique for implementing combinatorial algorithms
    • Examples: generating combinatorial configurations like permutations, combinations, variations, etc.
  • Recursion can be harmful when not used correctly