23~24 递归

23 递归：这帮小兔崽子

---

---

一、斐波那契数列的迭代实现

---

 （一）迭代方法

def F(n):
    n1 = 1
    n2 = 2
    n3 = 3

    if n < 1:
        print('输入有误！')
        return -1
    
    while (n-2) > 0:
        n3 = n2 + n1  #第三个月n3==1+1==2
        n1 = n2   #然后n1向后移一个，变成原来n2的数
        n2 = n3   #然后n2向后移一个，变成原来n3的数
        #新的n3其实是n4==n2（新的n1）+n3（新的n2）
        n -= 1   #n就可以减去一次。然后还需要循环（n-1）次

    #等到n减为0时，可以推出循环，返回return：
        return n3

'''举例'''
result = F(20)
if result != -1:
    print('总共有%d对小兔崽子诞生'% result)

 （二）递归方法

 【自己写滴！！】

def F(n):
    if n == 1 or n == 2:
        return 1
    else:
        return F(n-1) + F(n-2)

【标准答案】 

def F(n):
    if n < 1:
        print('输入有误！')
        return -1

    
    if n == 1 or n == 2:
        return 1
    else:
        return F(n-1) + F(n-2)

'''举例'''
result = F(20)
if result != -1:
    print('总共有%d对小兔崽子诞生'% result)

【笔记】
        递归的思想：分治思想

---

【存在问题】
        当把【n】改为【35】、【40】（很大）的时候，递归方法需要等一会才能出来结果（可以自己动手试一试）；但是迭代方法立刻就出来了。
        所以不支持所有情况都使用递归方法！！

24 递归：汉诺塔游戏

---

---

 

def hanoi(n, x, y, z):  #定义汉诺塔的三根针：x针，y针，z针
    if n == 1:
        print(x, '--->', z)
        return -1
    else:
        hanoi(n-1, x, z, y) # 将前(n-1)个盘子从x移动到y上
                            # 可以把中间的【z】当作借助柱（下同）
        print(x, '--->', z) # 将最底下的最大的盘子从x移动到z上
        hanoi(n-1, y, x, z) # 将y上的(n-1)个盘子从y移动到z上
                            # 可以把中间的【x】当作借助柱（同上）

'''运用'''
n = int(input('请输入汉诺塔的层数：'))
hanoi(n, 'x', 'y', 'z')