Recursion and Dynamic Programming

Gregory M. Kapfhammer

March 18, 2024

Recursion means a “reference to self”!

• Implementation of recursion in Python language
• Mental model for how to think about recursive functions
• Use of recursion as a problem solving technique
• Analysis of the running time of recursive functions

Recursive implementation of sumk

def sumk(k):
    if k > 0:
        return sumk(k-1) + k
    return 0

print(sumk(1))
print(sumk(2))
print(sumk(3))
print(sumk(4))
print(sumk(5))

1
3
6
10
15

• The sumk function calls itself with a smaller value of k
• The base case stops the recursion when k is equal to 0

Termination of recursive functions

How to ensure that a recursive function stops running?

• Base case stops the recursion by returning fixed value
• Recursive case reduces the input towards the base case
• Recursive calls are made of smaller sub-problems

What happens if the base case is not reached?

• The recursive function will enter an infinite recursion
• Python limits adding recursive functions to call stack
• The program will ultimately raise the RecursionError

The call stack and recursion

def sumsquarek(k):
    if k == 0:
        return 0
    else:
        return k ** 2 + sumsquarek(k - 1)

print(sumsquarek(1))  # Output: 1
print(sumsquarek(2))  # Output: 5
print(sumsquarek(3))  # Output: 14
print(sumsquarek(4))  # Output: 30
print(sumsquarek(5))  # Output: 55

1
5
14
30
55

• The sumsquarek function calls itself with a smaller value of k
• The base case stops the recursion when k is equal to 0

RecursionError with functions

def a(k):
    if k == 0: return 0
    return b(k)

def b(k):
    return c(k)

def c(k):
    return a(k-1)

a(340)

• This program will raise a RecursionError in Python
• Interestingly, it does not contain a recursive function!
• Error signals that Python reached limit of call stack

RecursionError with lists

A = [2]
B = [2]
A.append(A)
B.append(B)
A == B

• list.__eq__ method that compares two lists for == use
• The first elements of A and B are equal
• The second elements of A and B are actually lists
• This causes another call to the list.__eq__ method
• Ultimately, this leads to a RecursionError in Python
• Recursion is elegant but can lead to unexpected errors!

Iterative and recursive Fibonacci

def fibonacci_recursive(k):
    if k in [0,1]: return k
    return fibonacci_recursive(k-1) + fibonacci_recursive(k-2)

print([fibonacci_recursive(i) for i in range(10)])

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

def fibonacci_iterative(k):
    a, b = 0,1
    for i in range(k):
        a, b = b, a + b
    return a

print([fibonacci_iterative(i) for i in range(10)])

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

• Both approaches compute the Fibonacci sequence. Which one do you think is faster? Why do you think that is the case?

Recursive greatest common divisor

def gcd(a, b):
    if a == b:
        return a
    if a > b:
        a, b = b, a
    return gcd(a, b - a)

print("GCD of 12 and 513 is", gcd(12, 513))
print("GCD of 19 and 513 is", gcd(19, 513))
print("GCD of 19 and 515 is", gcd(515, 19))

GCD of 12 and 513 is 3
GCD of 19 and 513 is 19
GCD of 19 and 515 is 1

• Computes the greatest common divisor of two numbers
• Too many recursive calls when b is much larger than a!

Revising the recursive gcd

def gcd(a, b):
    if a > b:
        a, b = b, a
    if a == 0:
        return b
    return gcd(a, b % a)

print("GCD of 12 and 513 is", gcd(12, 513))
print("GCD of 19 and 513 is", gcd(19, 513))
print("GCD of 19 and 515 is", gcd(515, 19))

GCD of 12 and 513 is 3
GCD of 19 and 513 is 19
GCD of 19 and 515 is 1

• Both approach compute the same sequence of values
• Depending on inputs, one approach may be more efficient

What is dynamic programming?

• Solve a problem using solutions to sub-problems
• Often starts with an inefficient recursive algorithm
• Memoization stores the results of expensive function calls
• Tabulation stores the results of a bottom-up computation

Defective Greedy Change-Making

def greedyMC(coinvalueList, change):
    coinvalueList.sort()
    coinvalueList.reverse()
    numcoins = 0
    for c in coinvalueList:
        numcoins += change // c
        change = change % c
    return numcoins

print(greedyMC([1, 5, 10, 25], 63))
print(greedyMC([1, 21, 25], 63))    # Incorrect, should be 3
print(greedyMC([1, 5, 21, 25], 63)) # Incorrect, should be 3

6
15
7

• What is the minimum number of coins to make change for 63 cents? This greedyMC only works for canonical coin systems!

Slow Recursive Change-Making

def recMC(coinValueList, change):
   minCoins = change
   if change in coinValueList:
     return 1
   else:
      for i in [c for c in coinValueList if c <= change]:
         numCoins = 1 + recMC(coinValueList,change-i)
         if numCoins < minCoins:
            minCoins = numCoins
   return minCoins

print(recMC([1, 5, 10, 25], 63))
print(recMC([1, 21, 25], 63))
print(recMC([1, 5, 21, 25], 63))

• The recMC function calls itself with a smaller value of change
• Works correctly — but is very slow for certain input values!

Memoized Recursive Change-Making

def memoMC(coinValueList, change, knownResults):
    minCoins = change
    if change in coinValueList:
        knownResults[change] = 1
        return 1
    elif change in knownResults:
        return knownResults[change]
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + memoMC(coinValueList, change-i, knownResults)
            if numCoins < minCoins:
                minCoins = numCoins
                knownResults[change] = minCoins
    return minCoins

knownresults = {}
print(f"{memoMC([1, 5, 10, 21, 25], 63, knownresults)} coins needed.", end=" ")
print(f"Wow, computed {len(knownresults)} intermediate results!", end=" ")

3 coins needed. Wow, computed 60 intermediate results! 

Using dynamic programming

def dpMakeChange(coinValueList, change):
1    minCoins = [None]*(change + 1)
2    for cents in range(change+1):
3        minCoins[cents] = cents
4        for c in coinValueList:
            if cents >= c:
                minCoins[cents] = min(minCoins[cents], minCoins[cents - c] + 1)
5    return minCoins[change]

print(dpMakeChange([1,5,10,21,25], 63))

1

Create a list to store the answers to the sub-problems

2

For values from 0 to change, compute min number of coins

3

Assume at first that all 1 coins are used in solution

4

Determine if different coins can better make change

5

Return the element of the table with best solution

Dynamic programming

Key strategy in the dpMakeChange function

• Avoid recursive calls and memoization dictionary
• Starting with small values, build up the dictionary
• This is the essence of dynamic programming!

Implementation details of the dpMakeChange function

• Use a list accessed by an integer index
• Determine the next best step by trying each coin
• Subtract coin value from current value
• Check list for number of coins needed for remaining change

What are the similarities and differences between memoization and dynamic programming?

• Recursion

  • Works top down
  • Start with largest problem
  • Breaks to smaller problem

• Dynamic Programming
  • Works bottom up
  • Starts with smallest problem
  • Builds up to larger problem

Both algorithmic strategies can compute correct answer! Compare by experimentally studying runtime and analyzing running time.

Longest common subsequence

def lcs_recursive(X, Y):
    if X == "" or Y == "":
        return ""
    if X[-1] == Y[-1]:
        return lcs_recursive(X[:-1], Y[:-1]) + X[-1]
    else:
        return max([lcs_recursive(X[:-1], Y),
                    lcs_recursive(X, Y[:-1])], key = len)

lcs_str = lcs_recursive('ABCBDAB', 'BDCAB')
lcs_len = len(lcs_str)
print(f"LCS length is {lcs_len} and LCS contents are {lcs_str}")

LCS length is 4 and LCS contents are BCAB

• Code runs practically forever on moderate-sized inputs
• No matches in long strings yield depth-n binary call tree
• Wow, this means that there are \(2^n\) recursive calls!

LCS with dynamic programming

def lcs_dynamic(X, Y):
    t = {}
    for i in range(len(X)+1): t[(i,0)] = ""
    for j in range(len(Y)+1): t[(0,j)] = ""

    for i, x in enumerate(X):
        for j, y in enumerate(Y):
            if x == y:
                t[(i+1,j+1)] = t[(i, j)] + x
            else:
                t[(i+1,j+1)] = max([t[(i, j+1)], t[(i+1, j)]], key = len)
    return t[(len(X), len(Y))]

lcs_str = lcs_dynamic('ABCBDAB', 'BDCAB')
lcs_len = len(lcs_str)
print(f"LCS length is {lcs_len} and LCS contents are {lcs_str}")

LCS length is 4 and LCS contents are BCAB

• Total running time is \(O(k \times (m \times n))\) where \(k\) is output length

Only calculating the length of LCS

def lcs_calculate(X, Y):
    m = len(X)
    n = len(Y)
    L = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                L[i][j] = 0
            elif X[i - 1] == Y[j - 1]:
                L[i][j] = L[i - 1][j - 1] + 1
            else:
                L[i][j] = max(L[i - 1][j], L[i][j - 1])
    return L[m][n]

lcs_len = lcs_calculate('ABCBDAB', 'BDCAB')
print(f"LCS length is {lcs_len}")

LCS length is 4

• lcs_calculate function is \(O(m \times n)\), but does not return the LCS!

Algorithmic problem solving

Recursion

Implementation

• Problem solved by recursion
• Function calls itself
• Reduces problem size

Performance

• Risk of stack overflow
• Can be inefficient
• Optimized by memoization

Dynamic Programming

Implementation

• Solves complex problems
• Stores subproblem results
• Uses table to store results

Performance

• Efficient for subproblem repeats
• Polynomial time complexity
• Space complexity concerns