15-112 Fundamentals of Programming

Notes - Lecture 5.3


Content

  1. Basic Examples
    1. digitSum
    2. factorial
    3. sum
    4. rangeSum
    5. listSum
    6. power
  2. Divide and Conquer Examples
    1. rangeSum
    2. listSum
  3. Examples with Multiple Base or Recursive Cases
    1. power with negative exponents
  4. Examples with Multiple Recursive Calls
    1. fibonacci
  5. Towers of Hanoi

Basic examples

1. digitSum

def digitSum(n):
    if (n < 0): return digitSum(abs(n))
    elif (n < 10): return n
    else: return (n%10) + digitSum(n//10)

assert(digitSum(-12345) == 1+2+3+4+5)
print("ok!")

2. factorial

def factorial(n):
    if (n == 0): return 1
    else: return n * factorial(n-1)

assert(factorial(5) == 5*4*3*2*1)
print("ok!")

3. sum

def sum(n):
    if (n == 0): return 0
    else: return n + sum(n-1)

assert(sum(5) == 5+4+3+2+1)
print("ok!")

4. rangeSum

def rangeSum(lo, hi):
    if (lo > hi):
        return 0
    else:
        return lo + rangeSum(lo+1, hi)

print(rangeSum(10,15)) # 75

5. listSum

def listSum(L):
    if (len(L) == 0):
        return 0
    else:
        return L[0] + listSum(L[1:])

print(listSum([2,3,5,7,11])) # 28

6. power

def power(base, expt):
    # assume expt is non-negative integer
    if (expt == 0):
        return 1
    else:
        return base * power(base, expt-1)

print(power(2,5)) # 32

Divide and Conquer Examples

1. rangeSum

def rangeSum(lo, hi):
    if (lo == hi):
        return lo
    else:
        mid = (lo + hi)//2
        return rangeSum(lo, mid) + rangeSum(mid+1, hi)

print(rangeSum(10,15)) # 75

2. listSum

def listSum(L):
    if (len(L) == 0):
        return 0
    elif (len(L) == 1):
        return L[0]
    else:
        mid = len(L)//2
        return listSum(L[:mid]) + listSum(L[mid:])

print(listSum([2,3,5,7,11])) # 28

Examples with Multiple Base or Recursive Cases

1. power with negative exponents

def power(base, expt):
    # This version allows for negative exponents
    # It still assumes that expt is an integer, however.
    if (expt == 0):
        return 1
    elif (expt < 0):
        return 1.0/power(base,abs(expt))
    else:
        return base * power(base, expt-1)

print(power(2,5)) # 32
print(power(2,-5)) # 1/32 = 0.03125

Examples with Multiple Recursive Calls

1. fibonacci

A first attempt 
def fib(n):
    if (n < 2):
        # Base case:  fib(0) and fib(1) are both 1
        return 1
    else:
        # Recursive case: fib(n) = fib(n-1) + fib(n-2)
        return fib(n-1) + fib(n-2)

print([fib(n) for n in range(15)])
Once again, printing call stack using recursion depth: 
def fib(n, depth=0):
    print("   "*depth, "fib(", n, " )")
    if (n < 2):
        # Base case:  fib(0) and fib(1) are both 1
        return 1
    else:
        return fib(n-1, depth+1) + fib(n-2, depth+1)
fib(4)
Even better (printing result, too): 
def fib(n, depth=0):
    print("   "*depth, "fib(", n, " )")
    if (n < 2):
        result = 1
        # Base case:  fib(0) and fib(1) are both 1
        print("   "*depth, "-->", result)
        return result
    else:
        result = fib(n-1, depth+1) + fib(n-2, depth+1)
        print("   "*depth, "-->", result)
        return result
fib(4)
Finally, not duplicating code: 
def fib(n, depth=0):
    print("   "*depth, "fib(", n, " )")
    if (n < 2):
        result = 1
    else:
        result = fib(n-1, depth+1) + fib(n-2, depth+1)
    print("   "*depth, "-->", result)
    return result
fib(4)

Towers of Hanoi

First attempt (without Python):
# This is the plan to solve Towers of Hanoi (based on magic!)
magically move(n-1, source, temp, target)
          move(  1, source, target, temp)
magically move(n-1, temp, target, source)
Turn into Python (The "magic" is recursion!):
def move(n, source, target, temp):
    move(n-1, source, temp, target)
    move(  1, source, target, temp)
    move(n-1, temp, target, source)

move(2, 0, 1, 2) # Does not work -- infinite recursion
Once again, with a base case:
def move(n, source, target, temp):
    if (n == 1):
        print((source, target), end="")
    else:
        move(n-1, source, temp, target)
        move(  1, source, target, temp)
        move(n-1, temp, target, source)

move(2, 0, 1, 2)
Once more, with a nice wrapper:
def move(n, source, target, temp):
    if (n == 1):
        print((source, target), end="")
    else:
        move(n-1, source, temp, target)
        move(  1, source, target, temp)
        move(n-1, temp, target, source)

def hanoi(n):
    print("Solving Towers of Hanoi with n =", n)
    move(n, 0, 1, 2)
    print()

hanoi(4)
Iterative Towers of Hanoi (just to see it's possible):
def iterativeHanoi(n):
    def f(k): return (k%3) if (n%2==0) else (-k%3)
    return [(f(move & (move-1)),
             f((move|(move-1))+1)) for move in range(1,1 << n)]

def recursiveHanoi(n, source=0, target=1, temp=2):
    if (n == 1):
        return [(source, target)]
    else:
        return (recursiveHanoi(n-1, source, temp, target) +
                recursiveHanoi(  1, source, target, temp) +
                recursiveHanoi(n-1, temp, target, source))

def compareIterativeAndRecursiveHanoi():
    for n in range(1,10):
        assert(iterativeHanoi(n) == recursiveHanoi(n))
    print("iterative and recursive solutions match exactly in all tests!")

compareIterativeAndRecursiveHanoi()


Valid CSS! Valid XHTML 1.0 Strict