Question

递归算法的速度会特别慢的原因是什么？

Answer 1

递归调用本身需要使用系统栈,每次分配函数内存以及栈都需要时间.不过这个过程耗时并不多,可以说,单纯的递归本身并不比非递归慢多少.
然而,实践中就会发现,递归处理部分问题,特别是递推类问题时会表现出效率极低.这个问题的出现是因为重复计算.
举例说,用递归求解斐波那契数列的第n项,一般的递归公式为
f(n) = f(n-1)+f(n-2)
f(2) = 1
f(1) = 1
请尝试模拟计算机运行这个递归,你会发现,其中的某一项f(x)并不是只算了一次.当你计算f(5)的时候,你会试图计算f(4)和f(3),然而在你计算f(4)的时候其实也要计算f(3),这样f(3)就被调用了两次.
想象这个过程是指数型扩展的,效率会随着n的增大极快地下降.
要解决这个问题,可以使用记忆化思想.
定义记忆数组r,函数体改为:
define f(n):
if r[n] is defined, then simply return r[n] as the answer.
else, f(n) = f(n-1) + f(n-2)
before return the value, take it down in r[n].

如此改进之后的递归函数效率上与递推算法相差无几.

Answer 2

主要有两个原因吧。
1、递归需要不断的向下开栈，相较于循环，开销自然上来了，开栈的开销主要表现在：需要向栈上压参数（即访存，一般的代码会尽可能使用寄存器进行运算），需要往栈上压函数返回地址，需要给局部变量准备空间。
2、栈保护机制，因为现代编译器为了防止各种溢出攻击，会给函数调用加上栈保护，对应到指令层次就是会往栈上压一个金丝雀值。
所以一般追求效率的地方都会把递归改成循环，或者手动模拟栈。