Python 递归练习：基线条件与更小的问题
先写停止条件，递归会容易很多。然后只问一个问题：这个函数可以把什么样更小的输入传给自己？
先写基线条件
基线条件是可以立刻回答的输入。倒计时里，零是自然的停止点。先单独测试基线条件，再添加递归分支。
def countdown(n):
if n == 0:
return 0
return 1 + countdown(n - 1)
print(countdown(4))可计数的递归
缩小输入
每次调用都必须朝基线条件靠近。阶乘用 n 乘以 factorial(n - 1)，所以输入每次都减小。没有这个减小，函数会永远调用自己。
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print(factorial(5))每次输入都更小
小心分叉
有些问题需要两次递归调用。斐波那契使用 fib(n - 1) 和 fib(n - 2)。画出 n = 5 的调用树，会看到重复的分支；这也是大输入需要缓存的原因。
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(6))两个递归分支
遍历嵌套列表
递归列表函数先处理第一个元素，再把剩下的部分交给更小的列表。空列表返回基线值。这个模式可以扩展到树和其他嵌套结构。
def total(items):
if not items:
return 0
return items[0] + total(items[1:])
print(total([2, 4, 6]))列表越来越短
调试递归错误
如果 Python 抛出 RecursionError，在每次调用开头打印输入。检查基线条件是否存在，以及每个分支是否都更接近它。问题本身扁平且重复时，循环可能更清楚。
def total(items, depth=0):
print(" " * depth, len(items))
if not items:
return 0
return items[0] + total(items[1:], depth + 1)
print(total([1, 2, 3]))追踪不断缩短的输入
你的练习清单
- 写递归调用前，先找出最小输入。
- 确认每个分支都缩小了输入。
- 手算一个小例子。
- 递归没有带来清晰度时，改用循环。
常见问题
什么是基线条件？
函数不用再调用自己就能返回答案的输入。它负责停止递归。
为什么递归函数很慢？
它可能重复计算相同的子问题，朴素斐波那契就是例子。记忆化或迭代版本可以避免重复工作。
所有循环都能改写成递归吗？
理论上可以，但不是所有问题都会更清楚。数据或问题天然嵌套时，再用递归。
练习递归
12 道题，覆盖基线条件、阶乘、斐波那契、列表递归和调试。
继续阅读：