理解 Python 中的递归

问题描述：

我真的在努力弄清楚递归的工作原理并理解递归算法。例如，当我输入 5 时，下面的代码返回 120，请原谅我的无知，我只是不明白为什么？

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n-1)

answer = int (raw_input('Enter some number: '))

print fact(answer)

解决方案 1：

让我们看一下执行过程。

fact(5):
   5 is not 0, so fact(5) = 5 * fact(4)
   what is fact(4)?
fact(4):
   4 is not 0, so fact(4) = 4 * fact(3)
   what is fact(3)?
fact(3):
   3 is not 0, so fact(3) = 3 * fact(2)
   what is fact(2)?
fact(2):
   2 is not 0, so fact(2) = 2 * fact(1)
   what is fact(1)?
fact(1):
   1 is not 0, so fact(1) = 1 * fact(0)
   what is fact(0)?
fact(0):
   0 IS 0, so fact(0) is 1

现在让我们收集结果。

fact(5) = 5* fact(4)

用我们的结果代替事实（4）

fact(5) = 5 * 4 * fact(3)

用我们的结果代替事实（3）

fact(5) = 5 * 4 * 3 * fact(2)

用我们的结果代替事实（2）

fact(5) = 5 * 4 * 3 * 2 * fact(1)

用我们的结果代替事实（1）

fact(5) = 5 * 4 * 3 * 2 * 1 * fact(0)

用我们的结果代替事实（0）

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

就是这样。递归是将大问题分解为多个小问题的过程，直到达到简单（或“基本”）情况。

解决方案 2：

将问题分解为执行步骤。

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 * fact(0)))))
|||||| 5 * 4 * 3 * 2 * 1 * 1
120

您的函数只是调用自身，就像任何其他函数可以调用它一样。但是在这种情况下，您的函数需要一个停止点，以便它不会无限递归（导致堆栈溢出！）。在您的例子中，这是当n为 0 时（它可能应该是 1）。

解决方案 3：

请记住，每次调用 fact() 时，无论是外部调用还是自身调用，都会获得一组独特的局部变量。

fact(1) has n of 5
   fact(2) has n of 4
      fact(3) has n of 3
         fact(4) has n of 2
            fact(5) has n on 1
               fact(6) has n of 0

最深的层（这里fact(6)是指最深的层）在调用堆栈中位于其上方的层完成之前就已经完全计算出来了。

所以

• fact(6)返回 1 fact(5)（终止情况）。

• fact(5)返回 1 到fact(4)(1*1)

• fact(4)将 2 返回到fact(3)(2*1)

• fact(3)将 6 返回给fact(2)(3*2)

• fact(2)返回 24 到fact(1)(4*6)

• 最后fact(1)返回 120（5*24）给它的调用者，无论它是什么。

解决方案 4：

递归函数是调用自身并持续执行直到评估完成并产生结果的函数。上面的阶乘函数的关键是返回 x * fact(x-1)

因此，如果您输入 5，它将执行 5 fact(5-1) fact 4-1) .... 依此类推，直到达到 0 然后返回 1。因此，您将得到 54321，即 120。

它继续在堆栈上分配变量。因此，如果您输入的数字过高，可能会导致堆栈溢出异常。除非您使用所谓的尾部调用优化 (TCO)，它将递归函数变成 for 循环并清理分配的内存。