On Recursion¶
Agenda¶
- Recursion
- stopping recursion: simplification & base cases
- Recursive "shapes":
- Linear (single) recursion:
- Factorial
- Addition
- Binary search
- Tree (multiple) recursion: divide and conquer
- Fibonacci numbers
- Tower of Hanoi
- Merge sort
- Making change
- Linear (single) recursion:
- The Call Stack and Stack Frames
- simulating recursion
- debugging with
pdband%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:
In [1]:
class Bag:
def __init__(self, price, *contents):
self.price = price
self.contents = contents
In [2]:
bag1 = Bag(10)
In [3]:
bag2 = Bag(5, Bag(3))
In [4]:
bag3 = Bag(5, Bag(4, Bag(3)), Bag(2))
In [5]:
bag4 = Bag(0, Bag(5), Bag(10), Bag(3, Bag(2), Bag(100)), Bag(9, Bag(2, Bag(25))))
In [6]:
def price(bag):
p = bag.price
for b in bag.contents:
p += price(b)
return p
In [7]:
price(bag4)
Out[7]:
Stopping recursion: simplification & base case(s)¶
In [8]:
import sys
sys.setrecursionlimit(100)
In [9]:
def silly_rec(n):
if n == 0: # base case
return
n = n - 1 # simplify
silly_rec(n)
In [10]:
silly_rec(10)
To help visualize the recursive process, we can simply substitute the value of the parameter in each recursive call.
E.g., for silly_rec(5):
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$
In [11]:
def rec_factorial(n):
print('n = ', n)
if n == 0:
return 1
else:
return n * rec_factorial(n-1)
rec_factorial(10)
Out[11]:
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}$
In [12]:
def add(m, n):
print('m, n = ', (m, n))
if n == 0:
return m
else:
return add(m+1, n-1)
In [13]:
add(5, 0)
Out[13]:
In [14]:
add(5, 1)
Out[14]:
In [15]:
add(5, 5)
Out[15]:
Example: Binary search¶
In [16]:
def bin_search(x, lst):
if len(lst) == 0:
return False
else:
print('lo, hi = ', (lst[0], lst[-1]))
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:])
In [17]:
bin_search(20, list(range(100)))
Out[17]:
In [18]:
bin_search(-1, list(range(100)))
Out[18]:
In [19]:
bin_search(50.5, list(range(100)))
Out[19]:
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, ...
In [20]:
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)
Out[20]:
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):
- Move the small disc (0) from L to R
- Move the medium disc (1) from L to M
- Move 0 from R to M (R is empty)
- Move the large disc (2) from L to R
- Move 0 from M to L
- Move 1 from M to R
- 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?
In [21]:
height = 5
towers = [[] for _ in range(3)]
towers[0] = list(range(height, 0, -1))
def move(frm, to):
towers[to].append(towers[frm].pop(-1))
display()
def hanoi(frm, to, using, levels):
if levels == 1:
move(frm, to)
else:
hanoi(frm, using, to, levels-1)
move(frm, to)
hanoi(using, to, frm, levels-1)
In [22]:
towers
Out[22]:
In [23]:
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)
In [24]:
hanoi(0, 2, 1, 5)
Example: Mergesort¶
In [6]:
def merge(l1, l2):
merged = []
i1 = i2 = 0
while i1 < len(l1) or i2 < len(l2):
if i2 == len(l2) or (i1 < len(l1)
and l1[i1] < l2[i2]):
merged.append(l1[i1])
i1 += 1
else:
merged.append(l2[i2])
i2 += 1
return merged
In [7]:
l1 = [1, 5, 9]
l2 = [2, 6, 8, 11]
merge(l1, l2)
Out[7]:
In [8]:
def mergesort(lst, lo, hi):
if lo > hi:
return []
elif lo == hi:
return lst[lo:lo+1]
else:
mid = (lo + hi) // 2
return merge(mergesort(lst, lo, mid),
mergesort(lst, mid+1, hi))
In [9]:
import random
lst = list(range(10))
random.shuffle(lst)
In [10]:
mergesort(lst, 0, len(lst))
Out[10]:
In [11]:
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
In [12]:
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
In [18]:
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, 0, {}-1)'.format(size),
setup='import random ; from __main__ import mergesort ; '
'lst = [random.random() for _ in range({})]'.format(size),
number=1))
In [20]:
%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(insertionsort_times, 'ro')
plt.plot(heapsort_times, 'b^')
plt.plot(mergesort_times, 'gs')
plt.show()
In [21]:
%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(heapsort_times, 'b^')
plt.plot(mergesort_times, 'gs')
plt.show()
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?
Key observation: the number of ways we can make up some amount $N$ using $k$ different denominations is equal to:
- the number of ways we can make $N$ excluding some denomination $d_i$, plus
- the number of ways we can make $(N - d_i)$ using all $k$ denominations
In [3]:
def change(amount, denoms):
if amount == 0:
return 1
elif amount < 0 or not denoms:
return 0
else:
return (change(amount, denoms[1:])
+ change(amount-denoms[0], denoms))
In [5]:
change(5, (1, 5, 10, 25))
Out[5]:
In [7]:
change(100, (1, 5, 10, 25))
Out[7]:
Followup question: can we list the actual ways of making change?
In [10]:
# approach 1: build a tuple on the way "down" the recursion
def change(amount, denoms, way=()):
if amount == 0:
print(way)
return 1
elif amount < 0 or not denoms:
return 0
else:
return (change(amount, denoms[1:], way)
+ change(amount-denoms[0], denoms, way + (denoms[0],)))
In [11]:
change(5, (1, 5, 10, 25))
Out[11]:
In [12]:
change(10, (1, 5, 10, 25))
Out[12]:
In [15]:
# approach 2: build a list of tuples on the way back "up" the recursion
def change(amount, denoms):
if amount == 0:
return [()]
elif amount < 0 or not denoms:
return []
else:
ways = []
ways.extend(change(amount, denoms[1:]))
ways.extend([w + (denoms[0],) for w in change(amount-denoms[0], denoms)])
return ways
In [16]:
change(10, (1, 5, 10, 25))
Out[16]:
3. The Call Stack¶
Simulating recursive factorial¶
In [35]:
class Stack(list):
push = list.append
pop = lambda self: list.pop(self, -1)
peek = lambda self: self[-1]
empty = lambda self: len(self) == 0
In [36]:
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]
In [37]:
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)
In [38]:
call_stack
Out[38]:
In [47]:
ret = last_return_val()
n = restore_local()
return_with(n * ret)
call_stack
Out[47]:
Debugging with pdb and %debug¶
In [48]:
import sys
sys.setrecursionlimit(100)
In [49]:
def rec_factorial(n):
if n <= 1: # detect base case
raise Exception('base case!')
else:
return n * rec_factorial(n-1)
In [50]:
rec_factorial(10)
In [ ]:
%debug
# commands to try:
# help, where, args, p n, up, u 10, down, d 10, l, up 100, u, d (& enter to repeat)
In [51]:
def bin_search(x, lst):
if len(lst) == 0:
return False
else:
print('lo, hi = ', (lst[0], lst[-1]))
mid = len(lst) // 2
if x == lst[mid]:
import pdb ; pdb.set_trace()
return True
elif x < lst[mid]:
return bin_search(x, lst[:mid])
else:
return bin_search(x, lst[mid+1:])
In [53]:
bin_search(20, list(range(100)))