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].

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