目录

1. 递归基础

2. 递归效率

3. 递归实操

3.1 实例1：计算阶乘

3.2 实例2：斐波那契数列

3.3. 实例3：汉诺塔

---

1. 递归基础

所谓递归（recursion），就是函数调用自身的过程；

使用递归必须要有判断和结束条件，并且每次调用都要向着这个结束条件去推进，否则递归过程将永远执行下去直至耗尽所有内存资源；

Python3为防止出现上述永远执行下去的问题，对递归深度做了默认限制，也可以通过 Ctrl + C 让Python强制终止。

示例如下：

def funx(var):
     if var >= 0:
         print(f'当前输入参数={var}')
         var -= 1
         funx(var)  
         
funx(5)
当前输入参数=5
当前输入参数=4
当前输入参数=3
当前输入参数=2
当前输入参数=1
当前输入参数=0

2. 递归效率

递归需要从最底层函数一层层返回，当递归层数较大时，效率很低。

如下示例中对比了迭代和递归两种算法的代码量与执行效率，结果可见递归在数据量较大时效率很低；因此，通常推荐：数据量小时用递归，数据量大时用迭代。

def fiboIter(var):
     if var == 1:
         result = [1]
     elif var > 1:
         result = [1, 1]
         for i in range(2,var):
             result.append(result[i-2]+result[i-1])
     return result
 
def fiboIter2(var):
     if var == 1:
         return [1]
     elif var == 2:
         result = fiboIter2(var-1)
         result.append(1)
         return result
     elif var > 2:
         result = fiboIter2(var-1)
         result.append(result[var-3] + result[var-2])
         return result
 
import timeit
 
#单轮500级数列耗时
starttime = timeit.default_timer()
print("The start time is :",starttime)
fiboIter(500)
print("The time difference is :", timeit.default_timer() - starttime)
 
starttime = timeit.default_timer()
print("The start time is :",starttime)
fiboIter2(500)
print("The time difference is :", timeit.default_timer() - starttime)
 
#100轮100级数列耗时
print('迭代做斐波那契100级数列数列100次生成耗时：',timeit.timeit('fiboIter(100)', setup='from __main__ import fiboIter', number=100))
print('迭代做斐波那契100级数列数列100次生成耗时：',timeit.timeit('fiboIter2(100)', setup='from __main__ import fiboIter2', number=100))
 
 
The start time is : 1.0402109
The time difference is : 8.000000000008001e-05
The start time is : 1.0402999
The time difference is : 0.0003684000000001575
 
迭代做斐波那契100级数列数列100次生成耗时： 0.0010354000000000196
迭代做斐波那契100级数列数列100次生成耗时： 0.0021157000000000536

3. 递归实操

3.1 实例1：计算阶乘

阶乘：

一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!。

即n!=1×2×3×...×(n-1)×n。阶乘亦可以递归方式定义：0!=1，n!=(n-1)!×n。

亦即n!=1×2×3×...×(n-1)×n。阶乘亦可以递归方式定义：0!=1，n!=(n-1)!×n。

迭代实现：

def factorial(var:int) -> int:
     result = 1
     for i in range(1,var+1):
         result *= i
     return result        
 
factorial(10)
3628800

递归实现：

def factorial(var:int) -> int:
     if var == 0:
         return 1
     elif var > 0:
         return var * factorial(var-1)
     
factorial(10)
3628800

3.2 实例2：斐波那契数列

斐波那契数列（Fibonacci sequence）：

又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

迭代实现：

def fiboIter(var):
     if var == 1:
         result = [1]
     elif var > 1:
         result = [1, 1]
         for i in range(2,var):
             result.append(result[i-2]+result[i-1])
     return result
 
fiboIter(10)
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

递归实现：

def fiboIter2(var):
     if var == 1:
         return [1]
     elif var == 2:
         result = fiboIter2(var - 1)
         result.append(1)
         return result
     elif var > 2:
         result = fiboIter2(var - 1)
         result.append(result[var - 3] + result[var - 2])
         return result
 
fiboIter2(10)
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

3.3. 实例3：汉诺塔

汉诺塔规则说明：

递归实现：

def hannuota(layer:int,post1:str,post2:str,post3:str):
    if layer == 1:
        print(f'第{layer}片: {post1} => {post3}')
    elif layer > 1:
        hannuota(layer-1,post1,post3,post2)
        print(f'第{layer}片: {post1} => {post3}')
        hannuota(layer-1,post2,post1,post3)
 
print('3片汉诺塔：')
hannuota(3,'甲','乙','丙')
print('------------------终止------------------')
 
3片汉诺塔：
第1片: 甲 => 丙
第2片: 甲 => 乙
第1片: 丙 => 乙
第3片: 甲 => 丙
第1片: 乙 => 甲
第2片: 乙 => 丙
第1片: 甲 => 丙
------------------终止------------------