Python 递归算法基础：原理与经典实例

递归，作为编程中极具魅力的算法思想，核心是函数调用自身，将复杂问题拆解为规模更小的同类子问题，直到触达'边界条件'（递归出口）后逐层回溯，最终解决原问题。这种'大事化小、小事化了'的思路，能让代码简洁优雅，尤其适合解决具有重复子结构的问题。

本文将通过 4 个经典实例，带你吃透递归的核心逻辑，所有代码均可直接运行，建议结合注释逐行理解递归的'递'与'归'。

一、阶乘算法：递归的入门典范

阶乘是递归最基础的应用场景。数学上，n!（n 的阶乘）定义为：

• 边界条件：0! = 1（0 的阶乘为 1，是人为规定的递归出口）
• 递归关系：n! = n × (n-1)!（n>0 时，n 的阶乘等于 n 乘以 n-1 的阶乘）

代码实现：

# 阶乘运算
def factorial(n):
    if n == 0:
        return 1
    else:
        return factorial(n - 1) * n

n = int(input())
print(f'{n}的阶乘为{factorial(n)}')

逻辑解析：以计算 5! 为例，递归的执行过程是'先递后归'：

1. 递：factorial(5) → 调用 factorial(4) → 调用 factorial(3) → 调用 factorial(2) → 调用 factorial(1) → 调用 factorial(0)；
2. 归：factorial(0)返回 1 → factorial(1)=1×1=1 → factorial(2)=1×2=2 → factorial(3)=2×3=6 → factorial(4)=6×4=24 → factorial(5)=24×5=120。

二、斐波那契数列：递归解决递推关系问题

斐波那契数列是经典的递推数列，其核心规律为：

• 边界条件：第 1 位和第 2 位均为 1（F(1)=1，F(2)=1）；
• 递归关系：从第 3 位开始，每一位等于前两位之和（F(n) = F(n-1) + F(n-2)）。

代码实现：

# 第 n 个斐波那契数
def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

n = int(input())
print(f'第{n}个斐波那契数为{fibonacci(n)}')

逻辑解析：计算第 5 个斐波那契数时，递归会拆解为：fibonacci(5) = fibonacci(4) + fibonacci(3)，fibonacci(4) = fibonacci(3) + fibonacci(2)，fibonacci(3) = fibonacci(2) + fibonacci(1)。当触达 n=1或n=2 的边界条件后，开始回溯求和，最终得到 fibonacci(5)=5。

注：纯递归实现斐波那契数列存在重复计算问题（如 fibonacci(3)会被计算多次），适合理解递归逻辑；实际开发中可结合记忆化缓存优化效率。

三、全排列问题：递归拆解'选元素 + 排剩余'

全排列是指从 n 个不同元素中取出所有元素，按任意顺序排列，最终得到所有可能的排列组合。递归解决全排列的核心思路是：

• 边界条件：若列表只剩 1 个元素，其全排列就是自身；
• 递归关系：遍历列表中的每个元素，将其作为'第一个元素'，再对剩余元素递归求全排列，最终拼接所有结果。

代码实现：

# 全排列问题
def full_permutation(lst):
    if len(lst) == 1:
        # 如果列表中的元素仅有一个，那么直接输出
        return [lst]
    result = []
    for i in range(len(lst)):
        first = lst[i]
        rest = lst[:i] + lst[i+1:]
        for j in full_permutation(rest):
            result.append([first] + j)
    return result

# 用 eval 解析输入字符串为真正的列表
lst = eval(input("请输入列表，例如 [1,2,3]:"))
for p in full_permutation(lst):
    print(p)

逻辑解析：以列表 [1,2,3] 为例：

1. 先选 1 作为第一个元素，剩余 [2,3]，递归求 [2,3] 的全排列（[[2,3],[3,2]]），拼接得到 [[1,2,3],[1,3,2]]；
2. 再选 2 作为第一个元素，剩余 [1,3]，递归求全排列后拼接得到 [[2,1,3],[2,3,1]]；
3. 最后选 3 作为第一个元素，剩余 [1,2]，递归求全排列后拼接得到 [[3,1,2],[3,2,1]]；
4. 所有结果合并，得到 [1,2,3] 的 6 种全排列。

四、汉诺塔问题：递归解决'分步移动'类问题

汉诺塔是递归的经典应用，问题规则为：

• 有 A、B、C 三根柱子，A 柱有 n 个大小递减的盘子（大盘在下、小盘在上）；
• 每次只能移动 1 个盘子，且任何时候大盘不能放在小盘上；
• 目标是将 A 柱所有盘子移到 C 柱，B 柱作为过渡。

递归解决汉诺塔的核心思路：

• 边界条件：若只有 1 个盘子，直接从 A 移到 C；
• 递归关系：
  1. 先将 A 柱上 n-1 个盘子从 A 移到 B（以 C 为过渡）；
  2. 将 A 柱最后 1 个大盘移到 C；
  3. 再将 B 柱上 n-1 个盘子从 B 移到 C（以 A 为过渡）。

代码实现：

# 汉诺塔问题
def hanoi(n, start, mid, end):
    if n == 1:
        # 只有一个盘子，直接从 start 移动到 end
        print(start, "-->", end)
        return
    # 先把上面的 n-1 个盘子移动到 mid 处，才能移动最下面的那个最大的盘子（注意顺序）
    hanoi(n - 1, start, end, mid)
    print(start, "-->", end)
    # 再把中间的 n-1 个移动到 end，进行递归操作
    hanoi(n - 1, mid, start, end)

n = int(input())
if __name__ == "__main__":
    hanoi(n, "A", "B", "C")

逻辑解析：以 n=2 为例，执行过程：

1. 调用 hanoi(1,A,C,B)，触发边界条件，打印 A --> B；
2. 打印 A --> C（移动第 2 个盘子）；
3. 调用 hanoi(1,B,A,C)，触发边界条件，打印 B --> C；最终完成 2 个盘子从 A 到 C 的移动（实际输出可结合规则验证步骤合理性）。

---

递归算法核心总结

1. 递归三要素：明确边界条件（递归出口，避免无限递归）、定义递归关系（将大问题拆为小问题）、确定返回值（保证回溯时能正确拼接结果）；
2. 执行逻辑：始终遵循'先递后归'—— 先逐层拆解问题到边界条件，再从边界条件开始回溯计算，最终得到原问题答案；
3. 适用场景：适合解决具有'重复子结构'的问题（如阶乘、斐波那契、全排列、汉诺塔），但需注意递归深度（Python 默认递归深度有限）和重复计算问题，必要时结合缓存、迭代优化。

递归的本质是'自顶向下'的问题拆解，掌握它不仅能简化代码，更能培养'分而治之'的编程思维。建议结合上述实例手动推演执行过程，理解每一步的'递'与'归'，真正吃透递归的核心逻辑。