迭代是人，递归是神

怎么去正视迭代与递归呢？

正如数学之美所说，To iterate is human,to recurse divine.迭代是人，递归是神。

---

以斐波那契数列来作为表示
fib(0)=0;
fib(1)=1;
fib(n)=fib(n-1)+fib(n-2);

---

迭代，更加符合我们的思维方式，我们更加容易去写出来。就如上述的表示方法来说，大部分的人都可以简单的去理解它。那我们用代码表示的话就是下面简单的代码。便于人思考，理解，去写，去寻找错误。但是有一个问题，不断的调用这个函数的话带来大量不必要的开支，消耗大量的时间。具体解释见此

int fib(int n){  
     if(n>1) return fib(n-1) + fib(n-2);  
     else return n; // n = 0, 1时给出recursion终止条件  
}

递归，更加符合计算机计算的方式，有利于计算速度。不必不断的调用函数，以减少开支。代码如下：

int fib(int n){  
    int i, temp0, temp1, temp2;        
    if(n<=1) return n;  
    temp1 = 0;  
    temp2 = 1;  
    for(i = 2; i <= n; i++){  
        temp0 = temp1 + temp2;  
        temp1 = temp2;  
        temp2 = temp0;  
    }  
    return temp0;  
} 

你们可以将代码带入一个数字计算一下可以在45左右。对比可知。

爬楼梯

附上一道基础的爬楼梯的题目：

假设你正在爬楼梯。需要 n 步你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

1. 1 步 + 1 步
2. 2 步

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

1. 1 步 + 1 步 + 1 步
2. 1 步 + 2 步
3. 2 步 + 1 步

迭代：

int climbStairs(int n) {
        if(n <= 2)
            return n;
        if(n > 2)
            return climbStairs(n-1)+climbStairs(n-2);
    }

递归：

    int climbStairs(int n) {
    int i, temp0, temp1, temp2;        
    if(n<=2) return n;  
    temp1 = 1;  
    temp2 = 2;  
    for(i = 3; i <= n; i++){  
        temp0 = temp1 + temp2;  
        temp1 = temp2;  
        temp2 = temp0;  
    }  
    return temp0; 
    }