【CS61A】CS61A——Tree Recursion

Tree Recursion

Order of Recursive Calls

e.g.1:Cascade

1
2
3
4
5
6
7

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

结果为

1
2
3
4
5
6
7
8
9
10

>>> cascade(12345)
12345
1234
123
12
1
12
123
1234
12345

首先一直调用cascade到底，返回None，从调用入口出来后继续执行cascade下面的语句

cascade

还可以缩短为以下

1
2
3
4
5

def cascade_short(n):
    print(n)
    if n>10:
        cascade(n//10)
        print(n)

e.g.2:Inverse Cascade

1
2
3
4
5
6
7
8
9
10
11
12

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)

grow先进行处理，每次将数字缩短一节，到达递归底部后退出时便是从小到大依次输出

shrink先打印出来当前n，然后将数字缩短一节，这样递归过程便实现了从大到小依次输出

Tree Recursion

当递归函数对自身调用超过一次时，发生树形递归，产生树状过程

e.g.1 斐波那契数列

树形斐波那契

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)

e.g.2 计算分区

将正整数n分为大小不超过m的分区的方式有多少种，即n能以多少种方式表示为递增的不超过m部分之和

e.g. count_partitions(6,4)

有以下可能：

\(2+4=6\)

\(1+1+4=6\)

\(3+3=6\)

\(1+2+3=6\)

\(1+1+1+3=6\)

……

分为两种情况考虑：

• 至少分一个4
• 不分4

这样我们可以把递归问题拆分为两个小问题，将两种情况相加

• count_partitions(2,4)

• count_partitions(6,3)

  以此类推，count_partitions(6,3)按同样方式考虑，分3与不分3，直到递归底部

1
2
3
4
5
6
7
8
9
10
11

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