我真的在努力理解递归是如何工作并且理解递归算法。例如,当我输入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)
我真的在努力理解递归是如何工作并且理解递归算法。例如,当我输入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)
让我们走过执行过程。
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
就是这样。递归是一个将一个大问题一步步拆解为更小的子问题,直到达到基本情况(或“基础”)的过程。
将问题分解为执行步骤。
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)。
请记住,每次调用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
函数内部,它再次调用了自身?并且当 n 等于 0 时,这个自我调用就停止了?而且每次自我调用时,n 的值都会减少一个? - Marco de Wit