Video: Recursion (Bulgarian)

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

• Write a program to find all possible placements of 8 queens on a chessboard
  • So that no two queens attack each other
  • http://en.wikipedia.org/wiki/Eight_queens_puzzle

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