python2.7中递归函数的执行顺序

Question

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处理递归计算的规则是什么？

Answer 1

Python 运行s 每次调用都按照遇到指令的顺序调用它。因此，从 fac 的顶部开始 n=6，它将到达这一行：

x=fac(n-1)+fac(n-2)+fac(n-3)

它要做的第一件事是计算 n-1=5 和运行 fac(5) - 它再次从函数的顶部开始。它将到达同一个地方并调用 fac(4)，这将调用 fac(3) - 只是 returns 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)

python2.7中递归函数的执行顺序

the executed order of recursion function in python2.7

python

recursion

python-2.7