On Recursion

Agenda

  1. Recursion
    • stopping recursion: simplification & base cases
  2. Recursive "shapes":
    • Linear (single) recursion:
      • Factorial
      • Addition
      • Binary search
    • Tree (multiple) recursion: divide and conquer
      • Fibonacci numbers
      • Tower of Hanoi
      • Merge sort
      • Making change
  3. The Call Stack and Stack Frames
    • simulating recursion
    • debugging with pdb and %debug

1. Recursion

Recursive functions, directly or indirectly, call themselves.

Recursive solutions are applicable when a problem can be broken down into more easily solved sub-problems that resemble the original, and whose solutions can then be combined.

E.g., computing the combined price of a bunch of nested shopping bags of items:

Stopping recursion: simplification & base case(s)

2. Recursive "shapes"

Linear recursion

Example: Factorial

$n! = \begin{cases} 1 & \text{if}\ n=0 \\ n \cdot (n-1)! & \text{if}\ n>0 \end{cases}$

i.e., $n! = n \cdot (n-1) \cdot (n-2) \cdots 3 \cdot 2 \cdot 1$

Example: Addition of two positive numbers $m$, $n$

$m + n = \begin{cases} m & \text{if}\ n=0 \\ (m + 1) + (n - 1) & \text{if}\ n > 0 \end{cases}$

Tree recursion

Example: Fibonacci numbers

$fib(n) = \begin{cases} 0 & \text{if}\ n=0 \\ 1 & \text{if}\ n=1 \\ fib(n-1) + fib(n-2) & \text{otherwise} \end{cases}$

i.e., 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Example: Tower of Hanoi

Setup: three rods, with one or more discs of different sizes all stacked on one rod, smallest (top) to largest (bottom). E.g.,

     ||          ||          ||     
     ==          ||          ||     
    ====         ||          ||     
   ======        ||          ||     
------------------------------------

Goal: move all the discs, one by one, to another rod, with the rules being that (1) only smaller discs can be stacked on larger ones and (2) only the top disc in a stack can be moved to another rod.

For three discs, as shown above, we would carry out the following sequence to move the stack to the rightmost rod. The rods are abbreviated L (left), M (middle), R (right):

  1. Move the small disc (0) from L to R
  2. Move the medium disc (1) from L to M
  3. Move 0 from R to M (R is empty)
  4. Move the large disc (2) from L to R
  5. Move 0 from M to L
  6. Move 1 from M to R
  7. Move 0 from L to R (done)

Can you come up with the sequence needed to move a stack of 4 discs from one rod to another? 5 discs? An arbitrary number of discs?

Example: Mergesort

Example: Making Change

Question: how many different ways are there of making up a specified amount of money, given a list of available denominations?

E.g., how many ways of making 10 cents, given 1c, 5c, 10c, 25c coins?

3. The Call Stack (if time allows)

Simulating recursive factorial

Debugging with pdb