Python 3:为什么环比递归更快

Question

i比较了循环和递归的运行时间，发现循环的速度更快，同时又没有遇到递归的问题。为什么循环更快？

def factorial(n):
   if n == 0:
      return n
   else:
      return n + factorial(n-1)
%%timeit -n1000 -r10000
factorial(1000)

163 µs±13.2 µs每循环（平均±标准dev。10000次运行，每个1000个回路）

def factorial2(n):
   r = 0
   for i in range(n+1):
      r += i
   return r
%%timeit -n1000 -r10000
factorial2(1000)

最慢的运行时间比最快的时间长9.46倍。这可能意味着中间结果被缓存。每循环58.7 µs±25.2 µs（平均±std。Dev。10000次运行，每个1000个回路）

谢谢和愉快的编码！

Answer 1

一般而言，除非专门制作编程语言以支持快速递归，否则递归始终会较慢。当程序进行函数调用时，将创建一个新的堆栈帧，其中所有本地变量都存储在其他方面。在迭代期间，一切都发生在单个堆栈框架内。

有一个叫做"尾部递归"的东西，其中写入函数的方式是，该计算的结果始终在最后帧中可用 - 因此，从理论上讲，只有1个堆栈框架就足够了。在某些语言中，编译器认识到这种情况，并将递归转变为"幕后"的迭代 - 这种类型的递归确实与迭代一样快。不幸的是，python3不支持尾部递归。