我真的在努力理解递归是如何工作并且理解递归算法。例如，当我输入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)
了解Python中的递归
9
- suffa
4
4个回答
27
让我们走过执行过程。
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)
将结果中的fact(1)替换
fact(5) = 5 * 4 * 3 * 2 * 1 * fact(0)
在我们的结果中替换fact(0)
fact(5) = 5 * 4 * 3 * 2 * 1 * 1 = 120
就是这样。递归是一个将一个大问题一步步拆解为更小的子问题，直到达到基本情况（或“基础”）的过程。
- Ross Larson
11
将问题分解为执行步骤。
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）。
- Rob Wagner
6
请记住，每次调用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)`向`fact(5)`返回1（终止情况）。 - `fact(5)`向`fact(4)`返回1 * 1 - `fact(4)`向`fact(3)`返回2 * 1 - `fact(3)`向`fact(2)`返回3 * 2 - `fact(2)`向`fact(1)`返回4 * 6 - 最后，`fact(1)`将120（5 * 24）返回给它的调用者，无论那是什么。
- user1277476
3
一种递归函数是一种调用自身并继续执行直到评估完成并产生结果的函数。上面的阶乘函数的关键之处在于返回x * fact(x-1)，所以如果输入5，则它将执行5 * fact(5-1) * fact(4-1)....等等，直到遇到0，然后返回1。因此你会得到5*4*3*2*1，也就是120。它会继续在堆栈上分配变量，所以如果输入的数字太大，可能会导致堆栈溢出异常。除非使用称为尾调用优化（TCO）的东西，将递归函数转换为for循环并清理内存分配。
- The Internet
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
fact函数内部，它再次调用了自身？并且当 n 等于 0 时，这个自我调用就停止了？而且每次自我调用时，n 的值都会减少一个？ - Marco de Wit