递归在解决某些问题时，使得我们思考的方式得以简化，代码也更加精炼，容易阅读。然而，既然递归有这么多优点，我们是否应该对所有问题都使用递归来解决呢？难道递归就没有缺点吗？今天我们就来讨论一下递归的不足之处。谈到递归，不得不面对它的效率问题。
为什么递归是低效的？
以斐波那契数列为例。在很多教科书或文章中涉及到递归或计算复杂性的地方都会将计算斐波那契数列的程序作为经典示例。如果现在让你以最快的速度用C#写出一个计算斐波那契数列第n个数的函数(不考虑参数小于1或结果溢出等异常情况),你的程序是否会和下列代码类似：
```csharp
public static ulong Fib(ulong n)
{
return (n == 1 || n == 2) ? 1 : Fib(n - 1) + Fib(n - 2);
}
```
这段代码应该算是短小精悍(执行代码只有一行),直观清晰，而且非常符合许多程序员的代码美学。但是，如果用这段代码试试计算Fib(1000),你可能会感到抓狂。
看来好看的代码未必中用，如果程序在效率不能接受，那美观神马的就都是浮云了。如果简单分析一下程序的执行流，就会发现问题在哪。以计算Fibonacci(5)为例：
从上图可以看出，在计算Fib(5)的过程中，Fib(1)计算了两次、Fib(2)计算了3次、Fib(3)计算了两次。本来只需要5次计算就可以完成的任务却计算了9次。这个问题随着规模的增加会愈发凸显，以至于Fib(1000)已经无法再可接受的时间内算出。
我们当时使用的是简单的用定义来求fib(n),也就是使用公式fib(n)=fib(n-1)+fib(n-2)。这样的想法是很容易想到的，可是仔细分析一下我们发现，当调用fib(n-1)的时候，还要调用fib(n-2),也就是说fib(n-2)调用了两次。同样的道理，调用f(n-2)时f(n-3)也调用了两次。而这些冗余的调用是完全没有必要的。可以计算这个算法的复杂度是指数级的。
改进的斐波那契递归算法
那么计算斐波那契数列是否有更好的递归算法呢？当然有。让我们来观察一下斐波那契数列的前几项：
1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...
我们可以观察到，如果去掉前面一项，得到的数列依然满足$f(n) = f(n-1) - f(n-2)$, $(n>2)$,而我们得到的数列是以1,2开头的。很容易发现这个数列的第n-1项就是原数列的第n项。怎么样，知道我们该怎么设计算法了吧？
我们可以写这样的一个函数，它接受三个参数，前两个是数列的开头两项，第三个是我们想求的以前两个参数开头的数列的第几项。
```cpp
int fib_i(int a, int b, int n);
```
在函数内部我们先检查n的值，如果n为3则我们只需返回a+b即可，这是简单情境。如果n>3,那么我们就调用$f(b, a+b, n-1)$,这样我们就缩小了问题的规模(从求第n项变成求第n-1项)。好了，最终代码如下：
```cpp
int fib_i(int a, int b ,int n)
{
if (n == 3)
return a + b;
else
return fib_i(b, a+b, n-1);
}
```
这样得到的算法复杂度是O(n)的。已经是线性的了。它的效率已经可以与迭代算法的效率相比了，但由于还是要反复的进行函数调用，还是不够经济。
递归算法与迭代算法的区别主要体现在函数调用次数上。递归算法需要进行n次函数调用才能解决问题，而迭代算法只需进行n次迭代操作即可。这种差异在效率上是非常显著的。
小结：
综上所述，递归在处理问题时需要反复调用函数，这会增加其空间和时间开销。因此，在可以使用迭代算法轻松解决问题的情况下，使用递归虽然可以简化思维过程，但在效率方面并不划算。效率和开销问题是递归的主要弱点。
尽管存在这样的缺点，但递归的强大作用仍然不容忽视。因为对于一些使用迭代算法难以甚至无法解决的问题(如汉诺塔问题),递归的作用就显现出来了。
