递归框架：基准情形、信任、构建
应用三步法，为阶乘、幂运算和各位数字之和编写正确的递归解法，无需跟踪每次调用。
递归框架：基准情形、信任、构建 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
为什么递归让人感觉困难
大多数初学者会尝试在脑中跟踪每一次递归调用，即使递归深度只有五层，也很快会感到难以应付。专业的方法是使用一个三步框架——基本情况、信任、构建——这样您无需在脑中模拟完整的调用树，也能编写正确的递归函数。
这个框架有时也被称为信念飞跃：您相信函数能够处理更小的输入，并利用这一假设为更大的输入构建解决方案。
步骤 1：定义基本情况
基本情况是这样一种最简单的输入：无需进一步递归即可知道答案。每个递归函数都必须至少有一个基本情况；否则函数会无限递归（栈溢出）。好的基本情况包括：空列表、单个元素、n == 0、n == 1，或问题可归约为一个平凡恒等式。
请先写出基本情况，再编写任何递归逻辑。您可以通过提出以下问题来确定它：“我可以立即回答的这个问题的最小版本是什么？”
# Base cases for common problems
def factorial(n):
if n == 0: # base case: 0! = 1
return 1
# ... recursive step below
def sum_list(lst):
if not lst: # base case: sum of empty list is 0
return 0
# ...
def height(node):
if node is None: # base case: height of null node is 0
return 0
# ...
print('Base cases identified')步骤 2：信任递归调用
信任步骤是一种暂时的假设：假设您的函数对于任何严格小于当前输入的输入都已经正确运行。您现在不需要为每个更小的输入逐一证明——归纳证明会保证这一点。只需在较小的子问题上调用函数，并相信它会返回正确结果。
这是初学者常常跳过的一步，他们反而试图在脑中模拟整个过程。请克制这种冲动；一旦掌握这一框架，它可以扩展到任意深度的递归。
# Trust example: sum_list([3, 1, 4, 1, 5])
# Trust: sum_list([1, 4, 1, 5]) = 11 (we TRUST this, don't trace it)
# Build: 3 + 11 = 14
# So:
def sum_list(lst):
if not lst:
return 0
# Trust that sum_list(lst[1:]) returns sum of the rest
return lst[0] + sum_list(lst[1:])
print(sum_list([3, 1, 4, 1, 5])) # 14步骤 3：构建解决方案
构建步骤将可信的子问题结果与当前元素的贡献结合起来，为完整输入生成答案。这通常只需一行代码：对当前元素和递归调用的结果执行某个操作。常见的构建方式包括：将值加到总和中、将元素添加到列表开头、将计数加一、合并两个子结果。
def factorial(n):
if n == 0:
return 1
# Trust: factorial(n-1) gives (n-1)!
# Build: n * (n-1)! = n!
return n * factorial(n - 1)
def power(base, exp):
if exp == 0:
return 1
# Trust: power(base, exp-1) gives base^(exp-1)
# Build: base * base^(exp-1) = base^exp
return base * power(base, exp - 1)
print(factorial(6)) # 720
print(power(2, 10)) # 1024将框架应用于各位数字之和
问题：计算非负整数的各位数字之和。基本情况：n == 0 → 总和为 0（或者 n < 10 → n 本身）。信任：sumDigits(n // 10) 返回除最后一位外所有数字的总和。构建：将最后一位数字 n % 10 加到可信结果上。该框架通过三个声明式步骤得出解决方案。
def sumDigits(n):
if n < 10:
return n # base case: single digit
# Trust: sumDigits(n // 10) gives sum of all digits except last
# Build: add the last digit
return n % 10 + sumDigits(n // 10)
print(sumDigits(0)) # 0
print(sumDigits(7)) # 7
print(sumDigits(123)) # 6
print(sumDigits(9999)) # 36斐波那契：两个子问题
斐波那契需要进行两次递归调用：fib(n-1) 和 fib(n-2)。应用该框架：基本情况是 fib(0) = 0 和 fib(1) = 1。信任：两个更小的调用都会返回正确的斐波那契值。构建：返回它们的和。这种朴素实现的时间复杂度为 O(2^n)——我们会在记忆化课程中修复这个问题。
def fib(n):
if n <= 1:
return n # base cases: fib(0)=0, fib(1)=1
# Trust both smaller sub-problems
return fib(n - 1) + fib(n - 2)
for i in range(8):
print(f'fib({i}) = {fib(i)}') # 0,1,1,2,3,5,8,13使用递归反转字符串
问题：使用递归反转字符串。基本情况：空字符串或单个字符——它们已经是反转状态。信任：reverse(s[1:]) 返回除第一个字符之外所有内容的反转结果。构建：使用 append 将第一个字符添加到反转后缀的末尾。该框架给出了一个三行解决方案。
def reverse_str(s):
if len(s) <= 1:
return s # base case
# Trust: reverse_str(s[1:]) = reverse of 'ello' for 'hello'
# Build: append first character at end
return reverse_str(s[1:]) + s[0]
print(reverse_str('')) # ''
print(reverse_str('a')) # 'a'
print(reverse_str('hello')) # 'olleh'
print(reverse_str('racecar')) # 'racecar'使用递归统计出现次数
问题：使用递归统计列表中目标值的出现次数。基本情况：空列表——计数为 0。信任：count(lst[1:], target) 返回尾部列表中的计数。构建：如果第一个元素与目标值匹配，则加 1，否则加 0。每次递归都会将列表大小减少 1，从而向基本情况推进。
def count_occurrences(lst, target):
if not lst:
return 0
# Trust: count in rest of list is handled recursively
# Build: add 1 if first element matches, else 0
return (1 if lst[0] == target else 0) + count_occurrences(lst[1:], target)
print(count_occurrences([1, 2, 3, 2, 4, 2], 2)) # 3
print(count_occurrences([], 5)) # 0
print(count_occurrences([7, 7, 7], 7)) # 3检查列表是否已排序
问题：使用递归检查列表是否按升序排列。基本情况：包含 0 个或 1 个元素的列表始终是有序的。信任：is_sorted(lst[1:]) 会告诉您尾部列表是否有序。构建：当第一个元素 <= 第二个元素且尾部列表有序时，整个列表才有序。这是一个简洁的例子，其中构建步骤对两个条件使用逻辑 AND。
def is_sorted(lst):
if len(lst) <= 1:
return True
# Trust: is_sorted(lst[1:]) tells us if tail is sorted
# Build: head <= second element AND tail is sorted
return lst[0] <= lst[1] and is_sorted(lst[1:])
print(is_sorted([])) # True
print(is_sorted([1])) # True
print(is_sorted([1, 2, 3, 4])) # True
print(is_sorted([1, 3, 2, 4])) # False使用递归进行二分查找（再访）
使用该框架以递归方式表达二分查找：基本情况：lo > hi → 未找到（返回 -1）。信任：对正确的一半进行递归调用，它会找到目标值或返回 -1。构建：计算中点、进行比较，然后调用相应的一半。递归形式清晰地展示了分治结构，尽管在生产环境中，出于 O(1) 的空间考虑通常更倾向于使用迭代形式。
def binary_search(arr, target, lo, hi):
if lo > hi: # base case: search space exhausted
return -1
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
# Trust both halves return correct results
if arr[mid] < target:
return binary_search(arr, target, mid + 1, hi)
else:
return binary_search(arr, target, lo, mid - 1)
arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7, 0, len(arr) - 1)) # 3
print(binary_search(arr, 4, 0, len(arr) - 1)) # -1何时使用递归而非迭代
递归擅长处理能够自然分解为同类型更小子问题的问题（树、分治、回溯）。以下情况更适合使用迭代：递归深度较大（Python 中存在栈溢出风险，默认约为 1000），递归和迭代版本同样清晰，或者问题本身只是一个简单循环（阶乘、未使用记忆化的斐波那契）。
一个实用的经验法则是：如果画递归树感觉很自然，就使用递归。如果这棵树是一条直线（尾递归），请改用迭代。
import sys
# Python's default recursion limit
print('Recursion limit:', sys.getrecursionlimit()) # 1000
# A list of 2000 elements would overflow the recursive sum_list
# Use iteration for safety:
def sum_list_iter(lst):
total = 0
for x in lst:
total += x
return total
big = list(range(2000))
print(sum_list_iter(big)) # 1999000 — no stack overflow快速检查
请检验您对本课程中“数据结构与算法——编程面试准备”相关概念的理解。
课程回顾
在本课程中，您学到了：三步框架是基本情况（最简单的已知答案）、信任（假设子问题已解决）和构建（将当前元素与可信结果结合）；先编写基本情况，避免在脑中跟踪完整的调用树；以及当递归深度可能导致栈溢出，或递归和迭代形式同样清晰时，应使用迭代。接下来，我们将详细可视化调用栈。
常见问题解答
「递归框架：基准情形、信任、构建」课时是免费的吗？
是的 — 「递归框架：基准情形、信任、构建」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「递归框架：基准情形、信任、构建」这节课中我会学到什么？
应用三步法，为阶乘、幂运算和各位数字之和编写正确的递归解法，无需跟踪每次调用。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「递归框架：基准情形、信任、构建」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 递归框架：基准情形、信任、构建
- 可视化调用栈
- 递归与迭代的权衡
- 记忆化：缓存递归结果