递归算法大家都不陌生，当需要重复计算相同问题时，一般可以选择递归和循环两种算法。又因为递归实现起来代码比较简洁，所以通常都会使用递归来解决上述问题。比如斐波那契数列，再比如树的前序、中序、后续遍历算法。

递归算法虽然是有代码简洁这个优点，但是其缺点显著。因为递归函数是在执行过程中调用其自身，所以会占用大量的栈上空间，并且压栈和出栈都是有时间消耗的。所以从这一点上来看，递归的效率是不如循环。除了效率之外，递归还有一个相当明显的问题：可能会导致栈溢出。当递归调用的次数过大时，很有可能会出现栈溢出的情况。

我们这里暂不考虑空间复杂度，仅讨论其时间复杂度以及改善方法。

还是以经典的Fibonacci数列为例，其定义如下：

1. 递归解法

对于这个题目，大家对于其算法已经十分熟悉，很快就能写出下面的代码：

long long Fibonacci(unsigned int n)
{
    if (n <= 0) {
        return 0;
    }

    if (n == 1) {
        return 1;
    }

    return Fibonacci(n-1) + Fibonacci(n-2);
}

我们可以看出来，上面的树中，很多结点都是重复计算的。事实上，递归算法的时间复杂度是n的指数级的。这样的复杂度，一般来说是不可接受的。

2. 递归算法改善

long long Fibonacci(unsigned int n)
{
    long long fibNMinusOne = 1;
    long long fibNMinusTwo = 0;
    long long fibN = 0;
    int result[2] = {0, 1};
    int i;

    if (n < 2) {
        return result[n];
    }
    
    for (i = 2; i < n; i++) {
        fibN = fibNMinusTwo + fibNMinusOne;
        fibNMinusTwo = fibNMinusOne;
        fibNMinusOne = fibN;
    }

    return fibN;
}