Tree Recursion
Recursion Review
- How to Know That a Recursive Implementation is Correct:
- Tracing: Diagram the whole computational process (only feasilbe for small examples/cases)
- Induction: Check f(0), then check that f(n) is correct as long as f(n-1) .. f(0) are.
- Abstraction: Assume f is correct (on smaller examples), then use it to implement f.
- We can also trace out program to see what functions are called and what their respective return value is.
1
2
3
4
5
6
7
8
9
10
from ucb import trace
@trace
def fact(n):
if n == 0:
return 1
else:
return n * fact(n-1)
fact(3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
fact(3):
fact(2):
fact(1):
fact(0):
fact(0) -> 1
fact(1) -> 1
fact(2) -> 2
fact(3) -> 6
6
- Recursion is reducing down a multi-step problem down to two steps: Our current step, and then followed by trusting that the rest of the process works.
1
2
3
4
5
6
7
8
9
10
11
12
13
def streak(n):
"""Return True if all the digits in positive integer n are the same.
>>> streak(22222)
True
>>> streak(4)
True
>>> streak(2222322)
False
"""
return (n>=0 and n <=9) or (n>9 and (n%10 == n//10%10) and streak(n//10))
streak(2)
1
True
Mutual Recursion
- Two functions f and g are mutually recursive if g calls g and g calls f.
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
def unique_prime_factors(n):
"""Return the number of unique prime factors of n.
>>> unique_prime+factors(51)
2
>>> unique_prime_factors(27)
1
>>> unique_prime_factors(120)
2
"""
k = smallest_factor(n)
print(k)
def no_k(n):
"""Return the number of unique prime factors of n other than k"""
if n == 1:
return 0
elif n % k != 0:
return unique_prime_factors(n) # Recalculate k and solve. Every time we hit a different prime, call this and add 1
else:
return no_k(n//k) # See if k even divides again
return 1+no_k(n)
def smallest_factor(n):
factor = 2
while n % factor != 0:
factor+=1
return factor
unique_prime_factors(12309123)
1
2
3
4
5
6
7
8
9
10
3
37
173
641
4
Tree Recursion
Counting Partitions
The number of partitions of a positive integer n, using parts up to size m, is the number of ways in which n can be expressed as the sum of positive integer parts up to m.
1
2
3
4
5
6
7
8
9
10
11
12
13
def count_partitions(n, m):
if (n == 0): # Happens when n == m, count partitions is called when n = 0, which should return a total of 1 ways of getting the number
return 1
elif n < 0: # if m is bigger than n, it is impossible to count to n with m
return 0
elif m == 0: # How many ways to get to n with 0 numbers??? 0!!!!
return 0
else:
with_m = count_partitions(n-m, m)
without_m = count_partitions(n, m-1)
return with_m + without_m
count_partitions(6,4)
1
9
Spring 2023 Midterm 2 Question 5
- Definition. When parking vehicles in a row, a motercycle takes up 1 parking spot and a car takes up 2 adjacent parking spots. A string of length n can represent n adjacent parking spots using % for a motocycle, <> for a car, and . for an enpty spot.
Implement count_park, which returns the number of ways that vehicles can be parked in n adjacent parking spots for positive integer n. Some or all spots can be empty.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def count_park(n):
"""Count the ways to park cars and motocycles in n adjacent spots.
>>> count_park(1)
2
>>> count_park(2)
"""
if n < 0:
return 0
elif n == 0:
return 1
else:
return 2*count_park(n-1) + 1*count_park(n-2)
count_park(4)
1
29