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):   # iterable "list" of Bag objects,possibly empty None
        self.price = price
        self.contents = contents

bag1 = Bag(10)

bag2 = Bag(5, Bag(3))
bag2.price
bag2.contents
bag2.contents[0].price

5

(<__main__.Bag at 0x13c7cf94c70>,)

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 totalprice(bag):   # every call to totalprice has its own local variables  bag, temp
    temp=bag.price   
    for b in bag.contents:
        temp=temp+totalprice(b)
    return temp    

totalprice(bag1)
totalprice(bag2)
totalprice(bag3)
totalprice(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)

silly_rec(1)

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

~\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)
    silly_rec(n-1)
silly_rec(5)

5
4
3
2
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

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-18-0ce4f57f0cd5> in <module>
      2     print(n)
      3     silly_rec(n-1)
----> 4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
      2     print(n)
----> 3     silly_rec(n-1)
      4 silly_rec(5)

<ipython-input-18-0ce4f57f0cd5> in silly_rec(n)
      1 def silly_rec(n):
----> 2     print(n)
      3     silly_rec(n-1)
      4 silly_rec(5)

~\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>0:
        silly_rec(n-1)
silly_rec(5)

5
4
3
2
1
0

2. Recursive "shapes"

Linear recursion

def findMax(lst):  #unsorted list, length n items, find max
    # subproblem is the max of first n-1 items
    if len(lst)>1:
        temp = findMax(lst[0:len(lst)-1])
        if temp > lst[len(lst)-1]:
            return temp
        else:
            return lst[len(lst)-1]
    else:
        return lst[0]
    #O(n^2)

findMax([4,-2,6,8,0])

8

def findMax1(lst, toIndex):  #unsorted list, length n items, find max   toIndex is initially len(lst)-1
    # subproblem is the max of first n-1 items
    if toIndex>0:
        temp = findMax1(lst, toIndex-1)
        if temp > lst[toIndex]:
            return temp
        else:
            return lst[toIndex]
    else:
        return lst[0]
    
    #  O(n) recursive calls

findMax1([4,-2,6,8,0], 4)

8

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, frm, to):   #x is item to look for, lst is the sorted list
    # frm is initially 0    to is initially len(lst)-1
    print(frm, to)
    if frm <= to:
        midIndex = (frm+to)//2
        if lst[midIndex] == x:
            return midIndex
        elif lst[midIndex] > x:   # look on left side
            to = midIndex-1
            return bin_search(x, lst, frm, to)
        else:
            frm = midIndex+1
            return bin_search(x, lst, frm, to) 
    else:
        return -1
        

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

0 99
0 48
0 23
12 23
18 23

20

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

0 99
0 48
0 23
0 10
0 4
0 1
0 -1

-1

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

0 99
50 99
50 73
50 60
50 54
50 51
51 51
51 50

-1

def rec_bin_search(x, lst, frm, to):   #x is item to look for, lst is the sorted list
    # frm is initially 0    to is initially len(lst)-1
    print(frm, to)
    if frm <= to:
        midIndex = (frm+to)//2
        if lst[midIndex] == x:
            return midIndex
        elif lst[midIndex] > x:   # look on left side
            to = midIndex-1
            return bin_search(x, lst, frm, to)
        else:
            frm = midIndex+1
            return bin_search(x, lst, frm, to) 
    else:
        return -1

def binarySearch(x, lst):
    return rec_bin_search(x, lst, 0, len(lst)-1)

binarySearch(20, list(range(100)))

0 99
0 48
0 23
12 23
18 23

20

Tree recursion

def findMax2(lst):  #unsorted list, length n items, find max
    # subproblems are the max of first half and the max of the second half
    if len(lst)>1:
        temp1 = findMax2(lst[0:((len(lst)-1)//2 ) +1])
        temp2 = findMax2(lst[((len(lst)-1)//2)+1:])        
        if temp1 > temp2:
            return temp1
        else:
            return temp2
    else:
        return lst[0]
    
    #O(n)

findMax2([4,-2,6,8,0,10])

10

findMax2([4,-2,6,8,0])

8

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:
        return 0
    elif n==1:
        return 1
    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[0]   towers[1]  towers[2]
towers[0] = list(range(height, 0, -1))   #towers[0]=[3 2 1]   top is rightmost

def move(frm, to):
    towers[to].append(towers[frm].pop(-1))   #not error checking, assume small on big only
    display()

        #  0   2    1   initial call
def hanoi(frm, to, using, levels):   # frm, to, using are labels on the rods  0 or 1 or 2
    # levels is size of the current subproblem (how many discs I am moving)
    # base case    if len(towers[frm]) == 1  OR if levels==1
    if levels==1:
        move(frm, to)
    else:
        # solve the (n-1) subproblem   from to using
        #move the biggest disc  from to to
         # solve the (n-1) subproblem   using to to
        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 = 4
towers = [[] for _ in range(3)]  #towers[0]   towers[1]  towers[2]
towers[0] = list(range(height, 0, -1))   #towers[0]=[4 3 2 1]   top is rightmost
towers

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

hanoi(0, 2, 1, 4)

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

Example: Mergesort

def merge(l1, l2): # O(N), where N is the number of elements in the two lists
    # assumes l1 and l2 are sorted lists
    merged = []
    i1 = i2 = 0   #i1 is index to beginning of l1    i2 is index to beginning of l2
   
    # loop is O(n)     merge is amortized O(n), worst case O(n^2)
    while i1 < len(l1) or i2 < len(l2):   # i still have items to check in one or the other list or both
        if i2 == len(l2) or (i1 < len(l1)    #I have run out of l2 items
                             # or I have l1 items left and l1 item is smaller than the l2 item
                             and l1[i1] < l2[i2]):    # case that take an item from l1
        # no items in l2   OR   items in both and l1[i1] < l2[i2]
            merged.append(l1[i1])  #append is amortized O(1), worst case O(n)
            i1 += 1
        else:    # or i take the item from l2
            merged.append(l2[i2])
            i2 += 1
    return merged
# given two sorted lists return a new list of all items in sorted order

f=10*[None]
f

[None, None, None, None, None, None, None, None, None, None]

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

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

def merge(l1, l2): # O(N), where N is the number of elements in the two lists
    merged = (len(l1)+len(l2) )*[None]
    i1 = i2 = 0   #i1 is index to beginning of l1    i2 is index to beginning of l2
    k=0
    # loop is O(n)     merge is amortized O(n), worst case O(n^2)
    while i1 < len(l1) or i2 < len(l2):   # i still have items to check in one or the other list or both
        if i2 == len(l2) or (i1 < len(l1)    #I have run out of l2 items
                             # or I have l1 items left and l1 item is smaller than the l2 item
                             and l1[i1] < l2[i2]):    # case that take an item from l1
        # no items in l2   OR   items in both and l1[i1] < l2[i2]
            merged[k]= l1[i1]
            k+=1
            i1 += 1
        else:    # or i take the item from l2
            merged[k]= l2[i2]
            k+=1
            i2 += 1
    return merged
# given two sorted lists return a new list of all items in sorted order

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

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

            #        0        len(lst)-1   initial indexes
    # every call to mergesort must return a sorted sublist
def mergesort(lst, frmIndex, toIndex):    #minimize the number of slices
    #base case  n=1
    if frmIndex == toIndex:   # only one item in subproblem, nothing to do
        return lst[frmIndex:frmIndex+1] # return list of 1 item (slice)
    elif frmIndex>toIndex:     # no items in subprob
        return []
    else:    # my subproblem has more than 1 item
        #find the middle index
        #call MS on first half
        #call MS on second half
        #call merge
        mid = (frmIndex+toIndex)//2
        return merge(mergesort(lst, frmIndex, mid),  mergesort(lst, mid+1, toIndex))     
        

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

lst

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

mergesort(lst, 0, 9)

[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,0,{}-1)'.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 0x21012b8aeb0>]

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

def merge(lst, f, m, t): # O(N), where N is the number of elements in the two lists
    merged = (t-f+1)*[None]
    i1 =f #i1 is index to beginning of l1  lst = [ .... l1   and l2   ....]
    i2 = m+1  #i2 is index to beginning of l2
    k=0
    # loop is O(n)    
    while i1 <= m or i2 <=t:   # i still have items to check in one or the other list or both
        if i2 == t+1 or (i1 <= m    #I have run out of l2 items
                             # or I have l1 items left and l1 item is smaller than the l2 item
                             and lst[i1] < lst[i2]):    # case that take an item from l1
        # no items in l2   OR   items in both and l1[i1] < l2[i2]
            merged[k]= lst[i1]
            k+=1
            i1 += 1
        else:    # or i take the item from l2
            merged[k]= lst[i2]
            k+=1
            i2 += 1
    #copy merged back into the lst
    k=f
    for val in merged:   #merged is sorted, copy it back into the lst argument starting at index f
        lst[k]=val
        k+=1

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

merge(l,0,2,6)
l

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

l = [1,5,4,1, 5, 9, 2, 6, 8, 11, 421, 1, 4]
#    0 1 2 3 4   5 6  7  8   9
merge(l,3,5,9)
l

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

            #        0        len(lst)-1   initial indexes
def mergesort(lst, frmIndex, toIndex):    #minimize the number of slices
    #base case  n=1
    if frmIndex >= toIndex:   
        pass
    else:
        mid = (frmIndex+toIndex)//2
        mergesort(lst, frmIndex, mid)
        mergesort(lst, mid+1, toIndex)
        merge(lst, frmIndex,mid,toIndex)    
        

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

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

mergesort(lst,0,9)
lst

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

# power set problem, set of all subsets of a set (lst a sequence type)
def powerSet(lst, n, setSoFar=[] ):  
# n is how many items in the subproblem intialcall  powerSet(lst, len(lst))
    if n<0:  #current set has no items
        print( setSoFar)
    else:
        temp=lst[n]
        powerSet(lst, n-1, setSoFar)   # don't use temp
        setSoFar.append(temp)
        powerSet(lst, n-1, setSoFar)   # use temp
        setSoFar.pop()

powerSet(['A','B','C'], 2, [] )

[]
['A']
['B']
['B', 'A']
['C']
['C', 'A']
['C', 'B']
['C', 'B', 'A']

# palindrome or not
def isPal(s):
    if len(s)==1 or len(s)==0:
        return True
    elif s[0]==s[-1]:
        return isPal(s[1:-1])
    else:
        return False
    

isPal("racecar")
isPal("raccar")
isPal("dog")

True

True

False

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

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

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

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):
    if len(lst) == 0:
        return False
    else:
        print('lo, hi = ', (lst[0], lst[-1]))
        # breakpoint()
        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:])

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