递归定义

大家通常说普通程序员用迭代，天才程序员用递归。python3出于“善意的保护”，对递归深度默认是有限的，一般在写网络爬虫上会将递归深度加大。

import sys
sys.setrecursionlimit(10000) 设置递归深度为1万层

有名的递归案例

（1）汉诺塔游戏
（2）树结构的定义
（3）谢尔宾斯基三角形
（4）女神自拍

递归案例 1-求阶乘

写一个求阶乘的递归函数

至于什么是阶乘我相信大家应该都明白的，这里我就不做过多解释了，在此之间我们先尝试用非递归的方法来实现阶乘。

非递归方法实现阶乘

def f(n):
result=n
for i in range(1,n):
result*=i
return result
x=int(input(“请输入一个整数：”))
y=f(x)
print(y)

程序输出：
请输入一个整数：5
120

普通的迭代法实现阶乘大家应该都会写，那么我们在尝试一下递归的版本

def Recursion(n):
if n==1:
return n
else:
return n*Recursion(n-1)
x=int(input(“请输入一个整数：”))
y=Recursion(x)
print(y)

程序输出：
请输入一个整数：5
120
毫无疑问使用递归方法比迭代法更加的简洁，麻雀虽小，五脏俱全，这个简单的阶乘递归满足了递归的最基本的两个条件
（1）调用函数本身
（2）设置了正确的返回条件

详细解剖每一步骤：
  Recursion(5)=5*Recursion(4)  
    Recursion(4)=4*Recursion(3)
        Recursion(3)=3*Recursion(2)  
            Recursion(2)=2*Recursion(1)

这是阶乘递归的整个过程，然后在递归到Recursion(1)时层层返回最终得出结果。

“天才程序员用递归”，”普通程序员用迭代“这句话并不是绝对的，毕竟递归的实现是自己调用自己，每次函数的调用都需要进行压栈、弹栈、保存和恢复寄存器的栈的操作，所以会浪费大量的时间和空间，一旦忘记设置返回条件，或者返回条件设置错误，那么递归代码将会成为一个永远执行的无底洞。

递归案例 2-斐波那契数列

斐波那契数列发明者是意大利数学家列昂纳多 斐波那契发明的。当年是由兔子交配的故事引起的：假如说
兔子在出生两个月后，就有了繁殖能力，此后这对兔子在接下来的两个月都能生出一对可爱的小兔子。假设
所有兔子都不会老去，就这么一直折腾下去，那么一年后会繁殖多少个小兔子。
假设20个月总共呦多少对？

remote_addr

首先迭代方法：

def fab(n):
a1=1
a2=1
a3=1
if n<1:
print(“输入错误”)
return -1

while(n-2)>0:
a3=a1+a2
a1=a2
a2=a3
n-=1
return a3

result=fab(12)
if result!=-1:
print(“总共有小兔子:”,result)

递归法：
def fab(n):
a1=1
a2=1
a3=1
if n<1:
print(“输入错误”)
return 1
if n==1 or n==2:
return 1
else:
return fab(n-1)+fab(n-2)
result=fab(20)
if result!=-1:
print(“总共有小兔子:”,result)

总结：如果将n的值改成100或者更大，你会发现使用迭代比递归的效率更高，因此在选择方式时如果数
值量大尽量不要选择递归。如果选择了递归除非你的CPU性能高。

递归案例 3 汉诺塔

汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根
金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开
始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能
移动一个圆盘。

def hanoi(n,x,y,z):
if n==1:
print(x,’—–>’,z)
else:
hanoi(n-1,x,z,y)
print(x,’—–>’,z)
hanoi(n-1,y,x,z)
n=int(input(“请输入汉诺塔层数”))
hanoi(n,’X’,’Y’,’Z’)

输出：
请输入汉诺塔层数3
X —–> Z
X —–> Y
Z —–> Y
X —–> Z
Y —–> X
Y —–> Z
X —–> Z

说明：如果只有一层，直接从X移动到Z,
如果有两层，则将第一层移动到Y轴上，再将第二层移动到Z轴上，最后再将Y轴上的移动到Z轴上
如果超过n层，将前n-1个盘子看作一个整体，移动到Y轴上，再将第X轴上的移动到Z轴上，最后将第Y轴上移动到Z轴上。
总结：
首先借助Z轴将前n-1层移动到Y轴上，再将X轴上第n层移动Z轴上。
其次借助Z轴将Y轴上的前n-1层移动到X轴上，再将Y轴上的第n层移动到Z轴上。依此循环往复即可

赏
评 论