递归入门

罗浩森2026/8/22大约 1 分钟

1. 核心心法：递归信任（“套娃”思维）

不要试图在脑子里一层层追踪递归过程（n→n-1→n-2...）。你只需要相信：只要“小一号的子问题”能解决，当前问题就一定能解决。

2. 写递归函数的三步法

步骤1：定义函数（明确输入输出）
步骤2：找出口（Base Case）- 必须写在最前面，处理最小规模问题
步骤3：找公式（Recursive Rule）- 拆解为“一小步”+“剩余子问题”

3. 典型代码模板

# 线性递归（阶乘）
def factorial(n):
    if n == 1:        # 出口条件：当n=1时，递归结束
        return 1
    return n * factorial(n - 1)  # 公式

# 线性递归（列表求和-健壮版）
def sum_list(lst):
    if not lst:       # 出口条件：当列表为空时，递归结束
        return 0
    return lst[0] + sum_list(lst[1:])

# 两端收缩递归（回文判断）
def is_palindrome(s):
    if len(s) <= 1:   # 出口条件：当字符串长度为0或1时，满足回文，递归结束
        return True
    return s[0] == s[-1] and is_palindrome(s[1:-1])

4. 必须避开的致命陷阱

忘记写出口 -> RecursionError（栈溢出）
出口逻辑错误（如0!返回0） -> 全盘算错
忽略边界（如传入空列表/空字符串） -> IndexError

5. 底层机制：调用栈（Call Stack）

递推：任务暂停压栈 -> 触底 -> 回归：弹栈逐层返回计算结果。

6. 已掌握的两种递归模式

线性递归：每次解决一个元素（求和、阶乘）
分治（双向）递归：同时从两端向内推进（回文判断）