Recursion recursion recursion!
We saw two recursive functions for finding the maximal element in a list. We discussed quicksort. Then we wrote two recursive functions: binom and change. We also discussed memoization and demonstrated it using our recursive implementations for binom and change.
Recursion:
Memoization:
and finally changing your recursive implementation so that it will search for the key in the dictionary before making the recursive calls, and save the key:value pair after obtaining the value for a certain input.
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
Question from an exam:
Implement find_steady, a function that receives a list $L$ of sorted (ascending) unique integers, and returns a value $i \geq 0$ s.t. $L[i] == i$. If there is no such $i$, None is returned. If there is more than one such index, any one of them can be returned.
For example:
find_steady([3, 5, 9, 17]) => None
find_steady([-3, 0, 2, 10]) => 2
def find_steady(lst):
for i in range(len(lst)):
if lst[i] == i:
return i
return None
print(find_steady([3, 5, 9, 17]))
print(find_steady([-3, 0, 2, 10]))
None 2
def find_steady(lst):
n = len(lst)
left = 0
right = n-1
while left <= right:
middle = (right + left) // 2 # middle rounded down
if middle == lst[middle]: # item found
return middle
elif middle < lst[middle]: # item not in top half
right = middle - 1
else: # item not in bottom half
left = middle + 1
return None
print(find_steady([3, 5, 9, 17]))
print(find_steady([-3, 0, 2, 10]))
None 2
What just happened? The crucial point about this algorithm is the following: if $lst[mid] > mid$ then a fixed point cannot exist above $mid$. Why is that?
Assume there exists some $j = mid+k$ for some $k>0$ such that $lst[j] == j$. Note that $lst[mid] \geq mid + 1$. Now, as the elements in $lst$ are unique, we must have $lst[j] == lst[mid + k] \geq mid + k + 1 > j$
A similar argument shows that if $lst[mid] < mid$ then a fixed point cannot exist below $mid$, thus we get the correctness of the algorithm.
# We would like the function to return 3
print(find_steady([-1, 0, 3, 3, 3]))
The maximum is the maximal value between lst[0] and the result of recursively finding the max in lst[1:].
Let $n$ denote the size of lst.
Recursion depth: $O(n)$
Time complexity: $O(n^2)$
def max1(L):
if len(L) == 1:
return L[0]
return max(max1(L[1:]), L[0])
max1([2,5,10,2,100,-10])
100
The maximum is the maximal value between the result of recursively finding the max in lst[:n//2] and the result of recursively finding the max in lst[n//2:], where $n$ denotes the size of lst.
Recursion depth: $O(\log{n})$
Time complexity: $O(n\log{n})$
def max2(L):
if len(L) == 1:
return L[0]
l = max2(L[:len(L)//2])
r = max2(L[len(L)//2:])
return max(l,r)
max2([2,5,10,2,100,-10])
100
Since slicing is a costly action we can do things better. Instead of slicing the list each time we will maintain indices for the "active" part of the list (like we did for binary search) and simply recurse after updating the indices according to the same logic.
We also add envelope functions for a more user-friendly code.
How does time/depth change for each function? The depth is clearly unaffected. Time, however, is much better.
Since we only do $O(1)$ work in the function, the runtime is analogous to computing the size of the tree which is $O(n)$ in both cases.
def max11(L,left,right):
if left == right:
return L[left]
return max(L[left], max11(L, left + 1, right))
def max22(L, left, right):
if left == right:
return L[left]
mid = (left + right) // 2
l = max22(L, left, mid)
r = max22(L, mid + 1, right)
return max(l, r)
def max1_slice(L):
return max11(L, 0, len(L) - 1)
def max2_slice(L):
return max22(L, 0, len(L) - 1)
Quicksort has a very simple recursive logic:
import random
def quicksort(lst):
""" quick sort of lst """
if len(lst) <= 1:
return lst
else:
pivot = random.choice(lst) # select a random element from list
smaller = [elem for elem in lst if elem < pivot]
equal = [elem for elem in lst if elem == pivot]
greater = [elem for elem in lst if elem > pivot]
return quicksort(smaller) + equal + quicksort(greater) #two recursive calls
def det_quicksort(lst):
""" sort using deterministic pivot selection """
if len(lst) <= 1:
return lst
else:
pivot = lst[0] # select first element from list
smaller = [elem for elem in lst if elem < pivot]
equal = [elem for elem in lst if elem == pivot]
greater = [elem for elem in lst if elem > pivot]
return det_quicksort(smaller) + equal + det_quicksort(greater) #two recursive calls
The worst case and best case analyses were discussed in class. It is interesting to note that:
The subset sum problem is described as follows: given a list of integers $L$ and a value $s \in \mathbb{Z}$, is there a subset $S \subseteq L$ such that: $$\sum_{x \in S} x = s$$ If such an $S$ exists we return True, otherwise False.
Examples:
The base cases are pretty straight-forward:
What about the recursive call? Well, if $s \neq 0, L \neq []$ then the following holds:
So what do we do? We recursively check if either $L[1:], s - L[0]$ or $L[1:], s$ can be solved, and we only return False if both fail.
Note that instead of using slicing (e.g. $L[1:]$), we pass an index that indicates our iteration along the list.
Let's code:
def subset_sum(L, s, i=0):
# Base cases
if s==0:
return True
if i==len(L):
return False
# Check both cases
with_first = subset_sum(L, s-L[i], i+1)
without_first = subset_sum(L, s, i+1)
# If any of the above succeeds we return True, else False
return with_first or without_first
# Sanity checks
L1 = [4, -7, 12, 5, 1]
L2 = [1, 2, 4, 8, 16]
s1 = 6
s2 = 32
print(subset_sum(L1, s1, 0))
print(subset_sum(L2, s2, 0))
True False
What is the running time of the code in relation to the size of the list $|L| = n$?
The recurrence relation is $T(n) = 2 \cdot T(n-1) + O(1)$, which yields $T(n) = 2^n$ (Just like the Hanoi towers solution).
In class we've seen how to transform recursive algorithms which run in exponential time into iterative algorithms that run in linear time (i.e. - Fibonacci, factorial).
Can you think of a better solution? One that works in time $O(n^2)$? How about $O(n^{100})$?
Incredibly, there is a wide held belief that this problem yields no algorithm which runs in time $\mathrm{poly}(n)$. More on that later (much later, say, next year in computational models)...
A bus driver needs to give an exact change and she has coins of limited types. She has infinite coins of each type. Given the amount of change ($amount$) and the coin types (the list $coins$), how many ways are there?
def change(amount, coins):
if amount == 0:
return 1
elif amount < 0 or coins == []:
return 0
return change(amount, coins[:-1]) +\
change(amount - coins[-1], coins)
change(5, [1,2,3])
5
Why is it counting unique solution? For example, why is [2,2,1] counted once and not [1,2,2]?
Consider the case where $amount = n^2, coins = [1,2,\ldots, n]$. When we call $change(amount, coins)$ the first level of the recursion calls $change([1,\ldots, n-1], n^2)$ and $change([1,\ldots, n], n^2 - n)$. This means that the list size in the recusrive calls is at least $n-1$ and $amount \geq n^2 -n$.
One can show (using induction) that in the first $k \leq n$ levels of recursion the list size is at least $n - k$ and $amount \geq n^2-n k$, thus there are two recursive calls at each of these layers.
This gives a running time of at least $2^n$ by the same argument as that we applied in the subset sum problem.
It is interesting to note that while the two problem share some similarities, one major difference is that in the subset sum problem we are asking whether a solution exists while in the change problem we are trying to count the number of valid solutions to a problem.
This is a recurring theme in CS that we will encounter many times in the future.