Tree Recursion Inverse Cascade Tree Recursion 计算斐波那契数列 1 2 3 4 5 6 7 def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) 并不是最好的实现 -> 在遍历的时候会重复计算相同的节点，得想办法存储中间结果 🤔 Counting Partitions 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def count_partitions(n, m): """ >>> count_partitions(6, 4) 9 """ if n == 0: return 1 elif n < 0 or m < 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

Recursion Self-reference 都是返回函数导致的 😋 然后函数再次被call，就形成了自我递归 Recursive Functions 有一个细节，递归调用的frame的parent frame都是global而不是nested 🤔 Mutual Recursion 互相调用 Recursion to Iteration key: figure out what state must be maintained during the while loop Iteration to Recursion Iteration is a special case of recursion 😮

Function Example 1 1 2 3 4 5 def delay(arg): print('delayed') def g(): return arg return g 2 1 2 3 4 5 def pirate(arggg): print('matey') def plunder(): return arggg return plunder 3 horse mask 关键是两条红线 装饰器 本质上是一个HoF