def fac(n):
if n==1 or n==2 or n==3:
print "i am calling fac(",n,")"
return n
else:
print "i am calling fac(",n,")"
x=fac(n-1)+fac(n-2)+fac(n-3)
return x
fac(6) 的输出是:
fac(6)
i am calling fac( 6 )
i am calling fac( 5 )
i am calling fac( 4 )
i am calling fac( 3 )
i am calling fac( 2 )
i am calling fac( 1 )
i am calling fac( 3 )
i am calling fac( 2 )
i am calling fac( 4 )
i am calling fac( 3 )
i am calling fac( 2 )
i am calling fac( 1 )
i am calling fac( 3 )
20
python2.7执行递归函数的规则是什么?
结果让我一头雾水,无法从计算树上分析出来。
为什么结果不是其他形式?
python处理递归计算的规则是什么?
最佳答案
Python 按照遇到调用它的指令的顺序运行每个调用。所以,从 fac
的顶部开始,n=6
,它将到达这一行:
x=fac(n-1)+fac(n-2)+fac(n-3)
它要做的第一件事是计算 n-1=5
,然后运行 fac(5)
- 它从函数的顶部再次开始。它会到达同一个地方并调用 fac(4)
,这将调用 fac(3)
- 它只返回 3。只有现在它才会计算 n- 2=2
并运行 fac(2)
,然后运行 fac(1)
并进行加法。现在 fac(4)
已经完成,我们回到了 fac(5)
,我们继续从 fac(n-2)
开始。
如果您修改您的函数以跟踪您的递归深度,您可以将调用打印为树结构,以便您可以更轻松地查看发生了什么:
def fac(n, level=0):
print '{}fac({})'.format(level*'\t', n)
if n==1 or n==2 or n==3:
return n
else:
x = fac(n-1, level+1) + fac(n-2, level+1) + fac(n-3, level+1)
return x
给出:
fac(6)
fac(5)
fac(4)
fac(3)
fac(2)
fac(1)
fac(3)
fac(2)
fac(4)
fac(3)
fac(2)
fac(1)
fac(3)
关于python - python2.7中递归函数的执行顺序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28778357/