在鄧俊輝的數(shù)據(jù)結(jié)構(gòu)教材的1.4節(jié)中簡要介紹了一下遞歸問題，在查閱相關(guān)資料后，發(fā)現(xiàn)遞歸問題包含了以下幾個方面：

• 線性遞歸（減而治之）
• 二分遞歸（分而治之）
• 動態(tài)規(guī)劃問題
  接下來結(jié)合教材以及網(wǎng)上相關(guān)資料對遞歸以及動態(tài)規(guī)劃問題做一個簡單的膚淺的入門的總結(jié)。

1.線性遞歸

線性遞歸（linear recursion）即減而治之（decrease-and-conquer）的思想：遞歸每深入一層，待求解問題的規(guī)模都縮減一個常數(shù)，直至最終蛻化為平凡的?。ê唵危﹩栴}。將一個規(guī)模為n的大問題退化為一個規(guī)模為n-1的小問題，直至退化為規(guī)模為1的平凡情況，這種情況稱之為遞歸基（base case of recursion）。
比如如下教材中對數(shù)組求和的代碼，若n=0則總和必為0（這也是最終的平凡情況，遞歸基）；否則一般的，總和可理解為前n-1個整數(shù)（A[0,-1））之和，再加上末尾元素A[n-1]。

int sum(int A[], int n) { //數(shù)組求和算法（線性遞歸版）
  if (1 > n) //平凡情況，遞歸基
   return 0; //直接（非遞歸式）計算
 else //一般情況
   return sum(A, n - 1) + A[n - 1]; //遞歸：前n - 1向之和，再累計第n - 1項
 } //O(n)

又比如下面的數(shù)組倒置問題，也就是將數(shù)組中各元素的次選前后翻轉(zhuǎn)。借助線性遞歸不難解決這一問題，為此只需注意到并利用如下事實：為得到整個數(shù)組的倒置，可以先對換其首、末元素，然后遞歸地倒置除這兩個元素以外的部分。

 void reverse(int* A, int lo, int hi) { //數(shù)組倒置（多遞歸基線性遞歸版）
   if (lo < hi) {
     swap(A[lo], A[hi]); //交換A[lo]和A[hi]
     reverse(A, lo + 1, hi - 1); //遞歸倒置A(lo, hi)
   } //else隱含了兩遞歸基
 } //O(hi - lo + 1)

2.二分遞歸

二分遞歸（binary recursion）即分而治之（divide-and-conquer）的思想：將其分解為若干規(guī)模更小的子問題， 再通過遞歸機制分別求解。 這種分解持續(xù)進行，直到子問題規(guī)模縮減至平凡情況。在這種情況下，每一遞歸實例會調(diào)用多個遞歸來完成，故稱作多路遞歸（multi-way recursion），通常都是將原問題一分為二，故有二分遞歸。
以下代碼是對數(shù)組求和的二分遞歸的實現(xiàn)，新算法的思路是：以居中的元素為界將數(shù)組一分為二；遞歸地對子數(shù)組分別求和；最后，子數(shù)組之和相加即為原數(shù)組的總和。

 int sum(int A[], int lo, int hi) { //數(shù)組求和算法（二分遞歸版，入口為sum(A, 0, n - 1)）
   if (lo == hi) //如遇遞歸基（區(qū)間長度已降至1），則
     return A[lo]; //直接返回元素
   else { //否則（一般情況下lo < hi），則
     int mi = (lo + hi) >> 1; //以居中單元為界，將原區(qū)間間一分為二
     return sum(A, lo, mi) + sum(A, mi + 1, hi); //遞歸對各子數(shù)組求和，然后合計
   }
 } //O(hi - lo + 1)，線性正比與區(qū)間的長度

對sum(A,0,7)的遞歸跟蹤分析

當然，并非所有問題都適宜于采用分治策略。實際上除了遞歸，此類算法的計算消耗主要來自兩個方面。首先是子問題劃分，即把原問題分解為形式相同、規(guī)模更小的多個子問題，比如sum()算法將待求和數(shù)組分為前、后兩段。其次是子解答合并，即由遞歸所得子問題的解，得到原問題的整體解，比如由子數(shù)組之和累加得到整個數(shù)組之和。
為使分治策略真正有效， 不僅必須保證以上兩方面的計算都能高效地實現(xiàn)， 還必須保證子問題之間相互獨立——各子問題可獨立求解， 而無需借助其它子問題的原始數(shù)據(jù)或中間結(jié)果。否則，或者子問題之間必須傳遞數(shù)據(jù)，或者子問題之間需要相互調(diào)用，無論如何都會導致時間和空間復
雜度的無謂增加。以下就以Fibonacci數(shù)列的計算為例說明這一點。

Fibonacci數(shù)列定于如下：

Fibonacci定義

據(jù)此定義，可直接導出如下代碼所示的二分遞歸版fib()算法：

 int fib(int n) { //計算Fibonacci數(shù)列列第n項（二分遞歸版）： O(2^n)
//若達到遞歸基，直接取值，否則，遞歸計算前兩項，其和即為正解
 return (2 > n) ? n : fib(n - 1) + fib(n - 2); 
 }

基于Fibonacci數(shù)列原始定義的這一算法實現(xiàn)， 不僅正確性一目了然，而且簡潔自然。然而不幸的是，在這種場合采用二分遞歸策略的效率極其低下。實際上， 該算法需要運行O(2n)時間才能計算出第n個Fibonacci數(shù)。這一指數(shù)復雜度的算法，在實際環(huán)境中毫無價值。

對于Fibonacci問題最簡單的實現(xiàn)就是迭代循環(huán)，也是一種比較直觀的算法，g為當前項的值，f為前一項的值，從0開始往前計算直到返回欲求的第n項的數(shù)值。

 int fibI(int n) { //計算Fibonacci數(shù)列的第n項（迭代版）： O(n)
   int f = 0, g = 1; //初始化： fib(0) = 0, fib(1) = 1
   while (0 < n--) { g += f; f = g - f; } //依據(jù)原始定義，通過n次加法和減法計算fib(n)
   return f; //迒回
 }

3.動態(tài)規(guī)劃

以下內(nèi)容主要來自CSDN博客-HankingHu

動態(tài)規(guī)劃核心

A * "1+1+1+1+1+1+1+1 =？" *

A : "上面等式的值是多少"
B : *計算* "8!"

A *在上面等式的左邊寫上 "1+" *
A : "此時等式的值為多少"
B : *quickly* "9!"
A : "你怎么這么快就知道答案了"
A : "只要在8的基礎上加1就行了"
A : "所以你不用重新計算因為你記住了第一個等式的值為8!動態(tài)規(guī)劃算法也可以說是 '記住求過的解來節(jié)省時間'"

由上面的圖片和小故事可以知道動態(tài)規(guī)劃算法的核心就是記住已經(jīng)解決過的子問題的解。

動態(tài)規(guī)劃算法的兩種形式
上面已經(jīng)知道動態(tài)規(guī)劃算法的核心是記住已經(jīng)求過的解，記住求解的方式有兩種：①自頂向下的備忘錄法 ②自底向上。為了說明動態(tài)規(guī)劃的這兩種方法，舉一個最簡單的例子：求斐波拉契數(shù)列Fibonacci 。

遞歸版本的Fibonacci算法在上面已經(jīng)有了，此處不再重復。其執(zhí)行的遞歸樹如下圖：

Fibonacci遞歸樹

上面的遞歸樹中的每一個子節(jié)點都會執(zhí)行一次，很多重復的節(jié)點被執(zhí)行，fib(2)被重復執(zhí)行了5次。由于調(diào)用每一個函數(shù)的時候都要保留上下文，所以空間上開銷也不小。這么多的子節(jié)點被重復執(zhí)行，如果在執(zhí)行的時候把執(zhí)行過的子節(jié)點保存起來，后面要用到的時候直接查表調(diào)用的話可以節(jié)約大量的時間。下面就看看動態(tài)規(guī)劃的兩種方法怎樣來解決斐波拉契數(shù)列Fibonacci 數(shù)列問題。

1.自頂向下的備忘錄法

public static int Fibonacci(int n)
{
        if(n<=0)
            return n;
        int []Memo=new int[n+1]; //備忘錄數(shù)組
        for(int i=0;i<=n;i++)
            Memo[i]=-1;
        return fib(n, Memo);
    }
    public static int fib(int n,int []Memo)
    {
        //如果已經(jīng)求出了fib（n）的值直接返回，否則將求出的值保存在Memo備忘錄中。 
        if(Memo[n]!=-1)  return Memo[n];
        if(n<=2)   Memo[n]=1;
        else Memo[n]=fib( n-1,Memo)+fib(n-2,Memo);  

        return Memo[n];
    }

備忘錄法也是比較好理解的，創(chuàng)建了一個n+1大小的數(shù)組來保存求出的斐波拉契數(shù)列中的每一個值，在遞歸的時候如果發(fā)現(xiàn)前面fib(n)的值計算出來了就不再計算，如果未計算出來，則計算出來后保存在Memo數(shù)組中，下次在調(diào)用fib(n)的時候就不會重新遞歸了。比如上面的遞歸樹中在計算fib(6)的時候先計算fib(5)，調(diào)用fib(5)算出了fib(4)后，fib(6)再調(diào)用fib(4)就不會再遞歸fib(4)的子樹了，因為fib(4)的值已經(jīng)保存在Memo[4]中。

2.自底向上的動態(tài)規(guī)劃

備忘錄法還是利用了遞歸，上面算法不管怎樣，計算fib(6)的時候最后還是要計算出fib(1)、fib(2)、fib(3)……,那么何不先計算出fib(1)、fib(2)、fib(3)……,呢？這也就是動態(tài)規(guī)劃的核心，先計算子問題，再由子問題計算父問題。

public static int fib(int n)
{
        if(n<=0)
            return n;
        int []Memo=new int[n+1];
        Memo[0]=0;
        Memo[1]=1;
        for(int i=2;i<=n;i++)
        {
            Memo[i]=Memo[i-1]+Memo[i-2];
        }       
        return Memo[n];
}

自底向上方法也是利用數(shù)組保存了先計算的值，為后面的調(diào)用服務。觀察參與循環(huán)的只有i，i-1，i-2三項，因此該方法的空間可以進一步的壓縮如下。

public static int fib(int n)
    {
        if(n<=1)
            return n;

        int Memo_i_2=0;
        int Memo_i_1=1;
        int Memo_i=1;
        for(int i=2;i<=n;i++)
        {
            Memo_i=Memo_i_2+Memo_i_1;
            Memo_i_2=Memo_i_1;
            Memo_i_1=Memo_i;
        }       
        return Memo_i;
    }

一般來說由于備忘錄方式的動態(tài)規(guī)劃方法使用了遞歸，遞歸的時候會產(chǎn)生額外的開銷，使用自底向上的動態(tài)規(guī)劃方法要比備忘錄方法好。

4.跳臺階問題

跳臺階問題是典型的Fibonacci問題，有以下兩種版本，以下內(nèi)容主要來自hackbuteer1的CSDN博客：程序員面試100題之二：跳臺階問題（變態(tài)跳臺階）。

題目1：一個臺階總共有n級，如果一次可以跳1級，也可以跳2級。求總共有多少總跳法，并分析算法的時間復雜度。
分析：

這道題最近經(jīng)常出現(xiàn)，包括MicroStrategy等比較重視算法的公司都曾先后選用過個這道題作為面試題或者筆試題。
首先我們考慮最簡單的情況。如果只有1級臺階，那顯然只有一種跳法。如果有2級臺階，那就有兩種跳的方法了：一種是分兩次跳，每次跳1級；另外一種就是一次跳2級。
現(xiàn)在我們再來討論一般情況。我們把n級臺階時的跳法看成是n的函數(shù)，記為f(n)。當n>2時，第一次跳的時候就有兩種不同的選擇：一是第一次只跳1級，此時跳法數(shù)目等于后面剩下的n-1級臺階的跳法數(shù)目，即為f(n-1)；另外一種選擇是第一次跳2級，此時跳法數(shù)目等于后面剩下的n-2級臺階的跳法數(shù)目，即為f(n-2)。因此n級臺階時的不同跳法的總數(shù)f(n)=f(n-1)+(f-2)。
我們把上面的分析用一個公式總結(jié)如下：

跳臺階問題分析

分析到這里，相信很多人都能看出這就是我們熟悉的Fibonacci序列。

題目2：一個臺階總共有n級，如果一次可以跳1級，也可以跳2級......它也可以跳上n級。此時該青蛙跳上一個n級的臺階總共有多少種跳法？
分析:

用Fib(n)表示青蛙跳上n階臺階的跳法數(shù)，青蛙一次性跳上n階臺階的跳法數(shù)1(n階跳)，設定Fib(0) = 1；

• 當n = 1 時， 只有一種跳法，即1階跳：Fib(1) = 1;
• 當n = 2 時， 有兩種跳的方式，一階跳和二階跳：Fib(2) = Fib(1) + Fib(0) = 2;
• 當n = 3 時，有三種跳的方式，第一次跳出一階后，后面還有Fib(3-1)中跳法； 第一次跳出二階后，后面還有Fib(3-2)中跳法；第一次跳出三階后，后面還有Fib(3-3)中跳法
• 總計：Fib(3) = Fib(2) + Fib(1)+Fib(0)=4;

當n = n 時，共有n種跳的方式：

• 第一次跳出一階后，后面還有Fib(n-1)中跳法；
• 第一次跳出二階后，后面還有Fib(n-2)中跳法；
• ……
• 第一次跳出n階后，后面還有 Fib(n-n)中跳法.
• 總計：Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+...+Fib(n-n)=Fib(0)+Fib(1)+Fib(2)+...+Fib(n-1)
  又因為Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+...+Fib(n-2)
  兩式相減得：Fib(n)-Fib(n-1)=Fib(n-1) =====》 Fib(n) = 2*Fib(n-1)
  遞歸等式如下：
  

5.總結(jié)及后續(xù)

HankingHu的博客在最后用一個切鋼條的例子對動態(tài)規(guī)劃做了更加詳細的說明，但本文不再繼續(xù)介紹了。因為本文主要是數(shù)據(jù)結(jié)構(gòu)教材中遞歸（線性遞歸、二分遞歸）部分的簡要總結(jié)，然后對Fibonacci的典型應用-跳臺階問題進行了介紹。關(guān)于動態(tài)規(guī)劃的問題留待以后完善和總結(jié)。
博客對動態(tài)規(guī)劃總結(jié)的很好，以后應該深入學習一下動態(tài)規(guī)劃。

參考

1. 鄧俊輝，數(shù)據(jù)結(jié)構(gòu)C++版教材
2. HankingHu的CSDN博客：算法-動態(tài)規(guī)劃 Dynamic Programming--從菜鳥到老鳥
3. hackbuteer1的CSDN博客：程序員面試100題之二：跳臺階問題（變態(tài)跳臺階）