章节五：递归

向西而笑

程序调用自身的技巧叫做递归
例子：求阶乘

1. def jc (n):
   
2.     if n ==1:
   
3.         return 1
   
4.     else:
   
5.         return n * jc(n-1)
   
6. 
   
7. num = int(input('请输入一个数：'))
   
8. result= jc(num)
   
9. print('%d的阶乘是%d' %(num,result))

复制代码

斐波那契数列
兔子繁殖问题：第一个月有一对兔子，第二个月还是只有一对兔子，第三个月开始兔子对数是前一个月加上前两个月对数的和，问20个月后有多少对兔子。


迭代代码如下：

1. # 迭代实现斐波那契数列函数
   
2. def fib (n):
   
3.     x = 0
   
4.     y = 1
   
5.     while n:
   
6.         x,y=y,x+y
   
7.         n -= 1
   
8.     return x

复制代码

递归代码如下：

1. 
   
2. # 递归实现斐波那契数列函数
   
3. def fib (n):
   
4.     if n == 1 or n==2 :
   
5.         return 1
   
6.     else:
   
7.         return fib(n-2) +fib(n-1)

复制代码

运用递归实现汉诺塔游戏
汉诺塔游戏的规则如下：
有三根柱子：x、y、z，开始x柱子上有n个盘子，盘子大小不同，小的在大的上面。要求按同样顺序将x柱子上的盘子移动到z柱子上，每次只能转移一个，且小的不能在大的下面。
思路：将这个问题可以分解成三个问题：1、将x柱子上的n-1个盘子移动到y柱子上。2、将x柱子上最后一个盘子移动到z柱子上。 3、将y柱子上n-1个盘子移动到z柱子上。  依次将问题分解下去。
代码如下：

1. def hnt(n,x,y,z):
   
2.     if n == 1:
   
3.         print(x, '-->' ,z)
   
4.     else:
   
5.         hnt(n-1,x,z,y)
   
6.         print(x, '-->' ,z)
   
7.         hnt(n-1,y,x,z)
   
8. n = int(input('请输入层数:'))
   
9. hnt(n,'X','Y','Z')

复制代码

这个汉诺塔递归代码真的废了我好多时间区理解。
总结

递归思想就是把一个复杂的问题分成比较简单的问题解决，如果还解决不了就继续分下去直到解决。但是容易出错而且效率也低,非常消耗时间和空间，一不小心就会无限循环下去，谨慎使用。

新手·ing

能不能解释下汉诺塔代码~

向西而笑

新手·ing 发表于 2017-7-22 17:38
能不能解释下汉诺塔代码~

先把整个分成两个部分：顶上的n-1盘子和最底下的盘子。
n-1先要移动到中介的y柱子上，就是hut(n-1,x,z,y),然后print()出来
然后把y柱子上看成初始状态下的x柱子继续移动上面的n-1盘子到中介柱子上，一直这样分解下去，
知道x柱子上剩最后一个，移动到z上，递归结束。

1. hnt(n-1,x,z,y)  #上面的盘子移动到中介柱子上
   
2. print(x, '-->', z)#把这个过程打印出来
   
3. hnt(n-1,y,x,z)#假如只有两层，这个不执行。如果不是则继续分下去运行上面两行代码
   
4. 
   
5. #最后只剩一个盘子了，n==1，print最后一步
   
6. print(x, --> ,z)
   
7. 
   
8. 
   

复制代码

向西而笑

新手·ing 发表于 2017-7-22 17:38
能不能解释下汉诺塔代码~

理解这代码不能看作电脑在玩汉诺塔游戏