Recursion

• Exploit self-similarity in problems
• Learn recursive problem solving

• recursion: The function definition involving a call to the same function
  • Solving a problem using recurstion depends on solving smaller (simpler) occurrences of the same problem until the problem is simple enough that you can solve it directly.
  • Key question: "How is this problem self-similar?" --- what are the smaller subproblems that make up the bigger problem?
• Occurs in many places in code and in real world
  • Looking up a word in dictionary may involve looking up other words (that occur in the meaning of the first word)
  • Nested structures, e.g., trees, file folders, collections, can be self similar
  • Patterns can contain smaller versions of the same pattern (fractals)

recursive programming: Writing functions that call themselves to solve problems that are recursive in nature.

• An equally powerful substitute for iteration (loops).
• Particularly well-suited to solving certain types of problems
• Leads to elegant , simplistic, short code (when used well)
• Many programming languages ( "functional" languages such as Scheme, ML, and Haskell) use recursion exclusively (no loops)

Recursive blue shirt

• We want to count the number of people in the room who are wearing a blue shirt
• We can't directly count (there are a lot of people in the room)
• But all of you can help
• You can ask questions of the person behind you and respond to the questions of the person in front of you

The first person looks behind them:

• If there is no one there, the person responds with 1 if he/she is wearing a blue shirt or 0 if he/she is not.
• If there is someone behind the person, ask them how many people behind them (including the answerer) are wearing a blue shirt (recursive call)
• Once the person receives a response, they add 1 if he/she is wearing a blue shirt, or 0 if he/she is not, and respond to the person in front of them.
• Now I (the instructor) needs to ask everyone in the front row --- much simpler!

Recursion and cases: Every recursive algorithm involves at least two cases:

• base case: A simple occurrence that can be answered directly.
• recursive case: A more complex occurrence of the problem that cannot be directly answered, but can be instead described in terms of smaller occurrences of the same problem

Key idea: In a recursive piece of code, you handle a small part of the overall task yourself (usually the work involves modifying the results of the smaller problems), then make a recursive call to handle the rest.

Ask yourself, "how is ths task self-similar?"

• "How can I describe this algorithm in terms of a smaller or simpler version of itself?"

Recursion Tips

• Look for self-similarity
• Find the minimum amount of work
• Make the problem simpler by doing the least amount of work possible.
• Trust the recursion
• Find a stopping point (base case)

Three rules of recursion

• Every (valid) input must have a case (either recursive or base)
• There must be a base case that makes not recursive calls, i.e., on some input(s), the code should not make any recursive calls
• The recursive case must make the problem simpler and make forward progress to the base case. e.g., if the person behind you asks the person in front of him/her, that is not going to make progress

Recursive Program structure

recursiveFunc ()
{ 
  if (test for simple case) { // base case 
    Compute the solution without recursion 
  } else { // recursive case
    1. Break the problem into  subproblems of the same form 
    2. Call  recursiveFunc() on each  self-similar  subproblem
    3. Reassamble the results of the subproblems
  } 
} 

Non-recursive factorial

// Returns n!, or 1 * 2 * 3 * 4 * ... * n. 
// Assumes n >= 1. 
int factorial(int n) { 
    int total = 1; 
    for (int i = 1; i <= n; i++) { 
        total *= i; 
    } 
    return total; 
} 

0!= 1! = 1
4! = 4 * 3 * 2 * 1
5! = 5 * (4 * 3 * 2 * 1) = 5 * 4!

Recursive factorial

// Returns n!, or 1 * 2 * 3 * 4 * ... * n. 
// Assumes n >= 0. 
int factorial(int n) { 
    if (n <= 1) {
        // base case 
        return 1; 
    } else { 
        return n * factorial(n - 1);
        // recursive case 
    } 
} 

• The recursive code handles a small part of the overall task (by multiplying by n), then makes a recursive call to handle the rest
  • The recursive version is written without using any loops
    • Recursion replaces the while loop
  • We separate the code into a base case (a simple case that does not make any recursive calls), and a recursive case.

Recursive stack trace: Show the chain of function calls represented through a stack for fact(4)

Consider the following recursive function:

int mystery(int n) { 
    if (n < 10) { 
        return n; 
    } else { 
        int a = n / 10; 
        int b = n % 10; 
        return mystery(a + b); 
    }
} 

isPalindrome exercise: write a recursive function isPalindrome that accepts a string and returns true if it reads the same forwards as backwards.

isPalindrome("madam") returns true
isPalindrome("racecar") returns true
isPalindrome("step on no pets") returns true
isPalindrome("able was I ere I saw elba") returns true
isPalindrome("Q") returns true
isPalindrome("Java") returns false
isPalindrome("rotater") returns false
isPalindrome("byebye") returns false
isPalindrome("notion") returns false

• How is this problem self-similar>?
• What is the minimum amount of work?
• How can we make the problem simpler by doing the minimum amount of work?
• What is our stopping point, base case?

Recursive Big-O

• Below is the "pseudocode" for finding BigO of a function
  • Note that this is not real code; this is to show the recursive nature of BigO
  • Self-similarity: find BigO of smaller code blocks and combine them
  • The BigO pseudocode does not cover function calls and some other cases (to keep the discussion simple) --- though experiment to expand this

findBigO(codeSnippet):
  if codeSnippet is a single statement:
    return O(1)
  if codeSnippet is a loop:
    return number_of_times_loop_runs * findBigO(loop_inside)
  for codeBlock in codeSnippet:
    return the_sum_of findBigO(codeBlock)

Example: compute bigO for the following code using this recursive pseudocode:

for (int i = 0; i < N * N; i += 3) {
  for (int j = 3; j <= 219; j++) {
    cout << "sum: " << i + j << endl;
  }
}
cout << "Enjoy COL100\n";

Exercise: Write a function power that accepts integer parameters for a base and exponent and computes base ^ exponent.

• First write code using for-loop
• Now write a recursive version of this function (one that calls itself)
• Solve the problem without using any loops.

Method:

• How is the problem self-similar? x^n = x * x^(n-1)
• What is the minimum amount of work? multiplication
• How can we make the problem simpler by doing the least amount of work?
• What is our stopping point (base case)? n = 0. Why not n=1?

//Assumes exp >= 0
int power(int base, int exp)
{
  if (exp == 0) {
    return 1;
  } else {
    return base * power(base, exp - 1);
  }
}

Can we do better? Notice that x^18 = (x*x)^9; x^9=x*x^8

//Assumes exp >= 0
int power(int base, int exp)
{
  if (exp == 0) {
    return 1;
  } else if (exp % 2 == 0) {
    return power(base * base, exp/2); //recursive case 1
  } else {
    return base * power(base, exp - 1); //recursive case 2
  }
}

Exercise: write a recursive function convertFromBinary that accepts an a string of that number's representation in binary (base 2) and returns the base 10 int equivalent. e.g.,

convertFromBinary("111") returns 7
convertFromBinary("1100") returns 12
convertFromBinary("101010") returns 42

// Returns the given int's binary representation. 
// Precondition: n >= 0 
int convertFromBinary(string binary) {     
    int length = binary.length();     
    if (length == 1) {         
        // base case: binary is same as base 10         
        return stringToInteger(binary); 
    } 
    // recursive case: break number apart 
    string lastCharacter = binary.substr(length - 1); 
    string beginning = binary.substr(0, length - 1); 
    return 2 * convertFromBinary(beginning) + 
               convertFromBinary(lastCharacter); 
} 

Exercise: write a recursive function reverseLines that accepts a file input stream and prints the lines of that file in reverse order.
Example input:

Hello world
Hello foo
Hello bar
baz hello

baz hello
Hello bar
Hello foo
Hello world

void reverseLines(ifstream& input) { 
    string line; 
    if (getline(input, line)) { 
        // recursive case 
        reverseLines(input); 
        cout << line << endl; 
    } 
} 

Exercise: write a function crawl that accepts a file name as a parameter and prints information about that file.

• If the name represents a normal file, just print its name
• If the name represents a directory, print its name and information about every file/directory inside it, indented.

courses
    col100
        lab2
            hello_world.cpp
            order_of_evaluation.cpp
        lab3
            if_then_else.cpp
        minor1.pdf
        minor2.pdf
    eel200
        ...

Assume following functions are available (using SPL's "filelib.h"):

isDirectory("name")	Returns whether the filename represents a directory. Can use stat() method in standard C library but with more complicated syntax and semantics.
listDirectory("name")	returns a Vector<string> with the names of all files contained in the given directory. Can use a combination of opendir/readdir/closedir operations available in standard C library but with more complicated syntax and semantics.

How is this problem self-similar? Crawling a directory can be expressed in terms of crawling the subdirectories, albeit with a different indentation.
Base-case? File

// Prints information about this file, 
// and (if it is a directory) any files inside it. 
void crawl(string filename, string indent) { 
    cout << indent << getTail(filename) << endl; 
    if (isDirectory(filename)) { 
        // recursive case; print contained files/dirs 
        Vector<string> filelist; 
        listDirectory(filename, filelist); 
        for (string subfile : filelist) { 
            crawl(filename + "/" + subfile, 
                  indent + "    "); 
        } 
    } 
} 

Exercise: Write a recursive function fib that accepts an integer N and returns the Nth fibonacci number.

• The first two Fibonacci numbers are defined to be 1.
• Every other Fibonacci number is the sum of the two before it.

fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
...

// Returns the nth Fibonacci number. 
int fib(int n) { 
    if (n <= 2) { 
        return 1; 
    } else { 
        return fib(n - 1) + fib(n - 2); 
    } 
} 

Memoization

• Often implemented by storing call results in a collection.

Pseudo-code template:

cache = {}.       // empty 
function f(args): 
    if I have computed f(args) before: 
        Look up f(args) result in cache. 
    else: 
        Actually compute f(args) result. 
        Store result in cache. 
    Return result.

int fib(int n, Map<int, int> &cache) {
    if (n <= 2) { 
        return 1; 
    } else if (cache.containsKey(n)) { 
        return cache[n]; 
    } else { 
        int result = fib(n - 1) + fib(n - 2); 
        cache[n] = result; 
        return result; 
    } 
} 

But how to initialize the cache? Should we tell the user that he needs to initialize and pass the cache --- seems ugly!

Wrapper functions

• Some recursive functions need extra arguments to implement the recursion
• A wrapper function is a function that does some initial prep work, then fires off a recursive call with the right arguments.
• The recursion is done in the helper function.

int fibHelper(int n, Map<int, int> &cache) {
    if (n <= 2) { 
        return 1; 
    } else if (cache.containsKey(n)) { 
        return cache[n]; 
    } else { 
        int result = fibHelper(n - 1, cache) + fibHelper(n - 2, cache); 
        cache[n] = result; 
        return result; 
    } 
} 

int fib(int n)
{
  Map<int, int> cache;
  return fibHelper(n, cache);
}

Tail recursion

• Tail recursion can often be optimized by the compiler. e.g., use g++ -O3 foo.cpp. -O2 represents that the compiler should optimize the code with optimization-level 3.

Examples: Is this tail recursive?

int mystery(int n)
{
  if (n < 10) {
    return n;
  } else {
    int a = n/10;
    int b = n %10;
    return mystery(a + b);
  }
}

int fact(int n)
{
  if (n <= 1) {
    return 1;
  } else {
    return n * fact(n - 1);
  }
}

Can we rewrite factorial so that it becomes tail-recursive? Tail-recursive factorial:

int factorial_helper(int n, int accum)
{
  if (n <= 1) {
    return accum;
  } else {
    return factorial(n - 1, accum * n);
  }
}

int factorial(int n)
{
  return factorial_helper(n, 1);
}

Compare with non-recursive factorial (sometimes looking at the non-recursive version of a function can help you find the tail recursive solution):

int factorial(int n)
{
  int accum = 1;
  for (int i = 1; i <= n; i++) {
    accum = accum * i;
  }
  return accum;
}

Another tail-recursion example: fib(n)

int fib_helper(int n, int i, int fib_i, int fib_prev)
{
  if (i == n) {
    return fib_i;
  } else {
    return fib_helper(n, i + 1, fib_i + fib_prev, fib_i);
  }
}

int fib(int n)
{
  return fib_helper(n, 1, 1, 0);
}

int fib(int n)
{
  intt i = 1;
  int fib_i = 1;
  int fib_prev = 0;
  while (i != n) {
    int new_i = i + 1;
    int new_fib_i = fib_i + fib_prev;
    int new_fib_prev = fib_i;
    fib_i = new_fib_i;
    fib_prev = new_fib_prev;
    i = new_i;
  }
  return fib_i;
}

Another tail-recursive implementation of fib(n) with fewer arguments to helper function:

int fib_helper(int n, int fib_n, int fib_prev)
{
  if (n == 1) {
    return fib_n;
  } else {
    return fib_helper(n - 1, fib_n + fib_prev, fib_n);
  }
}

int fib(int n)
{
  return fib_helper(n, 1, 0);
}

int fib(int n)
{
  int fib_i = 1;
  int fib_prev = 0;
  while (n != 1) {
    int new_n = n - 1;
    int new_fib_i = fib_i + fib_prev;
    int new_fib_prev = fib_i;
    fib_i = new_fib_i;
    fib_prev = new_fib_prev;
    n = new_n;
  }
  return fib_i;
}

Notice the similarity of tail-recursive implementation to the non-recursive implementation (that uses loops). In general, any loop can be converted to a tail-recursive implementation. In fact, some programming languages do not support loops and only support recursion --- typically programmers write tail-recursive implementations of their programs in such languages.