跳到主要内容

递归函数

1. 定义​

  • 递归函数：在函数内部调用自身本身的函数。
  • 函数内部可以调用其他函数；若调用的是自己，即为递归。

2. 示例：阶乘​

  • 递推关系：fact(n) = n! = 1×2×…×n = (n−1)!×n = fact(n−1)×n
  • n=1 时特殊处理：fact(1)=1。
def fact(n):
    if n == 1:
        return 1
    return n * fact(n - 1)

fact(1)    # 1
fact(5)    # 120
fact(100)  # 很大的数

计算过程（fact(5)）​

=> fact(5)
=> 5 * fact(4)
=> 5 * (4 * fact(3))
=> 5 * (4 * (3 * fact(2)))
=> 5 * (4 * (3 * (2 * fact(1))))
=> 5 * (4 * (3 * (2 * 1)))
=> ... => 120

3. 优点与缺点​

优点缺点
逻辑简单清晰，定义贴近数学递推过深调用会导致栈溢出
理论上所有递归都可写成循环，但循环不如递归直观Python 标准解释器没有尾递归优化，任何递归都可能栈溢出

4. 栈溢出​

  • 原理：函数调用用栈（stack）实现——进入一次调用加一层栈帧，返回时减一层；栈大小有限，递归过深会溢出。
  • 表现：如 fact(1000) 会报 RuntimeError: maximum recursion depth exceeded。

5. 尾递归​

概念​

  • 尾递归：在函数返回时只调用自身本身，且 return 语句不包含表达式（即 return f(...) 这种形式）。
  • 这样编译器/解释器可做优化：递归只占一个栈帧，栈不增长，不会栈溢出。
  • 尾递归与循环等价；没有循环的语言可用尾递归实现循环。

为何 fact(n) 不是尾递归​

  • return n * fact(n - 1) 中含有表达式 n * ...，不是“只返回递归调用”，因此不是尾递归。

改成尾递归写法​

  • 把每一步的乘积作为参数传入，使 return 仅返回递归调用本身。
def fact(n):
    return fact_iter(n, 1)

def fact_iter(num, product):
    if num == 1:
        return product
    return fact_iter(num - 1, num * product)   # 仅返回递归调用，无表达式
  • fact(5) 对应 fact_iter(5, 1) 的调用链：
=> fact_iter(5, 1)
=> fact_iter(4, 5)
=> fact_iter(3, 20)
=> fact_iter(2, 60)
=> fact_iter(1, 120)
=> 120
  • 若做了尾递归优化，栈不会增长；但 Python 解释器没有做尾递归优化，即使用尾递归写法，在 Python 中仍会栈溢出。

小结​

要点说明
递归函数函数内部调用自身；逻辑清晰，易写
栈溢出调用过深，栈帧过多；Python 递归深度有限
尾递归return 只含“调用自身”，无表达式；可被优化为只占一个栈帧
Python标准解释器没有尾递归优化，任何递归都存在栈溢出风险；深递归建议改循环

记忆：递归 = 自己调自己；尾递归 = 最后一步只调自己、无运算；Python 不优化尾递归，深递归要小心。

练习：汉诺塔——编写 move(n, a, b, c)，把 n 个盘子从 A 借助 B 移到 C，并打印每一步（如 A-->C）。