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

bozhen

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

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

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

我的答案：

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

复制代码

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


参考答案迭代：

1. def fab(n):
   
2.     n1 = 1
   
3.     n2 = 1
   
4.     n3 = 1
   
5. 
   
6.     if n < 1:
   
7.         print('输入有误！')
   
8.         return -1
   
9. 
   
10.     while (n-2) > 0:     # 从n=3开始，符合F(n)=F(n-1)+F(n-2)
    
11.         n3 = n2 + n1
    
12.         n1 = n2
    
13.         n2 = n3
    
14.         n -= 1     # n 依次减1是为了依次计算n-1   n- 2  n-3 ...的值
    
15. 
    
16.     return n3
    
17. 
    
18. result = fab(45)
    
19. if result != -1:
    
20.     print('总共有%d对小兔崽子诞生！' % result)
    
21. 
    

复制代码

参考答案递归：

1. def fab(n):
   
2.     if n < 1:
   
3.         print('输入有误！')
   
4.         return -1
   
5. 
   
6.     if n == 1 or n == 2:
   
7.         return 1
   
8.     else:
   
9.         return fab(n-1) + fab(n-2)   # 简单直接的写出了数的规律
   
10. 
    
11. result = fab(35)
    
12. if result != -1:
    
13.     print('总共有%d对小兔崽子诞生！' % result)
    

复制代码

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



递归实例二：汉诺塔

1. def hanoi(n, x, y, z):
   
2.     if n == 1:
   
3.         print(x, ' --> ', z)
   
4.     else:
   
5.         hanoi(n-1, x, z, y) # 将前n-1个盘子从x移动到y上
   
6.         print(x, ' --> ', z) # 将最底下的最后一个盘子从x移动到z上
   
7.         hanoi(n-1, y, x, z) # 将y上的n-1个盘子移动到z上
   
8. 
   
9. n = int(input('请输入汉诺塔的层数：'))
   
10. hanoi(n, 'X', 'Y', 'Z')
    
11. 此例最好的办法就是用递归实现

复制代码