递归

#include <iostream>
using namespace std;

//斐波拉契数列是这样一个数列：1, 1, 2, 3, 5, 8
int Fib(int n){
    if (n == 1 || n == 2){
        return 1;
    }
    else{
        return Fib(n - 1) + Fib(n - 2);
    }
}
//不使用递归
int myFib(int n){

    if (n == 1 || n == 2){
        return 1;
    }
    int prev = 0;
    int cur = 1;
    for (int i = 0; i < n-1; i++){
        int temp = cur;
        cur = prev + cur;
        prev = temp;
    }
    return cur;
}

int main(void)
{
    cout << Fib(7) << endl;
    cout << myFib(7) << endl;
}

 这种递归的写法看起来简洁明了，但是上面写法有一个问题：我们要求F(100)，那么要计算F(99)和F(98)；要计算F(99)，我们要计算F(98)和F(97)。。。大家已经发现到这一步，我们已经重复计算两次F(98)了。而之后的计算中还会有大量的重复，这使得这个解法的复杂度非常之高。解决方法就是，用一个数组，将计算过的值存起来，这样可以用空间上的牺牲来换取时间上的效率提高

int Fib(int n){


    if (n == 1 || n == 2){
        return 1;
    }
    if (array[n - 1] != 0){
        return array[n - 1];
    }
    array[n - 1] = Fib(n - 1) + Fib(n - 2);
    return array[n - 1];
}

动态转移虽然看上去十分高大上，但是它也存在两个致命缺点：

• 栈溢出 ：每一次递归，程序都会将当前的计算压入栈中。随着递归深度的加深，栈的高度也越来越高，直到超过计算机分配给当前进程的内存容量，程序就会崩溃。
• 数据溢出 ：因为动态规划是一种由简至繁的过程，其中积蓄的数据很有可能超过系统当前数据类型的最大值，导致崩溃。

当然，这两个bug也有相应的解决方法。对付栈溢出，我们可以把递归写成循环的形式（ 所有的递归都可改写成循环 ）；对付数据溢出，我们可以使用动态数组，vector来解决。

具体实例请参考动态规划相关

http://www.cnblogs.com/yuguangyuan/p/5835866.html