python复盘：023-024递归：这帮小兔崽子与汉诺塔

慕良

023-024递归：这帮小兔崽子与汉诺塔

斐波那契（Fibonacci）数列的递归实现（分治思想）

例1：兔子的繁衍

月数	1	2	3	4	5	6	7	8	9	10	11	12
数量	1	1	2	3	5	8	13	21	34	55	89	144

求20个月后的兔子数量。
迭代：

1. def fab(n):
   
2.     n1 = n2 = n3 = 1
   
3.     if n < 1:
   
4.         print('输入有误！')
   
5.         return -1
   
6. 
   
7.     while (n-2) > 0:
   
8.         n3 = n2 + n1
   
9.         n1 = n2
   
10.         n2 = n3
    
11.         n -= 1
    
12. 
    
13.     return n3
    
14. 
    
15. result = fab(20)
    
16. if result != -1:
    
17.     print('总共有%d对小兔崽子诞生！' % result)

复制代码

递归：

1. def fab(n):
   
2.     if n < 1:
   
3.         print('输入有误！')
   
4.         return -1
   
5.     if n == 1 or n == 2:
   
6.         return 1
   
7.     else:
   
8.         return fab(n-1) + fab(n-2)
   
9. 
   
10. result = fab(20)
    
11. if result != -1:
    
12.     print('总共有%d对小兔崽子诞生！' % result)
    

复制代码

例2：汉诺塔

1. def hanoi(n,x,y,z):#x,y,z代表3根针
   
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')

复制代码

Sungne_jer

很强