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按照遇到调用它的指令的顺序运行每个调用.所以,从facwith 的顶部开始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)