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

递归调用本身就需要使用系统堆栈，每次分配函数内存和堆栈都需要时间。然而，这个过程并不需要太多时间。可以说简单递归本身并不比非递归慢多少。

但是在实践中会发现，一些问题的递归处理，尤其是递归问题，会表现出极低的效率。出现这个问题是因为重复计算。

比如用递归求解斐波那契数列的第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，并将函数体改为:

定义f(n):

如果定义了r[n]，那么只需返回r[n]作为答案。

否则，f(n) = f(n-1) + f(n-2)

在返回值之前，把它记在r[n]中。

改进的递归函数的效率与递归算法的效率几乎相同。