A-10-递归总结与练习

高渐飞

1. #知识点总结
   
2. #(1)递归即函数内部自己调用自己;必须要有正确的返回值；
   
3. #(2)每次递归都需要建栈,弹栈,清理,消耗内存，因此当递归无返回值或返回值错误时，会导致代码无休止的运行直到程序崩溃
   
4. #(3)斐波那契数列，又称黄金分割数列，兔子序列，F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）
   
5. #(4)汉诺塔:假设汉诺塔有x，y，z三根柱子，已知柱子x上有n个盘子，盘子大小各不相同呈金字塔状放置；
   
6. #   要求将n个盘子从柱子x上移到柱子z上，条件是每次只能移到一个盘子，而且必须永远是大盘子在下小盘子在上的移到状态。
   
7. #   将n个盘子从柱子x移到柱子z上，无法直接实现该过程，需借助柱子y；
   
8. #      首先，将柱子x上的n-1个盘子移动到柱子y上；
   
9. #      然后，将柱子x上最后一个盘子移动到柱子z上；
   
10. #      最后，将柱子y上的n-1个盘子移动到柱子z上。
    
11. 
    
12. #练习部分
    
13. #coding: UTF-8
    
14. 
    
15. #1.实现阶乘
    
16. def factorial(n):
    
17.     if n == 1:
    
18.         return 1
    
19.     else:
    
20.         return n * factorial(n-1)
    
21. 
    
22. number = int(input('请输入一个正整数:'))
    
23. result = factorial(number)
    
24. print("%d 的阶乘是:%d" % (number, result))
    
25. 
    
26. 
    
27. #2.用迭代法（循环）实现斐波那契数列，并输出
    
28. def fab(n):
    
29.     n1 = 1
    
30.     n2 = 1   
    
31.     temp="1 1"
    
32.     if n < 1:
    
33.         print('输入有误！')
    
34.         return -1
    
35.     else:
    
36.         print("0-n之间的斐波那契数列为：\n",temp,end=" "),
    
37.         while (n-2) > 0:
    
38.             n3 = n1 + n2
    
39.             n1 = n2
    
40.             n2 = n3
    
41.             n -= 1
    
42.             print(n3,end=" ")      #使用end=" "可以避免换行，end默认为"\n"
    
43.         return n3
    
44.    
    
45. num = int(input("请输入数列的层数："))
    
46. result = fab(num)
    
47. if result != -1:
    
48.         print('\n总共有%d对小兔崽子诞生！' % result)
    
49. 
    
50. 
    
51. #3.用递归法实现斐波那契数列，并输出
    
52. def fab(n):
    
53.     if n < 0:
    
54.         print("输入有误！")
    
55.     elif n ==1 or n==2:
    
56.         return 1
    
57.     else:
    
58.         return fab(n-1) + fab(n-2)
    
59.    
    
60. num = int(input("请输入数列的层数："))
    
61. if num <= 0:
    
62.     print("请输入正整数！")
    
63. else:
    
64.     print("0-n之间的斐波那契数列为:\n",end=' ')
    
65.     for i in range(1,num+1):
    
66.         print(fab(i), end="; ")
    
67. 
    
68. #4.汉诺塔
    
69. def hanoi(n, x, y, z):
    
70.     if n == 1:
    
71.         print(x, ' --> ', z)
    
72.     else:
    
73.         hanoi(n-1, x, z, y)   #将前n-1个盘子从x移动到y上
    
74.         print(x, ' --> ', z ) #将最底下的最后一个盘子从x移动到z上
    
75.         hanoi(n-1, y, x, z)   #将y上的n-1个盘子移动到z上
    
76. 
    
77. n = int(input('请输入汉诺塔的层数:'))
    
78. hanoi(n, 'x', 'y', 'z')
    

复制代码