理解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)

.

替换我们的结果以便（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

.

和你有它。递归是通过在达到琐碎（或“基础”）案例之前通过看起来成功较小的问题来打破更大问题的过程。

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

递归函数是一个呼叫自身，继续这样做，直到评估完成并且产生结果。上面具有阶乘函数的键是返回x *事实（x-1）

所以如果输入5，它将执行5 *事实（5-1）*事实4-1）....等等，直到它命中0然后返回1.所以你有5 * 4 * 3* 2 * 1是120.

继续在堆栈上分配变量。因此，如果您将一个太高的数字，它可能会导致堆栈溢出异常。除非您使用称为尾呼叫优化（TCO）的东西，否则将递归函数变为循环并清除分配的内存。