CSC300 / CSC402: Recursion

Linear: need to know where we are
Non-Linear: need to know where we are and where we have been (Theseus and the Minotaur, Help from Ariadne)
- Keep track of each choice we make
- Go back to the decision point and explore the consequences of making a different choice
- Eliminate the possible choices at each intersection one at a time until you solve the problem

recursion-race-track recursion-y-maze

Data Structures 2 emphasizes backtracking:

The major data structures we look at in Data Structures 1 don't typically use backtracking.

Stacks and Recursion [3/14]

Stacks are useful for backtracking
...in particular when working with trees and graphs!

Make choices going forward
Revisit choices going backward in reverse order

Functions use a Call Stack

Thus, recursive functions are useful for backtracking

Recursive functions are more general than loops

Loops always go forward
Recursive functions go forward, then back

We can translate any loop into a recursive function

This is a warmup for Data Structures 2

Example program [4/14]

package algs11;
import java.util.Arrays;
import stdlib.*;
public class Playground {
  /* Return number of times 5.0 occurs in the list */
  public static int numFives (double[] list) {
    return StdRandom.uniform (100); //TODO: fix this
  }
  /* This is a test function */
  public static void testNumFives (int expected, double[] list) {
    int actual = numFives (list);
    if (expected != actual) {
      StdOut.format ("Failed: Expecting [%d] Actual [%d] with argument %s\n", expected, actual, Arrays.toString (list));
    }
  }
  /* A main function for testing */
  public static void main (String[] args) {
    testNumFives (0, new double[] { });
    testNumFives (1, new double[] { 5 });
    testNumFives (0, new double[] { 11 });
    testNumFives (3, new double[] { 5, 5, 5 });
    testNumFives (0, new double[] { 11, 21, 31, 41 });
    testNumFives (1, new double[] { 5, 11, 21, 31, 41 });
    testNumFives (1, new double[] { 11, 21, 31, 41, 5 });
    testNumFives (1, new double[] { 11, 21, 5, 31, 41 });
    testNumFives (3, new double[] { 11, 21, 5, 31, 5, 41, 5});
    StdOut.println ("Finished tests");
  }
  /* A main function for debugging -- change the name to "main" to run it */
  public static void main2 (String[] args) {
    //Trace.drawSteps ();
    Trace.drawStepsOfMethod ("numFives");
    Trace.drawStepsOfMethod ("numFivesHelper");
    Trace.run ();
    double[] list = new double[] { 5, 11, 5, 5 };
    double result = numFives (list);
    StdOut.println ("result: " + result);
  }
}

While loop version [5/14]

Code:

  public static int numFives (double[] list) {
    int i = 0;
    int result = 0;



    while (i < list.length) {
      if (list[i] == 5) {
        result++;
      }
      i = i + 1;
    }
    return result;
  }

For [5,11,5,5], the loop values (line 17) are

// list==[5,11,5,5], i==0, result==0
// list==[5,11,5,5], i==1, result==1
// list==[5,11,5,5], i==2, result==1
// list==[5,11,5,5], i==3, result==2
// list==[5,11,5,5], i==4, result==3

More abstractly:

// list[i..]==[5,11,5,5], result==0
//   list[i..]==[11,5,5], result==1
//      list[i..]==[5,5], result==1
//        list[i..]==[5], result==2
//         list[i..]==[], result==3

This is a while loop.

Execution enters the loop without first checking to see if it is necessary.

Converting a while loop to a recursive function [6/14]

Create a helper function.

Determine the helper function's parameters.
Add one parameter to the helper function's signature for each local variable we need for our loop.

Write the body of the helper function:
- Change while loop to an if block.
- Instead of incrementing the index variable, do a recursive call to the helper function, passing the incremented value of the index variable.

Call the helper function passing the initial values of the variables.

Recursive version (forward) [7/14]

Replacing a while loop with a recursive function call:

  public static int numFives (double[] list) {
    int result = numFivesHelper (list, 0, 0);
    return result;
  }

  public static int numFivesHelper (double[] list, int i, int result) {
    if (i < list.length) {
      if (list[i] == 5) {
        result++;
      }
      result = numFivesHelper (list, i + 1, result); 
    }
    return result;
  }

For [5,11,5,5], the computation is:

// list[i..]==[5,11,5,5], result==0
//   list[i..]==[11,5,5], result==1
//      list[i..]==[5,5], result==1
//        list[i..]==[5], result==2
//         list[i..]==[], result==3

The call/return pattern is:

// call@3 ([5,11,5,5], 0)
//   call@4 ([11,5,5], 1)
//     call@5  ([5,5], 1)
//       call@6  ([5], 2)
//         call@7 ([], 3)
//         retn@7 ([], 3) : 3
//       retn@6  ([5], 2) : 3
//     retn@5  ([5,5], 1) : 3
//   retn@4 ([11,5,5], 1) : 3
// retn@3 ([5,11,5,5], 0) : 3

(Abbreviating list and i as single parameter showing list[i..].)

Converted to a recursive function.

Note that we do not mutate i in the helper!

Note that computation goes forward. We forget the old values of i as we go forward.

This kind of recursion is called tail recursion: the recursive call is the last thing the function does before it returns. There's no work to do after the recursive call returns.

There is a one-to-one correspondence between loops and tail-recursive functions. We can mechanically convert between these to forms. Compilers do it all the time.

In the language I work in, Scala, the compiler can be instructed to expect to be able to do tail-call elimination.

General Recursion [8/14]

Recursive functions are more general than looping!

Instead of going forward, we can also go backward.

We can look at the list from the back to the front: start at the end of the list.

What's the difference?

With forward recursion:

We do the work for the current element first.

Then we do the recursive call last to process the rest of the elements in the data structure.

With backward recursion:

We do the recursive call to process the rest of the elements in the data structure first.
Then we combine the result of the recursive call with the work for the current element last.

I don't need a result parameter in my helper function!

Recursive version (backward) [9/14]

Recursion is more general than looping!

  public static int numFives (double[] list) {

    int result = numFivesHelper (list, 0);
    return result;
  }
  public static int numFivesHelper (double[] list, int i) {
    int result = 0;
    if (i < list.length) {
      result = numFivesHelper (list, i + 1); 
      if (list[i] == 5) {
        result++;
      }
    }
    return result;
  }

For [5,11,5,5], the computation is:

//         list[i..]==[], result==0
//        list[i..]==[5], result==1
//      list[i..]==[5,5], result==2
//   list[i..]==[11,5,5], result==2
// list[i..]==[5,11,5,5], result==3

The call/return pattern is:

// call@3 ([5,11,5,5])
//   call@4 ([11,5,5])
//     call@5  ([5,5])
//       call@6  ([5])
//         call@7 ([])
//         retn@7 ([]) : 0
//       retn@6  ([5]) : 1
//     retn@5  ([5,5]) : 2
//   retn@4 ([11,5,5]) : 2
// retn@3 ([5,11,5,5]) : 3

The immediate recursive call here is often referred to as the leap of faith.

You're assuming you can solve the problem for the rest of the list.

Backwards and forwards [10/14]

It is common for recursive functions to do work both forwards and backwards.

Try going through this example yourself.

  public static double sumUntil (double val, double[] list) {
    double result = sumUntilHelper (val, list, 0);
    return result;
  }
  public static double sumUntilHelper (double val, double[] list, int i) {
    double result = 0;
    if (i < list.length && list[i] != val) {
      result = sumUntilHelper (val, list, i + 1); 
      result = result + list[i];
    }
    return result;
  }

For val==5, list==[11,21,31,5,41], the call tree is

call@3 (5, [11,21,31,5,41])
   call@4 (5, [21,31,5,41])
      call@5 (5, [31,5,41])
         call@6 (5, [5,41])
          ret@6 (5, [5,41]) : 0
       ret@5 (5, [31,5,41]) : 31
    ret@4 (5, [21,31,5,41]) : 52
 ret@3 (5, [11,21,31,5,41]) : 63

Here is the complete starter code for this example:

package algs11;
import java.util.Arrays;
import stdlib.*;
public class Playground {
  /* Return the sum of the values in the list up to, but no including the first 5.0 */
  public static double sumUntil (double val, double[] list) {
    return StdRandom.uniform (); //TODO: fix this
  }
  /* This is a test function */
  public static void testSumUntil (double expected, double val, double[] list) {
    double actual = sumUntil (val, list);
    if (expected != actual) {
      StdOut.format ("Failed: Expecting [%f] Actual [%f] with argument (%f, %s)\n", expected, actual, val, Arrays.toString (list));
    }
  }
  /* A main function for testing */
  public static void main (String[] args) {
    for (double v : new double[] { 5, 7 }) {
      testSumUntil (63, v, new double[] { 11, 21, 31, v, 41 });
      testSumUntil (0, v, new double[] { v, 11, 21, 31, 41 });
      testSumUntil (104, v, new double[] { 11, 21, 31, 41, v });
      testSumUntil (11, v, new double[] { 11, v, 21, v, 31, 41 });
      testSumUntil (0, v, new double[] { v });
      testSumUntil (0, v, new double[] { v, v });
      testSumUntil (104, v, new double[] { 11, 21, 31, 41 });
      testSumUntil (11, v, new double[] { 11 });
      testSumUntil (0, v, new double[] {});
    }
    StdOut.println ("Finished tests");
  }
  /* A main function for debugging -- change the name to "main" to run it */
  public static void main2 (String[] args) {
    //Trace.drawSteps ();
    //Trace.drawStepsOfMethod ("sumUntil");
    //Trace.drawStepsOfMethod ("sumUntilHelper");
    //Trace.run ();
    double[] list = new double[] { 11, 21, 31, 5, 41 };
    double result = sumUntil (5, list);
    StdOut.println ("result: " + result);
  }
}

Pure recursive functions [11/14]

Pure functions are like functions in math: they always do the same thing.

No side effects:A function is pure if it does not change any non-local variables, read files or network connections, or make any output.

To understand the execution of a pure recursive function, it is easiest to start at the base case and work your way up.

What does this function do?

  public static int f (int n) {
    if (n <= 0) return 1;
    int nMinus1 = f (n-1);
    return n * nMinus1;
  }

Bottom up (from the base case):
Building up a table
Memoizing

  f(0) = 1
  f(1) = 1 * f(0) = 1
  f(2) = 2 * f(1) = 2
  f(3) = 3 * f(2) = 6
  f(4) = 4 * f(3) = 24
  f(5) = 5 * f(4) = 120

Top down (from the initial argument):

  f(3) = 3 * f(2) 
       = 3 * (2 * f(1)) 
       = 3 * (2 * (1 * f(0)))
       = 3 * (2 * (1 * 1))

It can be easier to think about this from the bottom up. Imagine trying this for f(5) or f(17).

Which is easier to reason about?

Reading pure recursive functions [12/14]

Another example:

  public static int g (int n) {
    if (n <= 1) return n;
    int nMinus1 = g (n-1);
    int nMinus2 = g (n-2);
    return nMinus1 + nMinus2;
  }

Bottom up (from the base case):
Building up a table
Memoizing

  g(0) = 0
  g(1) = 1
  g(2) = g(0) + g(1) =  0 +  1 =  1
  g(3) = g(1) + g(2) =  1 +  1 =  2
  g(4) = g(2) + g(3) =  1 +  2 =  3
  g(5) = g(3) + g(4) =  2 +  3 =  5
  g(6) = g(4) + g(5) =  3 +  5 =  8
  g(7) = g(5) + g(6) =  5 +  8 = 13
  g(8) = g(6) + g(7) =  8 + 13 = 21
  g(9) = g(7) + g(8) = 13 + 21 = 34

Top down (from the initial argument):

  g(5) = g(3)                   + g(4)
       = (g(2)          + g(1)) + g(4)  
       = ((g(0) + g(1)) + g(1)) + g(4)
       = ((0    + 1   ) + 1   ) + g(4)
       = 2                      + g(4)
       = 2                      + g(3)                   + g(2)
       = 2                      + (g(2)          + g(1)) + g(2)
       = 2                      + ((g(0) + g(1)) + g(1)) + g(2)
       = 2                      + ((0    + 1   ) + 1   ) + g(2)
       = 2                      + 2                      + g(2)         
       = 2                      + 2                      + (g(0) + g(1))
       = 2                      + 2                      + (0    + 1   )
       = 2                      + 2                      + 1
       = 5

You can view this as a call tree:

    g(5)
      + g(4)
      |   + g(3)
      |   |   + g(2)    
      |   |   |   + g(1)
      |   |   |   + g(0)
      |   |   + g(1)    
      |   + g(2)
      |       + g(1)
      |       + g(0)
      + g(3)
          + g(2)    
          |   + g(1)
          |   + g(0)
          + g(1)

g(5) calls g(4) and g(3).
g(4) calls g(3) and g(2).
etc.

Rules for looping [13/14]

There is an index (more generally, some metric)

Start somewhere valid

    i = 0

Base case says when to stop

    i >= a.length

Inductive case takes us closer to base case

    i = i + 1

Rules for recursion [14/14]

There is an index (more generally, some metric)

Start somewhere valid

    i = 0

Base case says when to stop

    i >= a.length

Inductive case takes us closer to base case

    i = i + 1

Inductive cases should not overlap!

Exponential explosion of work!