递推与递归

    递推：构造低阶的规模(如规模为i，一般i=0)的问题，并求出解，推导出问题规模为i+1的问题以及解，依次推到规模为n的问题。(知道第一个，推出下一个，直到达到目的。，关键要找到递推公式）
    递归：将问题规模为n的问题，降解成若干个规模为n-1的问题，依次降解，直到问题规模可求，求出低阶规模的解，代入高阶问题中，直至求出规模为n的问题的解。（要知道第一个，需要先知道下一个，直到一个已知的，再反回来，得到上一个，直到第一个。）
    递归包括回溯和递推两个过程。

 

    最好的例子是斐波那契数列:   0   1   1   2   3   5   8   13   21   ...   ...
    总结成公式就是F(n)=F(n-1)+F(n-2),   F(0)=0,F(1)=1;
    你可以用递归的方法写这个函数:
    int   F(int   n)  

   {
       if   (n <2)  

           return   n;
       else  

           return   F(n-1)+F(n-2);
   }
   但也可以用递推的方式:
   int   F(int   n)  

  {
       if   (n <2)  

            return   1; 
       int   twoback=0,oneback=1,current;

      for   (int   i=0;   i <n-1;   i++)  

        { 
            current=oneback+twoback; 
            twoback=oneback;        //保存f（n-1），下次的f(n-2)             oneback=current;          //保存f（n），下次的f(n-1)
        }
   }
    显然能用递推的话就用递推,   一般肯定要比递归快,除非有的问题不用递归做不出来的.
线性规划法在推导时往往是用递归的形式,但最后可以化为递推。