Python[CS61A] Tree Recursion: Videos 정리

Order of Recursive Calls 영상

 

def cascade(n):
    if n < 10:
        print(n)
    else:
        print(n)
        cascade(n//10)
        print(n)

 

 

---

Example: Inverse Cascade 영상

grow함수랑 shrink함수에 대한 코드를 작성해보았음.

grow = lambda n: f_then_g(grow, print, n // 10)
shrink = lambda n: f_then_g(print, shrink, n // 10)

---

Tree Recursion 영상

Tree recursion: Whenever executing the body of a recursive function makes more than one call to that function.

from ucb import trace

@trace #decorator
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-2) + fib(n-1)

@trace: Before the function that you want to define and it changes the behavior of the function to print out when it gets called and when it returns. (Decorator의 일종)

---

Example: 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 in increasing order.

count_partitions(6, 4)

2 + 4 = 6
1 + 1 + 4 = 6
3 + 3 = 6
1 + 2 + 3 = 6
1 + 1 + 1 + 3 = 6
2 + 2 + 2 = 6
1 + 1 + 2 + 2 = 6
1 + 1 + 1 + 1 + 2 = 6
1 + 1 + 1 + 1 + 1 + 1 = 6

 

• Use at least one 4
• Don't use any 4

로직 반복

def count_partitions(n, m):
    if n == 0:
        return 1
    elif n < 0:
        return 0
    elif m == 0:
        return 0
    else:
        with_m = count_partitions(n-m, m)
        without_m = count_partitions(n, m-1)
        return with_m + without_m
    
result = count_partitions(5, 3)

---