Python 里特别有意思的一种编程技巧 ——递归！递归就像是俄罗斯套娃，一个娃娃里面套着另一个更小的娃娃，层层嵌套。在编程里，递归就是函数自己调用自己。听起来有点绕？别担心，我会用最简单的例子带你搞懂它！掌握了递归，你写代码的思路会开阔很多，一些复杂的问题也能迎刃而解。

一、什么是递归？

递归是一种解决问题的方法，在这种方法中，函数会直接或间接地调用自己。递归函数通常包含两个部分：

基线条件（Base Case）也叫终止条件，是递归停止的点，防止无限循环。

递归条件（Recursive Case）函数调用自己的条件。

举个生活中的例子，假设你在电影院看电影，你想知道自己坐在第几排，但是又懒得数。这时候你可以问前面一排的人："你坐在第几排？"，等前面的人告诉你他的排数后，你再在他的排数上加 1，就是你自己的排数。前面的人如果也不知道自己的排数，他也会问他前面的人，直到问到第一排的人，第一排的人知道自己是第 1 排，然后这个信息就会一层一层传回来，直到你得到答案。

在这个例子中，"问到第一排的人" 就是基线条件，因为第一排的人不需要再问别人；"问前面的人" 就是递归条件，因为每个人都在重复这个动作。

二、递归函数的基本结构

在 Python 中，递归函数的基本结构是这样的：

def recursive_function(parameters):    # 基线条件    if base_case_condition:        return base_case_value    # 递归条件    else:        return recursive_function(modified_parameters)

下面我们通过几个具体的例子来理解递归。

三、递归的经典例子：计算阶乘

阶乘是一个数学概念，用符号n!表示，定义如下：

0! = 1

n! = n * (n-1)!（当n > 0时）

可以看到，阶乘的定义本身就具有递归的特性，我们可以用递归函数来计算阶乘：

def factorial(n):    # 基线条件：当n为0时，返回1    if n == 0:        return 1    # 递归条件：当n大于0时，返回n乘以(n-1)的阶乘    else:        return n * factorial(n-1)# 测试阶乘函数print(factorial(5))  # 输出120，因为5! = 5 * 4 * 3 * 2 * 1 = 120

这个函数是怎么工作的呢？当我们调用factorial(5)时，执行过程如下：

factorial(5)调用5 * factorial(4)

factorial(4)调用4 * factorial(3)

factorial(3)调用3 * factorial(2)

factorial(2)调用2 * factorial(1)

factorial(1)调用1 * factorial(0)

factorial(0)返回 1（基线条件）

然后结果一层一层返回：factorial(1)返回1 * 1 = 1

factorial(2)返回2 * 1 = 2

factorial(3)返回3 * 2 = 6

factorial(4)返回4 * 6 = 24

factorial(5)返回5 * 24 = 120

小贴士：递归函数的调用过程可以用调用栈来表示，每一次函数调用都会在栈上创建一个新的帧，当函数返回时，这个帧就会被弹出。

四、递归的另一个经典例子：斐波那契数列

斐波那契数列是这样一个数列：0, 1, 1, 2, 3, 5, 8, 13, ...，其中每个数都是前两个数的和，定义如下：

F(0) = 0

F(1) = 1

F(n) = F(n-1) + F(n-2)（当n > 1时）

我们可以用递归函数来计算斐波那契数列的第 n 项：

def fibonacci(n):    # 基线条件：当n为0或1时，直接返回n    if n == 0 or n == 1:        return n    # 递归条件：当n大于1时，返回前两项的和    else:        return fibonacci(n-1) + fibonacci(n-2)# 测试斐波那契函数print(fibonacci(6))  # 输出8，因为斐波那契数列的第6项是8

这个函数的执行过程比阶乘函数要复杂一些，因为每次调用都会产生两个递归调用。当我们调用fibonacci(6)时，函数会多次调用自己，形成一个递归树。

注意事项：斐波那契数列的递归实现虽然简洁，但效率不高，因为会有大量的重复计算。对于较大的 n，建议使用迭代方法或记忆化技术来优化。

五、递归的实际应用场景

递归在实际编程中有很多应用场景，比如：

遍历目录树：操作系统在查找文件时，会递归地遍历目录树。

解析 XML/HTML 文档：解析器会递归地解析文档的每个节点。

分治算法：如快速排序、归并排序等。

游戏开发：如 AI 路径查找、棋类游戏的状态树搜索等。

下面是一个简单的递归函数，用于计算列表中所有元素的和：

def sum_list(lst):    # 基线条件：当列表为空时，返回0    if not lst:        return 0    # 递归条件：返回列表的第一个元素加上剩余元素的和    else:        return lst[0] + sum_list(lst[1:])# 测试求和函数numbers = [1, 2, 3, 4, 5]print(sum_list(numbers))  # 输出15

六、递归的优缺点

优点

代码简洁递归可以用很少的代码解决复杂的问题。

逻辑清晰对于一些具有递归结构的问题，递归解法更符合人类的思维方式。

缺点

效率问题递归调用会消耗大量的栈空间，如果递归深度过大，可能会导致栈溢出。

可能的重复计算如斐波那契数列的递归实现，会有大量的重复计算。

小练习：用递归函数实现一个函数，计算一个数的幂，即power(base, exponent)，例如power(2, 3)应该返回 8。试试看吧！

七、常见错误提醒

忘记基线条件如果递归函数没有基线条件，或者基线条件不满足，会导致无限递归，最终导致栈溢出错误。

递归深度过大Python 默认的递归深度是有限的（通常是 1000 层），如果递归深度超过这个限制，会抛出RecursionError。

性能问题对于一些问题，递归解法可能不是最优的，需要考虑使用迭代或其他优化方法。