23 递推算法

递推和递归是兄弟吗？

大纲

• 什么是递推

• 计算青蛙上台阶问题

• 汉诺塔问题

• 猴子吃桃问题

什么是递推算法

我们先用一个例子来对比一下递归和递推的联系和区别。

# 递归
def fibonacc_1(n):
    if n<= 2:
        return 1     # 停止条件
    else:
        return fibonacci(n-1)+fibonacci(n-2)  # 分拆到子问题

fibonacc_1(8)

21

# 递推
def fibonacc_2(n):
    if n in (1,2):  # 初始情况的返回值
        return 1
    a=b=1
    for i in range(1,n):
        new = a+b   # 递推式，后一个数字等于前面两个数字之和
        a=b
        b=new
    return a

fibonacc_2(8)

21

# 递推，不需要new变量
def fibonacc_2(n):
    if n in (1,2):
        return 1
    a=b=1
    for i in range(1,n):
        a, b= b, a + b
    return a

fibonacc_2(8)

21

• 递推的结构为线型，人的简单逻辑推理（一件事想到另一件事）就是递推的模型。

• 关于递归，有个经典的例子: 我梦见自己在做梦。递归的特点是，自我嵌套的稍复杂结构。

从上例可以看到，递归算法可以用一个递推来代替。

让我们把上面算法做一个修改，把之前所有结果都存下来。

def fibonacci_list(n):
    li =[]
    for i in range(n):
        if i ==0 or i ==1:#第1,2项 都为1
            li.append(1)
        else:
            li.append(li[i-2]+li[i-1])#从第3项开始每项值为前两项值之和
    return li

fibonacci_list(8)

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

上台阶问题

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

# 递归算法
def taijie_1(n):
    if n<= 2:
        return n     # 停止条件
    elif n==3:
        return 4
    else:
        return taijie_1(n-1)+taijie_1(n-2)+taijie_1(n-3)  # 分拆

taijie_1(8)

81

# 递推算法
def taijie_2(n):
    li = [1,2,4]
    for i in range(3,n):
        temp = li[i-1]+li[i-2]+li[i-3] # 走到第4级台阶分三种情况，最后第1级台阶一步上来，从第2级一步上来，从第3级一步上来。
        li.append(temp)
    return li[-1]

taijie_2(8)

81

汉诺塔问题

上次课的汉诺塔问题中，我们用递归计算了不同情况下如何移动圆盘，这次我们用递推算法来计算，移动n个圆盘，需要移动多少次？

记得把大象送进冰箱需要几步吗？三大步骤，打开门，移动圆盘，关上门。打开门实际是需要移动n-1个圆盘，送上门也是要移动n-1个圆盘，所以F(n)=F(n-1)+1+F(n-1)

def hanoi_cnt(n):
    li = [1]   # 如果只有一个圆盘，那么只需要移动一次
    for i in range(1,n):
        temp = 2*li[i-1]+1 # 三大步骤
        li.append(temp)
    return li[-1]

hanoi_cnt(3)

7

猴子吃桃问题

猴子第一天摘下若干个桃，当即吃一半，又多吃一个。第二天早上又将剩下的一半吃掉一半，又多了吃一个。以后每天早上都吃了前天剩下的一半零一个，到第10天早上只剩下最后一个桃。问第一天摘了几个桃。

# 递推
def chitao_1(n):
    li = [1]   # 最后一天只有一个
    for i in range(1,n):
        temp = 2*(li[i-1]+1) # 一天前的个数是2*x+2
        li.append(temp)
    return li[-1]

chitao_1(10)

1534

# 递归
def chitao_2(n):
    if n==1:
        return 1 # 最后一天只有一个
    else:
        return 2*chitao_2(n-1)+2  #第N天的个数是N-1天个数是2*x+2

chitao_2(10)

1534