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

# by default, only the result of the last expression in a cell is displayed after evaluation.
# the following forces display of *all* self-standing expressions in a cell.

from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"

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:

class Bag:
    def __init__(self, price, *contents):  #*contents is a unknown number of arguments to init 
         # that you can iterate over
            # a bag contains an item and possibly a sequence of more bags
        self.price = price
        self.contents = contents

bag1 = Bag(10)

bag2 = Bag(5, Bag(3))

bag3 = Bag(5, Bag(4, Bag(3)), Bag(2))

bag4 = Bag(0, Bag(5), Bag(10), Bag(3, Bag(2), Bag(100)), Bag(9, Bag(2, Bag(25))))

def price(bag):
    # send price a bag, return total value in it
    # base case for a bag is if *contents is empty, then the value of the bag is just self.price 
    valueSoFar=bag.price
    #iterate over the other bags within this bag, adding up their values into valueSoFar
    #if bag.contents is empty, base case
    for b in bag.contents:    # b handles all the arguments in the current bag
        valueSoFar+=price(b)
    return valueSoFar
    

price(bag1)
price(bag2)
price(bag3)
price(bag4)

10

8

14

156

Stopping recursion: simplification & base case(s)

import sys
sys.setrecursionlimit(200)

def silly_rec(n):
    print(n)
    silly_rec(n-1)

silly_rec(1)

1
0
-1
-2
-3
-4
-5
-6
-7
-8
-9
-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
-42
-43
-44
-45
-46
-47
-48
-49
-50
-51
-52
-53
-54
-55
-56
-57
-58
-59
-60
-61
-62
-63
-64
-65
-66
-67
-68
-69
-70
-71
-72
-73
-74
-75
-76
-77
-78
-79
-80
-81
-82
-83
-84
-85
-86
-87
-88
-89
-90
-91
-92
-93
-94
-95
-96
-97
-98
-99
-100
-101
-102
-103
-104
-105
-106
-107
-108
-109
-110
-111
-112
-113
-114
-115
-116
-117
-118
-119
-120
-121
-122
-123
-124
-125
-126
-127
-128
-129
-130
-131
-132
-133
-134
-135
-136
-137
-138
-139
-140
-141
-142
-143
-144
-145
-146
-147
-148
-149
-150
-151
-152
-153
-154
-155

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-13-af015c898eaa> in <module>
----> 1 silly_rec(1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)

<ipython-input-12-d3f98e10e6a7> in silly_rec(n)
      1 def silly_rec(n):
----> 2     print(n)
      3     silly_rec(n-1)

~\anaconda3\lib\site-packages\ipykernel\iostream.py in write(self, string)
    402             is_child = (not self._is_master_process())
    403             # only touch the buffer in the IO thread to avoid races
--> 404             self.pub_thread.schedule(lambda : self._buffer.write(string))
    405             if is_child:
    406                 # mp.Pool cannot be trusted to flush promptly (or ever),

~\anaconda3\lib\site-packages\ipykernel\iostream.py in schedule(self, f)
    200         If the thread is not running, call immediately.
    201         """
--> 202         if self.thread.is_alive():
    203             self._events.append(f)
    204             # wake event thread (message content is ignored)

~\anaconda3\lib\threading.py in is_alive(self)
   1080         if self._is_stopped or not self._started.is_set():
   1081             return False
-> 1082         self._wait_for_tstate_lock(False)
   1083         return not self._is_stopped
   1084 

~\anaconda3\lib\threading.py in _wait_for_tstate_lock(self, block, timeout)
   1025         if lock is None:  # already determined that the C code is done
   1026             assert self._is_stopped
-> 1027         elif lock.acquire(block, timeout):
   1028             lock.release()
   1029             self._stop()

RecursionError: maximum recursion depth exceeded while calling a Python object

def silly_rec(n):
    print(n)
    if n>-10:
        silly_rec(n-1)
silly_rec(1)

1
0
-1
-2
-3
-4
-5
-6
-7
-8
-9
-10

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$

def rec_factorial(n):
    print('n = ', n)
    if n==0:
        return 1
    else:
        return n*rec_factorial(n-1)
    

rec_factorial(10)

n =  10
n =  9
n =  8
n =  7
n =  6
n =  5
n =  4
n =  3
n =  2
n =  1
n =  0

3628800

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}$

def add(m, n):
    print('m, n = ', (m, n))
    if n==0:
        return m
    else:
        return add(m+1, n-1)

add(5, 0)

m, n =  (5, 0)

5

add(5, 1)

m, n =  (5, 1)
m, n =  (6, 0)

6

add(5, 5)

m, n =  (5, 5)
m, n =  (6, 4)
m, n =  (7, 3)
m, n =  (8, 2)
m, n =  (9, 1)
m, n =  (10, 0)

10

Example: Binary search

def bin_search(x, lst):   # assumes lst is sorted
    # look at middle of lst for x, if found return true (base case)
    # check if x is bigger or smaller than middle of lst, recursively call bin_search on the correct half
    # another base case is if lst has nothing left in it (lst is the current part of the original lst)
    if len(lst)>0:
        midIndex=len(lst)//2  # since we know the length of lst, we can find the middle index   len(lst)//2
        if lst[midIndex] == x:
            return True
        else:
            if lst[midIndex] > x:   # look at lower half
                return bin_search(x,lst[:midIndex])
            else:  #  look at upper half
                return bin_search(x,lst[midIndex+1:] )
    else:
        return False
        # the python list slices are O(n), this ruins the expected O(lgn) for bin search

bin_search(20, list(range(100)))

True

bin_search(-1, list(range(100)))

False

bin_search(50.5, list(range(100)))

False

bin_search(0, list(range(100)))
bin_search(99, list(range(100)))
bin_search(100, list(range(100)))

True

True

False

def bin_search1(x, lst):   # assumes lst is sorted   
    def rec_bin_search1(x, lst, start, end):   # assumes lst is sorted   start=0    
        if end>=start:   #items left to look at
            midIndex=(start+end)//2
            if lst[midIndex] == x:
                return True
            else:
                if lst[midIndex] > x:   # look at lower half
                    return rec_bin_search1(x,lst,start, midIndex-1)
                else:  #  look at upper half
                    return rec_bin_search1(x,lst,midIndex+1, end)
        else:
            return False
    return rec_bin_search1(x, lst, 0, len(lst)-1)

bin_search1(0, list(range(100)))
bin_search1(99, list(range(100)))
bin_search1(100, list(range(100)))

True

True

False

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, ...

def rec_fib(n):
    print('n = ', n)
    if n==0 or n==1:
        return n
    else:
        return rec_fib(n-1)+rec_fib(n-2)

rec_fib(5)

n =  5
n =  4
n =  3
n =  2
n =  1
n =  0
n =  1
n =  2
n =  1
n =  0
n =  3
n =  2
n =  1
n =  0
n =  1

5

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?

height = 3
towers = [[] for _ in range(3)]   #  towers is a list of three empty lists   0       1     2
towers[0] = list(range(height, 0, -1))   #tower 0 is "from" initially
 #[  [ 3 2 1 ]   [  ]    [ ]   ]
  #     from      using    to
  #  3 disc is bigger than 2 disk is bigger than 1 disc
    # 3 disc at 0 position means on the bottom or rod
   
def move(frm, to):   # frm and to are rod numbers
    # not doing error checking, assuming we are only moving correctly
    if len(towers[to])==0  or  towers[frm][len(towers[frm])-1] < towers[to][len(towers[to])-1]:
        towers[to].append(towers[frm].pop(-1))
        display()
    else:
        print("move error")

def hanoi(frm, to, using, levels):   #innitially frm=0  to=2   using=1  levels is how many discs on frm
    if levels==1:
        move(frm, to)
    else:
        # move levels-1 disks frm to using  recursion
        # move 1 disk frm to to
        # move levels-1 disks using to to  recurson
        hanoi(frm, using, to, levels-1)
        move (frm, to)
        hanoi(using, to, frm, levels-1)
        

towers

[[3, 2, 1], [], []]

from time import sleep
from IPython.display import clear_output

def display():
    clear_output(True)
    print('{:^12}'.format('||') * 3)
    for level in range(height, 0, -1):
        for t in towers:
            try:
                print('{:^12}'.format('==' * t[level-1]), end='')
            except IndexError:
                print('{:^12}'.format('||'), end='')
        print()
    print('-' * 36)
    sleep(1)

display()

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

hanoi(0, 2, 1, 3)

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

height = 5
towers = [[] for _ in range(3)]
towers[0] = list(range(height, 0, -1))
hanoi(0, 2, 1, 5)

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

Example: Mergesort

def merge(l1, l2): # O(N), where N is the number of elements in the two lists
    merged = []
    i1 = i2 = 0
    while i1 < len(l1) or i2 < len(l2):   # as long as at least one of l1 and l2 has items
        if i2 == len(l2) or (i1 < len(l1)    # find the smaller item in l1 or l2
                             and l1[i1] < l2[i2]):
        # no items in l2   OR   items in both and l1[i1] < l2[i2]
            merged.append(l1[i1])
            i1 += 1
        else:
            merged.append(l2[i2])
            i2 += 1
    return merged

l1 = [1, 5, 9]
l2 = [2, 6, 8, 11]
merge(l1, l2)

[1, 2, 5, 6, 8, 9, 11]

def merge1(lst, a,b,c): #first sorted part is a to b  indicies
    # second sorted part is b+1 to c  indicies
    merged = []
    i1 = a
    i2 = b+1
    while i1 <= b or i2 <= c:   
        if i2 == c+1 or (i1 <= b and lst[i1] < lst[i2]):
            merged.append(lst[i1])
            i1 += 1
        else:
            merged.append(lst[i2])
            i2 += 1
    # copy the merged into lst[a : c  ]
    i=a
    for x in merged:
        lst[i]=x
        i+=1
        

def mergesort(data):   # always O(N lg N)
    def rec_mergesort(lst, frm, to):   #frm and to are indexes in lst defining the subproblem
        if frm==to:  #base case
            pass
        else:
            mid=(frm+to)//2
            rec_mergesort(lst, frm, mid)
            rec_mergesort(lst, mid+1, to)
            merge1(lst, frm, mid, to)  #first sorted part is frm to mid  indicies
                                # second sorted part is mid+1 to to  indicies
   
    rec_mergesort(data, 0, len(data)-1)   # line is outside the  def rec_mergesort

import random
lst = list(range(10))
random.shuffle(lst)

lst

[4, 2, 8, 1, 0, 6, 7, 9, 5, 3]

mergesort(lst)
lst

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

def insertion_sort(lst):
    for i in range(1, len(lst)):
        for j in range(i, 0, -1):
            if lst[j-1] > lst[j]:
                lst[j-1], lst[j] = lst[j], lst[j-1] # swap
            else:
                break   

class Heap:
    def __init__(self):
        self.data = []

    @staticmethod
    def _parent(idx):
        return (idx-1)//2
        
    @staticmethod
    def _left(idx):
        return idx*2+1

    @staticmethod
    def _right(idx):
        return idx*2+2
    
    def _heapify(self, idx=0):
        while True:
            l = Heap._left(idx)
            r = Heap._right(idx)
            maxidx = idx
            if l < len(self) and self.data[l] > self.data[idx]:
                maxidx = l
            if r < len(self) and self.data[r] > self.data[maxidx]:
                maxidx = r
            if maxidx != idx:
                self.data[idx], self.data[maxidx] = self.data[maxidx], self.data[idx]
                idx = maxidx
            else:
                break
            
    def add(self, x):
        self.data.append(x)
        i = len(self.data) - 1
        p = Heap._parent(i)
        while i > 0 and self.data[p] < self.data[i]:
            self.data[p], self.data[i] = self.data[i], self.data[p]
            i = p
            p = Heap._parent(i)
        
    def max(self):
        return self.data[0]

    def pop_max(self):
        ret = self.data[0]
        self.data[0] = self.data[len(self.data)-1]
        del self.data[len(self.data)-1]
        self._heapify()
        return ret
    
    def __bool__(self):
        return len(self.data) > 0

    def __len__(self):
        return len(self.data)


def heapsort(iterable):
    heap = Heap()
    for x in iterable:
        heap.add(x)
    sorted_lst = []
    while heap:
        sorted_lst.append(heap.pop_max())
    sorted_lst.reverse()
    return sorted_lst

import timeit
import random
insertionsort_times = []
heapsort_times = []
mergesort_times = []
for size in range(100, 3000, 100):
    insertionsort_times.append(timeit.timeit(stmt='insertion_sort(lst)',
                               setup='import random ; from __main__ import insertion_sort ; '
                                         'lst = [random.random() for _ in range({})]'.format(size),
                               number=1))
    heapsort_times.append(timeit.timeit(stmt='heapsort(lst)',
                               setup='import random ; from __main__ import heapsort ; '
                                         'lst = [random.random() for _ in range({})]'.format(size),
                               number=1))
    mergesort_times.append(timeit.timeit(stmt='mergesort(lst)'.format(size),
                               setup='import random ; from __main__ import mergesort ; '
                                         'lst = [random.random() for _ in range({})]'.format(size),
                               number=1))

%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(insertionsort_times, 'ro')
plt.plot(heapsort_times, 'b^')
plt.plot(mergesort_times, 'gs')
plt.show()

[<matplotlib.lines.Line2D at 0x2089e4550d0>]

[<matplotlib.lines.Line2D at 0x2089e455520>]

[<matplotlib.lines.Line2D at 0x2089e4557f0>]

%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(heapsort_times, 'b^')
plt.plot(mergesort_times, 'gs')
plt.show()

[<matplotlib.lines.Line2D at 0x2089e5319d0>]

[<matplotlib.lines.Line2D at 0x2089e531e20>]

# power set generation, set of all subsets of a set
def powerSet(s):   # s is the set (python list)
    def rec_powerSet(s, n, pset):  # n is the size of the current set s, pset is a list of the powerset so far
        if n>=0:
            rec_powerSet(s, n-1, pset)  # don't add the nth item to the pset
            pset.append(s[n])
            rec_powerSet(s, n-1, pset)  # add the nth item to the pset
            del pset[-1]
        else:
            print(pset)
    rec_powerSet(s, len(s)-1, [])    

powerSet([1,2,3])

[]
[1]
[2]
[2, 1]
[3]
[3, 1]
[3, 2]
[3, 2, 1]

# combination generation, C(n,r)  n objects choose r, order doesn't matter
def combos(s, n, r): # s is the set (python list)
    def rec_combos(s, n, r, answerSoFar):    #C(n,r)
        if r>0 and n>=0:
             #C(n-1,r)   don't use item n
            rec_combos(s, n-1, r, answerSoFar)
            answerSoFar.append(s[n])    
             #C(n-1,r-1)   use item n
            rec_combos(s, n-1, r-1, answerSoFar)
            del answerSoFar[-1]
        else:  
            if r==0:   #we must have found an answer
                print(answerSoFar)
        
    rec_combos(s, len(s)-1, r, [])

combos([ 1, 2 ,3], 3, 2)

[2, 1]
[3, 1]
[3, 2]

combos([ 1, 2 ,3,4,5], 5, 3)

[3, 2, 1]
[4, 2, 1]
[4, 3, 1]
[4, 3, 2]
[5, 2, 1]
[5, 3, 1]
[5, 3, 2]
[5, 4, 1]
[5, 4, 2]
[5, 4, 3]

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?

def change(amount, denoms):    # denoms is a list
    def rec_change(amount, denoms, n, answerSoFar):   #n is which coins I am cosidering
        if amount==0:
            print(answerSoFar)
            return 1
        elif amount<0 or n<0:  #done, not a valid answer
            return 0
        else:   #possibly try the two subproblems, use coin n, don't use coin n anymore
            x= rec_change(amount-denoms[n], denoms, n, answerSoFar+(denoms[n],))
            y=rec_change(amount, denoms, n-1, answerSoFar)
            return x+y
        
    return rec_change(amount, denoms, len(denoms)-1, ())  #  answerSoFar inisitally an empty  tuple]

x=change(5, (1, 5, 10, 25))
x

(5,)
(1, 1, 1, 1, 1)

2

change(10, (1, 5, 10, 25))

(10,)
(5, 5)
(5, 1, 1, 1, 1, 1)
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

4

change(1000, (1, 5, 10, 25))

3. The Call Stack (if time allows)

Simulating recursive factorial

class Stack(list):
    push = list.append
    pop  = lambda self: list.pop(self, -1)
    peek = lambda self: self[-1]
    empty = lambda self: len(self) == 0

call_stack = Stack()

def call(arg):
    call_stack.push('<frame begin>')
    call_stack.push(('arg', arg))

def get_arg():
    return call_stack.peek()[-1]

def save_local(name, val):
    call_stack.push(('local', name, val))
    
def restore_local():
    return call_stack.pop()[2]
    
def return_with(val):
    while call_stack.pop() != '<frame begin>':
        pass
    call_stack.push(('ret', val))
    
def last_return_val():
    return call_stack.pop()[-1]

call(10) # initial call
while True: # recursive calls
    n = get_arg()
    if n == 1:
        return_with(1)
        break
    else:
        save_local('n', n)
        call(n-1)

call_stack

ret = last_return_val()
n = restore_local()
return_with(n * ret)
call_stack

Debugging with pdb

def bin_search(x, lst):   #ipdb
    if len(lst) == 0:
        return False
    else:
        print('lo, hi = ', (lst[0], lst[-1]))
        #breakpoint()
        mid = len(lst) // 2
        if x == lst[mid]:
            return True
        elif x < lst[mid]:
            return bin_search(x, lst[:mid])
        else:
            return bin_search(x, lst[mid+1:])

bin_search(20, list(range(100)))

lo, hi =  (0, 99)
lo, hi =  (0, 49)
lo, hi =  (0, 24)
lo, hi =  (13, 24)
lo, hi =  (20, 24)
lo, hi =  (20, 21)
lo, hi =  (20, 20)

True

def bin_search(x, lst):   #ipdb
    if len(lst) == 0:
        return False
    else:
        #print('lo, hi = ', (lst[0], lst[-1]))
        breakpoint()
        mid = len(lst) // 2
        if x == lst[mid]:
            return True
        elif x < lst[mid]:
            return bin_search(x, lst[:mid])
        else:
            return bin_search(x, lst[mid+1:])

bin_search(20, list(range(100)))