章节五：递归

向西而笑

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

def jc (n):
    if n ==1:
        return 1
    else:
        return n * jc(n-1)

num = int(input('请输入一个数：'))
result= jc(num)
print('%d的阶乘是%d' %(num,result))

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


迭代代码如下：

# 迭代实现斐波那契数列函数
def fib (n):
    x = 0
    y = 1
    while n:
        x,y=y,x+y
        n -= 1
    return x

递归代码如下：

# 递归实现斐波那契数列函数
def fib (n):
    if n == 1 or n==2 :
        return 1
    else:
        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柱子上。  依次将问题分解下去。
代码如下：

def hnt(n,x,y,z):
    if n == 1:
        print(x, '-->' ,z)
    else:
        hnt(n-1,x,z,y)
        print(x, '-->' ,z)
        hnt(n-1,y,x,z)
n = int(input('请输入层数:'))
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上，递归结束。

hnt(n-1,x,z,y)  #上面的盘子移动到中介柱子上
print(x, '-->', z)#把这个过程打印出来
hnt(n-1,y,x,z)#假如只有两层，这个不执行。如果不是则继续分下去运行上面两行代码

#最后只剩一个盘子了，n==1，print最后一步
print(x, --> ,z)

向西而笑

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

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