[!info] related notes 算法面试题型 MOC 二叉树基础 分治

递归算法

基本结构

递归函数由两部分组成：

1. 基线条件（Base Case）：不再递归的终止情况，直接返回结果。
2. 递归条件（Recursive Case）：将问题缩小为更小的子问题，调用自身。

def factorial(n):
    if n <= 1:          # base case
        return 1
    return n * factorial(n - 1)  # recursive case

调用栈可视化

以 factorial(4) 为例：

factorial(4)
  factorial(3)
    factorial(2)
      factorial(1) → 返回 1    ← base case
    返回 2 * 1 = 2
  返回 3 * 2 = 6
返回 4 * 6 = 24

每次递归调用在栈上压入一帧（frame），包含局部变量和返回地址。栈深 = 递归深度。Python 默认递归限制约 1000 层。

尾递归（Tail Recursion）

如果递归调用是函数的最后一个操作，编译器可以优化为循环，不增加栈帧。

# 普通递归（非尾递归）
def factorial(n):
    if n <= 1: return 1
    return n * factorial(n - 1)  # 乘法在递归返回后执行

# 尾递归版本
def factorial_tail(n, acc=1):
    if n <= 1: return acc
    return factorial_tail(n - 1, n * acc)  # 递归是最后一步

注意：Python 不做尾递归优化，但理解这个概念对函数式语言（Scheme、Erlang）很重要。

记忆化（Memoization）

递归 + 缓存 = 避免重复计算，是动态规划的自顶向下版本。

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1: return n
    return fib(n - 1) + fib(n - 2)

时间从 $O(2^n)$ 降为 $O(n)$。

递归 vs 迭代

维度	递归	迭代
可读性	对树/图结构更自然	对线性结构更直观
空间	$O(n)$ 栈空间	$O(1)$（手动管理栈除外）
性能	函数调用开销	通常更快
转换	任何递归都能改写为迭代+显式栈	—

常见落点

• 树：天然递归结构（根 + 左子树 + 右子树）。入门建议用二叉树练递归：二叉树基础。
• DFS：递归栈就是隐式栈。
• 回溯：递归 + 选择 + 撤销。模板：

def backtrack(path, choices):
    if 满足结束条件:
        result.append(path[:])
        return
    for choice in choices:
        path.append(choice)       # 做选择
        backtrack(path, 新choices) # 递归
        path.pop()                # 撤销选择

• 分治：拆分 -> 递归求解 -> 合并。参见 分治。

相关笔记

• 二叉树基础
• 分治
• 算法面试题型 MOC