递归、迭代、回溯

递归(Recursion)

递归：一个函数在其定义中直接或间接调用自身的一种方法,它通常把一个大型的复杂的问题转化为一个与原问题相似的规模较小的问题来解决，可以极大的减少代码量。
递归必须包括两个部分：1）递归终止条件；2）递归过程。
它分为两个阶段:
1）递推：把复杂的问题的求解推到比原问题简单一些的问题的求解;
2）回归：当获得最简单的情况后,逐步返回,依次得到复杂的解.
利用递归可以解决很多问题:如背包问题,汉诺塔问题。
例：斐波那契数列为:0,1,1,2,3,5...

//fib(0)=0;
//fib(1)=1;
//fib(n)=fib(n-1)+fib(n-2);
int fib(int n)  
{  
   if(0 == n)  
       return 0;  
   if(1 == n)  
       return 1;  
   if(n > 1)  
       return fib(n-1)+fib(n-2);  
}

迭代(Iteration)

迭代：利用变量的原值推算出变量的一个新值。如果递归是自己调用自己的话，迭代就是A不停的调用B。
递归中一定有迭代，但是迭代中不一定有递归，大部分可以相互转换。能用迭代的不用递归，递归调用函数，浪费空间，并且递归太深容易造成堆栈的溢出。

//这是递归  
int funcA(int n)  
{  
    if(n > 1)  
       return n+funcA(n-1);  
    else   
       return 1;  
}  
//这是迭代  
int funcB(int n)  
{  
    int i,s=0;  
    for(i=1;i<n;i++)  
       s+=i;  
    return s;  
}

回溯法

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。