CS61A lect9 tree recusion

• Each cascade frame is from a different call to cascade.
• Until the Return value appears, that call has not completed.
• Any statement can appear before or after the recursive call.
Write a function that prints an inverse cascade:
1
12
123
1234
123
12
1

1
2
3
4
5
6
7
8
9
10
def inverse_cascade(n): 
    grow(n) 
    print(n) 
    shrink(n)
def f_then_g(f, g, n): 
    if n: 
        f(n) 
        g(n)
grow = lambda n: f_then_g(grow, print, n//10) 
shrink = lambda n: f_then_g(print, shrink, n//10)

tree recursive

The computational process of fib evolves into a tree structure
汉诺塔：

1
2
3
4
5
6
7
8
9
10
11
def move_disk(disk_number, from_peg, to_peg):
 print("Move disk " + str(disk_number) + " from peg " \
 + str(from_peg) + " to peg " + str(to_peg) + ".")
def solve_hanoi(n, start_peg, end_peg):
 if n == 1:
 move_disk(n, start_peg, end_peg)
 else: 
 spare_peg = 6 - start_peg - end_peg 
 solve_hanoi(n - 1, start_peg, spare_peg) 
 move_disk(n, start_peg, end_peg)
 solve_hanoi(n - 1, spare_peg, end_peg)