《零基础入门学习python》第二十三~四讲笔记：递归实例

bozhen

斐波那契数列（Fibonacci）是递归算法的来源

递归可以理解为分治思想，把一个复杂的问题分解成一个小问题，然后用代码来实现这个小问题

我们可以用数学函数来定义：
                  1，当n=1
F(n) =        1，当n=2
                  F(n-1)+F(n-2)，当n>2
课间练习：假设我们需要求出经历了20个月后，总共有多少对小兔崽子？（迭代vs 递归）

我的答案：

list1 = [1,1,2]
for i in range(2,21):
    list1[i] = list1[i-1] + list1[i-2]
    list1.append(list1[i])
print(list1[19])   # 求第20个月兔子数量

  我这个方法有点投机取巧的感觉


参考答案迭代：

def fab(n):
    n1 = 1
    n2 = 1
    n3 = 1

    if n < 1:
        print('输入有误！')
        return -1

    while (n-2) > 0:     # 从n=3开始，符合F(n)=F(n-1)+F(n-2)
        n3 = n2 + n1
        n1 = n2
        n2 = n3
        n -= 1     # n 依次减1是为了依次计算n-1   n- 2  n-3 ...的值

    return n3

result = fab(45)
if result != -1:
    print('总共有%d对小兔崽子诞生！' % result)

参考答案递归：

def fab(n):
    if n < 1:
        print('输入有误！')
        return -1

    if n == 1 or n == 2:
        return 1
    else:
        return fab(n-1) + fab(n-2)   # 简单直接的写出了数的规律

result = fab(35)
if result != -1:
    print('总共有%d对小兔崽子诞生！' % result)

迭代和递归，就此例来说，随着月数更大，递归所消耗的时间也更久。不如用迭代



递归实例二：汉诺塔

def hanoi(n, x, y, z):
    if n == 1:
        print(x, ' --> ', z)
    else:
        hanoi(n-1, x, z, y) # 将前n-1个盘子从x移动到y上
        print(x, ' --> ', z) # 将最底下的最后一个盘子从x移动到z上
        hanoi(n-1, y, x, z) # 将y上的n-1个盘子移动到z上

n = int(input('请输入汉诺塔的层数：'))
hanoi(n, 'X', 'Y', 'Z')
此例最好的办法就是用递归实现