20 递归算法实操

奇妙的想法更需要反复练习

大纲

• 练习：斐波那契数列

• 练习：青蛙跳台阶

• 练习：兔子繁殖问题

练习：斐波那契数列

斐波那契数列是指这项数字等于前面两项数字之和的序列

1、1、2、3、5、8、13、21、34、……

让我们用递归算法来实现一下，如何计算出数列的第N项

def fibonacci(n):
    if n<= 2:
        return 1     # 停止条件
    else:
        return fibonacci(n-1)+fibonacci(n-2)  # 分拆

fibonacci(8)

21

for x in range(1,10):
    print(fibonacci(x))

1
1
2
3
5
8
13
21
34

如果要算出所有的数字，可以直接用列表解析。

[fibonacci(x) for x in range(1,10)]

[1, 1, 2, 3, 5, 8, 13, 21, 34]

练习：青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

每次跳的时候，小青蛙可以跳一个台阶，也可以跳两个台阶，也就是说，每次跳的时候，小青蛙有两种跳法。第一种跳法：第一次我跳了一个台阶，那么还剩下n-1个台阶还没跳，剩下的n-1个台阶的跳法有f(n-1)种。第二种跳法：第一次跳了两个台阶，那么还剩下n-2个台阶还没，剩下的n-2个台阶的跳法有f(n-2)种。所以，小青蛙的全部跳法就是这两种跳法之和了，即 f(n) = f(n-1) + f(n-2)。

def taijie(n):
    if n<= 2:
        return n     # 停止条件
    else:
        return taijie(n-1)+taijie(n-2)  # 分拆

taijie(8)

34

练习：兔子繁殖问题

有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？

第n月的时候的兔子包括两种，一种是当前新生的兔子，另一种是以前的老兔子，新兔子的数量等于两个月前的老兔子数量，以前的老兔子数量就是一个月前的老兔子数量，所以F(n) = F(n-1)+F(n-2)

def tuzi(n):
    if n<= 2:
        return 2     # 停止条件
    else:
        return tuzi(n-1)+tuzi(n-2)  # 分拆

tuzi(8)

42

[tuzi(x) for x in range(1,12)]

[2, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178]

假设兔子寿命是8个月，1月出生的兔子到了9月就会死亡，那么上面这个问题里，到了两年后兔子总数会是多少？

第n月的时候的兔子数量除了新兔子和老兔子，还要考虑8个月前的兔子，所以F(n) = F(n-1)+F(n-2)-F(n-8)

def tuzi(n):
    if n<= 2:
        return 2     # 停止条件
    else:
        if n<=8:
            return tuzi(n-1)+tuzi(n-2) # 分拆
        else:
            return tuzi(n-1)+tuzi(n-2)-tuzi(n-8)

[tuzi(x) for x in range(1,12)]

[2, 2, 4, 6, 10, 16, 26, 42, 66, 106, 168]

tuzi(24)

70040