普通程序员用迭代，牛逼程序员用递归。# 1. 什么是递归有进有出才叫递归，一定要记得返回！返回！
求x的阶乘：

def fun(x):
 if x == 1:
 return 1
 else:
 return x * fun(x - 1)

2. 斐波那契数列的递归实现

Paste_Image.png

1. 迭代方法：

def fun(n):
    n1 = 1
    n2 = 1
    n3 = 1

    if n < 1:
        return -1

    while n > 2:
        n3 = n1 + n2
        n1 = n2
        n2 = n3
        n -= 1

    return n3

2. 递归方法：

def fun(n):
 if n < 1:
 return -1
 elif n ==1 or n ==2:
 return 1
 else:
 return fun(n - 1) + fun(n - 2)

3. 比较

在本题中，递归写起来固然简单，但是以牺牲效率为代价。当输入为35时，递归的运行时间就会很长，而迭代法立刻就能出来结果。

3.汉诺塔

def fun(n,x,y,z):
    if n == 1:
        print(x,'-->',z)
    else:
        fun(n-1,x,z,y)      #把n-1个从x移到y
        print(x,'-->',z)      #把最下面一个从x移到z
        fun(n-1,y,x,z)      #把n-1个从y移到z

num = int(input('input the number:'))
fun(num,'X','Y','Z')