# 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]

 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

• Linear: one thing after another, til the end
• Non-Linear: maybe more than one thing

Examples

• Racetrack versus Maze
• List of children versus Tree of descendents
• List of lectures versus DAG of prerequesites

 Backtracking [3/13]

Exploring Non-Linear structures may require backtracking

• Linear: need to know is where we are
• Non-Linear: need to know is where we are and where we have been

Data structures 2 emphasizes backtracking

Data structures 1 avoids it

 Stacks and Recursion [4/13]

Stacks are useful for backtracking

• Make choices going forward
• Revisit choices goin 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

Thus, we can translate any loop into a recursive function

• This is a warmup for Data Structures 2

 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.

 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.

 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.

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

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

 ``` 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)
```
• `g(5)` calls `g(4)` and `g(3)`.
• `g(4)` calls `g(3)` and `g(2)`.
• etc.

 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