python - 理解 Python 中的递归

Question

我真的很想围绕递归的工作原理和理解递归算法。例如，当我输入 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)

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)

用我们的结果代替 fact(4)

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

用我们的结果代替 fact(3)

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

用我们的结果代替 fact(2)

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

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

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

用我们的结果替换 fact(0)

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

你有它。递归是通过将较大的问题视为成功的较小问题来分解较大问题的过程，直到您遇到微不足道的（或“基本”）案例。

Answer 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）。

Answer 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) 给它的调用者，不管它是什么。

Answer 4

递归函数是一个调用自身并继续这样做直到评估完成并产生结果的函数。上面的阶乘函数的关键是 return x * fact(x-1)

因此，如果您输入 5，它将执行 5 * fact(5-1) * fact 4-1) .... 依此类推，直到达到 0 然后返回 1。所以您将拥有 5*4*3*2* 1 是 120。

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