CSC300: Recursion

Contents [0/13]

Video [1/13]
Linearity [2/13]
Backtracking [3/13]
Stacks and Recursion [4/13]
Example program [5/13]
While loop version [6/13]
Recursive version (forward) [7/13]
Recursive version (backward) [8/13]
Backwards and forwards [9/13]
Pure recursive functions [10/13]
Reading pure recursive functions [11/13]
Rules for looping [12/13]
Rules for recursion [13/13]

(Click here for one slide per page)


Video [1/13]

In three parts

Open Playlist

00:00 Linearity, Backtracking and Recursion
05:10 An example loop
09:29 Converting the loop to a recursive function

Open Playlist

00:00 Backward recursion versus forward recursion
05:53 Recursion going forwards and backwards

Open Playlist

Linearity [2/13]

Linear versus Non-Linear

recursion-race-track recursion-y-maze

Examples

Backtracking [3/13]

Exploring Non-Linear structures may require backtracking

recursion-race-track recursion-y-maze

Data structures 2 emphasizes backtracking

Data structures 1 avoids it

Stacks and Recursion [4/13]

Stacks are useful for backtracking

Functions use a Call Stack

Recursive functions are more general than loops

Thus, we can translate any loop into a recursive function

Example program [5/13]

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
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 [6/13]

11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
  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.

numFivesAIO-

Recursive version (forward) [7/13]

11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
  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 forwards. 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 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.

numFivesAROF-

Recursive version (backward) [8/13]

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
  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 recursive call here is often referred to as the leap of faith.

numFivesAROB-

Backwards and forwards [9/13]

11
12
13
14
15
16
17
18
19
20
21
22
 
  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;
  }

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

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
sumUntilARO-

Here is the complete starter code for this example:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
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 [10/13]

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

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

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

01
02
03
04
05
 
  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): 

  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))

Reading pure recursive functions [11/13]

01
02
03
04
05
06
 
  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): 

  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)

Rules for looping [12/13]

There is an index (more generally, some metric) 

    i

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 [13/13]

There is an index (more generally, some metric) 

    i

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

Revised: 2008/03/17 13:01