递归与递归树法
将递归调用展开为树，应用主定理，并推导归并排序、阶乘和各种斐波那契实现的时间复杂度。
递归与递归树法 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
递归与调用栈
当函数调用自身时，每次调用都会添加一个栈帧，这些栈帧不断累积，直到遇到基准情况后逐层返回。理解这一过程是分析递归的第一步。
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive call
# Call chain: factorial(4)
# 4 * factorial(3)
# 3 * factorial(2)
# 2 * factorial(1)
# 1 * factorial(0) -> 1
# Unwinds: 1, 2, 6, 24
print(factorial(5)) # 120斐波那契递归树
递归树会将每次调用展开为它的子调用。朴素的斐波那契算法每次都会拆分成两个调用，形成一棵大约包含 2^n 个节点的树——复杂度为 O(2^n)。请查看代码。
call_count = [0]
def fib_naive(n):
call_count[0] += 1
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2)
for n in [5, 10, 15, 20]:
call_count[0] = 0
result = fib_naive(n)
print(f'fib({n})={result}, calls={call_count[0]}')
# Calls roughly double each time n increases by 1识别重复的子问题
在这棵树中，相同的调用会在不同分支中重复出现，例如计算第 3 项的调用。这些重叠子问题正是使用记忆化的信号，它可以将 O(2^n) 降低到 O(n)。
# Memoised: each unique sub-problem computed once
def fib_memo(n, memo={}):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
call_count2 = [0]
def fib_counted(n, memo={}):
call_count2[0] += 1
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_counted(n-1, memo) + fib_counted(n-2, memo)
return memo[n]
fib_counted(20)
print(f'calls with memo: {call_count2[0]}') # only 21归并排序递归树
归并排序的递归树有 log n 层，每一层的总工作量都是 O(n)——每个元素都会被访问一次。将两者相乘即可得到 O(n log n)。请查看代码。
# Merge sort: at each level, n total elements are merged
# Level 0: 1 merge of n elements -> n work
# Level 1: 2 merges of n/2 each -> n work
# Level 2: 4 merges of n/4 each -> n work
# ...log(n) levels...
# Total: n * log(n)
# Verify with operation counter:
def merge_sort_counted(arr):
ops = [0]
def _sort(a):
if len(a) <= 1: return a
m = len(a) // 2
l, r = _sort(a[:m]), _sort(a[m:])
result, i, j = [], 0, 0
while i < len(l) and j < len(r):
ops[0] += 1
if l[i] <= r[j]: result.append(l[i]); i+=1
else: result.append(r[j]); j+=1
return result + l[i:] + r[j:]
return _sort(arr), ops[0]
_, c = merge_sort_counted(list(range(64, 0, -1)))
print(f'Merge ops: {c}') # ~384 ~ 64*log2(64)=384主定理
主定理可以通过三种情况求解 T(n) = a*T(n/b) + O(n^d)。对于归并排序（a=2，b=2，d=1），它给出的结果是 O(n log n)。请为考试记住这三种情况。
# Merge sort: T(n) = 2*T(n/2) + O(n)
# a=2, b=2, d=1, log_b(a)=log2(2)=1=d => O(n log n)
# Binary search: T(n) = 1*T(n/2) + O(1)
# a=1, b=2, d=0, log2(1)=0=d => O(log n)
# Strassen matrix mult: T(n) = 7*T(n/2) + O(n^2)
# a=7, b=2, d=2, log2(7)~2.81 > 2 => O(n^log2(7)) ~ O(n^2.81)
import math
print('log2(7) =', math.log2(7)) # 2.807...绘制递归树：逐步进行
绘制递归树时：先在顶部写下 T(n)，展开每次调用，计算每一层的工作量总和，然后乘以层数。请不断练习，直到能够熟练完成。
# Factorial: T(n) = T(n-1) + O(1)
# Tree is a chain: n levels, O(1) each -> O(n)
# Fibonacci: T(n) = T(n-1) + T(n-2) + O(1)
# Binary tree of depth n, ~2^n nodes -> O(2^n)
# Merge sort: T(n) = 2*T(n/2) + O(n)
# Log levels, n work each -> O(n log n)
def count_recursive_calls(n, results=[]):
if n <= 1:
results.append(n)
return n
return count_recursive_calls(n-1, results) + count_recursive_calls(n-2, results)
results = []
count_recursive_calls(8, results)
print(f'fib(8) leaf calls: {len(results)}')指数级递归：subsets
生成所有 subsets 的复杂度是 O(2^n)——它们恰好有 2^n 个，因此不可能做得更快。每个元素要么被选入，要么被排除，从而构建出一棵二叉选择树。请查看代码。
def subsets(nums):
result = []
def backtrack(start, current):
result.append(list(current)) # O(n) copy
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
return result
nums = [1, 2, 3]
ss = subsets(nums)
print(len(ss)) # 8 = 2^3
print(ss)尾递归与优化
尾递归指递归调用正好是最后一步。有些语言会复用这个栈帧，但 Python不会这样做——因此深层递归仍然会导致栈溢出。请改用循环。
# Tail-recursive factorial (accumulator pattern)
def fact_tail(n, acc=1):
if n == 0:
return acc
return fact_tail(n - 1, n * acc) # tail call
# Python does NOT TCO, so this overflows for large n
# Instead, convert to iterative:
def fact_iter(n):
acc = 1
while n > 0:
acc *= n
n -= 1
return acc
print(fact_tail(10)) # 3628800
print(fact_iter(10)) # 3628800递归的空间复杂度
每次递归调用都会保留一个栈帧，因此递归会占用 O(深度) 的空间。线性递归是 O(n)；平衡树的 DFS 是 O(log n)。递归过深就会触发 RecursionError。
import sys
print(sys.getrecursionlimit()) # default 1000
# Increase limit for deep problems
sys.setrecursionlimit(10000)
# Track max depth manually
def max_depth_tracker(n, depth=0, max_seen=[0]):
max_seen[0] = max(max_seen[0], depth)
if n <= 0:
return
max_depth_tracker(n - 1, depth + 1, max_seen)
return max_seen[0]
print(max_depth_tracker(50)) # 50 => O(n) stack frames快速排序的递归树
选择良好基准值时，快速排序是 O(n log n)；但在有序输入上选择糟糕的基准值时，复杂度会退化为 O(n^2)。这就是随机化基准值很重要的原因。请查看代码。
import random
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = random.choice(arr) # randomised -> O(n log n) expected
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
return quick_sort(less) + equal + quick_sort(greater)
print(quick_sort([3, 6, 8, 10, 1, 2, 1])) # sorted幂函数：O(log n) 递归
朴素地计算 x^n 需要 O(n) 次乘法，但通过平方运算可以在每一步将工作量减半：x^n = (x^(n/2))^2。这样就得到清晰的 O(log n)——这正是减半的应用。请查看代码。
def fast_pow(x, n):
if n == 0: return 1
if n < 0: return 1 / fast_pow(x, -n)
if n % 2 == 0:
half = fast_pow(x, n // 2)
return half * half # O(log n) calls
return x * fast_pow(x, n - 1)
print(fast_pow(2, 10)) # 1024
print(fast_pow(3, 5)) # 243
# Only log2(10)=3-4 recursive calls for n=10快速检查
快速检查一下——展示递归树方法带给您的收获。只有一道题，请慢慢思考。🌳
课程回顾
回顾：递归树揭示总工作量，主定理用于求解分治递归式，而递归会占用 O(深度) 的栈空间。
常见问题解答
「递归与递归树法」课时是免费的吗？
是的 — 「递归与递归树法」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「递归与递归树法」这节课中我会学到什么？
将递归调用展开为树，应用主定理，并推导归并排序、阶乘和各种斐波那契实现的时间复杂度。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「递归与递归树法」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 从零理解大 O 记法
- 分析循环与嵌套循环
- 递归与递归树法
- 空间复杂度与权衡