【重修Python】谈一谈递归

封面

前言

在正式开始前，先来回忆一个问题。

假定一对刚出生的小兔一个月后就能长成大兔，再过一个月便能剩下一对小兔，并且每个月都生一对小兔。一年以内没有发生死亡。那么有一对刚出生的兔子开始，12个月后会有多少对兔子呢？

以上来自小学六年级下册的数学课本。当时老师讲解的方案是找规律。

这也非常著名的斐波那契数列！

直到后来，我们使用数学公式来表达这个问题的解。

那现在我们对于这个问题，可以使用自己调自己的函数来解决，如下：

# 斐波那契数列
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

如上，就是本文所要谈的话题，专业名词称为递归。

什么是递归？

光看上面的公式，不是很直观。

而放在数学学科中，常常以数形结合的方式，所以本文也效仿一下。

斐波那契示例图

当我们想知道第n（n>2）个月兔子的数量，就可以向下一层一层的向下去问，这个过程就叫做"递"。一直"递"到无法再"递"的节点，然后再将结果一层一层汇总，向上“归”。那么我们说这个过程，可以称之为递归。

如何写递归

再回到上文案例中，把问题形式和求解过程抽象出来

• 问题形式：可以拆解成小问题，并且形式与原问题一致。
• 求解过程：找到那个无需计算的最小问题，作为递归的终止条件，再汇总多个这样的解，得到原问题的解。

理论存在，那么来秒一道求阶乘问题！

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)
print(factorial(5)) 
#  计算过程 5 * 4 * 3 * 2 * 1 = 120

如何写好递归

谜底就在谜面上，其实只要写出递归，就已经写好了，因为你已经直到了如何拆分这个问题为递归模式。但是还没有完，往往我们递归的问题出在后面的异常超时等问题。

Stack overflow

①当我们终止条件不正确的时候，见下图

错误案例-1

如果上述阶乘的案例中，不小心将-错写成了+。那么势必会进入无法终止的条件，导致报错。

②除此之外，还有一种情况，即使你写好了终止条件，但是因为n过大，导致循环次数过多，也会出现上述的情况，或者计算时间很长。拿常规的斐波那契写法举例（见前言中的案例），如果n设置为100，那么你将会看到控制台像卡住一样得不到结果（你需要进行大约 1.67 亿次递归调用）。

解决方案

对于①的情况，往往需要你重新设计算法，或debug检查变量的值（debug的方法见本文结尾）。

而情况②，则需要算法中常用的一种方法：剪枝。

仔细分析此案例中的递归，当n为5时，我们大概需要1次重复运算，就是f(3)；而当n到6时，重复计算的次数来到了5次。

所以，如果我们将计算结果缓存起来，每次先去缓存里看有没有计算过，这样，我们像减去“递归”树的枝叶一样，节省了资源。具体代码如下：

from functools import lru_cache
import time

@lru_cache(maxsize=None)
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# 测试 运行时间
start = time.time()
print(fibonacci(100))  # 输出: 354224848179261915075
end = time.time()
print(end - start)

在这个例子中，我们使用了 functools 模块中的 lru_cache 装饰器来为 fibonacci 函数提供缓存。maxsize=None 表示缓存的大小没有限制。这将缓存所有已计算的斐波那契数，从而减少时间复杂度。

请注意，这种方法在计算大的斐波那契数时可能会消耗大量内存。你可以通过设置 maxsize 参数来限制缓存的大小。

递归的应用

递归只能来解数学题？上面两个案例中，我都是用来解决数学中的问题。不过只是为了省去其他学习门槛，接下来，看一看编程中实际的应用。

树的遍历

完整代码：

# 定义二叉树
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# 测试数据
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# 先序遍历
def preOrder(root):
    if root is None:
        return
    print(root.data, end=' ')
    preOrder(root.left)
    preOrder(root.right)
    
# 执行
preOrder(root) # 输出：1 2 4 5 3 

树的结构就是对递归最好的诠释。

• 文体形式：每个节点都有0~2个子节点。
• 终止条件：只需要判断当前节点不为none即可。

可见下图看结果

测试数据图例

扩展

怎样debug递归代码

如果自己一步一步的查看代码显然是不现实的，那么正确的debug递归代码，应该采取以下方案：

• 适量输出log 当问题出现在递归代码时，我们应该对于一些关键变量输出，甚至可以加一些格式使过程更直观。
• 减少问题规模 一般出问题的情况都是终止条件的问题，所以，将输入尽量减小数据，或分批测试出异常case。
• 采取非递归 有很多时候，可以将递归写法改为非递归，回到阶乘案例，可以进行循环计算

def factorial(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result
print(factorial(10))  # 结果：3628800

控制递归深度

import sys

sys.setrecursionlimit(50)

总结

递归凭借着简洁的语法得到极大的关注，但是想要写好递归还是需要一定经验的。希望本文对你有所帮助。