五、遞回演算法

（1）遞回

遞回：在運行的程序中通過呼叫本身進行“遞”與“歸”來解決問題的一種演算法，
遞回演算法一般用于解決三類問題：
(1)資料的定義是按遞回定義的，（Fibonacci函式）
(2)問題解法按遞回演算法實作，
這類問題雖則本身沒有明顯的遞回結構，但用遞回求解比迭代求解更簡單，如Hanoi問題，
(3)資料的結構形式是按遞回定義的，
如二叉樹、廣義表等，由于結構本身固有的遞回特性，則它們的操作可遞回地描述，

（2）遞回的三大要素

第一要素：明確你這個函式想要干什么

對于遞回，很重要的一個事就是，這個函式的功能是什么，它要完成什么樣的一件事，而這個，是完全由你自己來定義的，也就是說，我們先不管函式里面的代碼什么，而是要先明白，你這個函式是要用來干什么，
比如，我定義了一個函式

//算 n 的階乘(假設n不為0)
int f(int n) 
{
}

這個函式的功能是計算 n 的階乘，好了，我們已經定義了一個函式，并且定義了它的功能是什么，接下來我們看第二要素，

第二要素：尋找遞回結束條件

所謂遞回，就是會在函式內部代碼中，呼叫這個函式本身，所以，我們必須要找出遞回的結束條件，不然的話，會一直呼叫自己，進入死回圈，也就是說，我們需要找出當引數為啥時，遞回結束，之后直接把結果回傳，請注意，這個時候我們必須能根據這個引數的值，能夠直接知道函式的結果是什么，
比如，上面那個例子，當 n = 1 時，那你應該能夠直接知道 f(n) 是啥吧？此時，f(1) = 1，完善我們函式內部的代碼，把第二要素加進代碼里面，如下

// 算 n 的階乘(假設n不為0)
int f(int n)
{
    if(n == 1)
    {
        return 1;
    }
}

有人可能會說，當 n = 2 時，那我們可以直接知道 f(n) 等于多少啊，那我可以把 n = 2 作為遞回的結束條件嗎？
當然可以，只要你覺得引數是什么時，你能夠直接知道函式的結果，那么你就可以把這個引數作為結束的條件，所以下面這段代碼也是可以的，

// 算 n 的階乘(假設n>=2)
int f(int n){
    if(n == 2){
        return 2;
    }
}

注意我代碼里面寫的注釋，假設 n >= 2，因為如果 n = 1時，會被漏掉，當 n <= 2時，f(n) = n，所以為了更加嚴謹，我們可以寫成這樣：

// 算 n 的階乘(假設n不為0)
int f(int n){
    if(n <= 2){
        return n;
    }
}

第三要素：找出函式的等價關系式

第三要素就是，我們要不斷縮小引數的范圍，縮小之后，我們可以通過一些輔助的變數或者操作，使原函式的結果不變，例如，f(n) 這個范圍比較大，我們可以讓 f(n) = n * f(n-1)，這樣，范圍就由 n 變成了 n-1 了，范圍變小了，并且為了原函式 f(n) 不變，我們需要讓 f(n-1) 乘以 n，說白了，就是要找到原函式的一個等價關系式，f(n) 的等價關系式為 n * f(n-1)，即f(n) = n * f(n-1)，
找出了這個等價關系式，繼續完善我們的代碼，我們把這個等價式寫進函式里，如下：

// 算 n 的階乘(假設n不為0)
int f(int n){
    if(n <= 2){
        return n;
    }
    // 把 f(n) 的等價操作寫進去
    return f(n-1) * n;
}

至此，遞回三要素已經都寫進代碼里了，所以這個 f(n) 功能的內部代碼我們已經寫好了，
這就是遞回最重要的三要素，

（3）遞回簡單案例

案例1：斐波那契數列

斐波那契數列的是這樣一個數列：1、1、2、3、5、8、13、21、34…，即第一項 f(1) = 1,第二項 f(2) = 1…,第 n 專案為 f(n) = f(n-1) + f(n-2)，求第 n 項的值是多少，

1、第一遞回函式功能

假設 f(n) 的功能是求第 n 項的值，代碼如下：

int f(int n){

}

2、找出遞回結束的條件

顯然，當 n = 1 或者 n = 2 ,我們可以輕易著知道結果 f(1) = f(2) = 1，所以遞回結束條件可以為 n <= 2，代碼如下：

int f(int n){
    if(n <= 2){
        return 1;
    }
}

3、找出函式的等價關系式

題目已經把等價關系式給我們了，所以我們很容易就能夠知道 f(n) = f(n-1) + f(n-2)，

所以最終代碼如下：

int f(int n){
    // 1.先寫遞回結束條件
    if(n <= 2){
        return 1;
    }
    // 2.接著寫等價關系式
    return f(n-1) + f(n - 2);
}

案例2：hzx跳臺階

hzx是一只勇敢的豬，一次可以跳上1級臺階，也可以跳上2級，求hzx跳上一個n級的臺階總共有多少種跳法，

1、第一遞回函式功能

假設 f(n) 的功能是求hzx跳上一個n級的臺階總共有多少種跳法，代碼如下：

int f(int n){

}

2、找出遞回結束的條件

求遞回結束的條件，我們直接把 n 壓縮到很小很小就行了，因為 n 越小，我們就越容易直觀著算出 f(n) 的多少，所以當 n = 1時，我們知道 f(1) 為多少吧？即 f(1) = 1，代碼如下：

int f(int n)
{
    if(n == 1)
    {
        return 1;
    }
}

3、找出函式的等價關系式

每次跳的時候，hzx可以跳一個臺階，也可以跳兩個臺階，也就是說，每次跳的時候，hzx有兩種跳法，
第一種跳法：第一次hzx跳了一個臺階，那么還剩下n-1個臺階還沒跳，剩下的n-1個臺階的跳法有f(n-1)種，
第二種跳法：第一次hzx跳了兩個臺階，那么還剩下n-2個臺階還沒，剩下的n-2個臺階的跳法有f(n-2)種，
所以，hzx的全部跳法就是這兩種跳法之和了，即 f(n) = f(n-1) + f(n-2)，
至此，等價關系式我們就求出來了，于是寫出代碼如下：

int f(int n)
{
    if(n == 1)
    {
        return 1;
    }
    return f(n-1) + f(n-2);
}

大家覺得上面的代碼對不對？
答案是不對的，當 n = 2 時，顯然會有 f(2) = f(1) + f(0)，我們知道，f(0) = 0，按道理是遞回結束，不用繼續往下呼叫的，但我們上面的代碼中，會繼續呼叫 f(0) = f(-1) + f(-2)，這會導致無限呼叫，進入死回圈，這也是我們需要注意的，關于遞回結束條件是否夠嚴謹問題，有很多人在使用遞回的時候，由于結束條件不夠嚴謹，導致出現死回圈，
也就是說，當我們在第二步找出了一個遞回結束條件的時候，可以把結束條件寫進代碼，然后進行第三步，但是請注意，當我們第三步找出等價函式之后，還得再回傳去第二步，根據第三步函式的呼叫關系，會不會出現一些漏掉的結束條件，就像上面，f(n-2)這個函式的呼叫，有可能出現 f(0) 的情況，導致死回圈，所以我們把它補上，
總代碼如下：

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

案例3：漢諾塔問題

問題描述：

相傳在古印度圣廟中，有一種被稱為漢諾塔(Hanoi)的游戲，該游戲是在一塊銅板裝置上，有三根桿(編號A、B、C)，在A桿自下而上、由大到小按順序放置64個金盤(如下圖)，游戲的目標：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好，操作規則：每次只能移動一個盤子，并且在移動程序中三根桿上都始終保持大盤在下，小盤在上，操作程序中盤子可以置于A、B、C任一桿上，

問題分析：

設三根柱子分別為 x,y, z , 盤子在 x 柱上，要移到 z 柱上，

1、當 n=1 時，盤子直接從 x 柱移到 z 柱上；

2、當 n>1 時, 則

①設法將 前 n –1 個盤子 借助 z ，從 x 移到y 柱上，把 盤子 n 從 x 移到 z 柱上；

② 把n –1 個盤子從 y 移到 z 柱上，

漢諾塔問題可以分成三個子問題：

1.Hanoi(n-1, x, z, y)

//將X柱上的n-1個園盤借助Z柱移到Y柱上，此時X柱只剩下第n個園盤；

2.Move( n, x， z)

//將X柱上的第n個移動到Z柱

3.Hanoi(n-1, y, x, z)

//將Y柱上的n-1個園盤借助X柱移到Z柱上；

n=1時可以直接求解

可視化圖解

代碼如下：

#include <iostream>
using namespace std;
long count = 0;//記錄移動的次數
void hanoi(int n,char a,char b,char c)   //n個盤子，a移動到c，用b做臨時塔
{
      if (1 == n)
        {
          cout<<"第"<<++count<<"次: "<<a<<"塔--->"<<c<<"塔"<<endl;
        }
    else
        {
           hanoi(n-1,a,c,b);//遞回呼叫，a移到b,c做臨時塔
        cout<<"第"<<++count<<"次: "<<a<<"塔--->"<<c<<"塔"<<endl;
           hanoi(n-1,b,a,c);
        }
}
int main()
{
int n;
cout<<"輸入漢諾塔圓盤的數量： ";
cin>>n;
hanoi(n,'A','B','C');
return 0;
}

案例4：分魚問題

問題描述：

A、B、C、D、E這5個人合伙夜間捕魚，凌晨時都已經疲憊不堪，于是各自在河邊的樹叢中找地方睡著了，第二天日上三竿時，A第一個醒來，他將魚平分為5份，把多余的一條扔回河中，然后拿著自己的一份回家去了；B第二個醒來，但不知道A已經拿走了一份魚，于是他將剩下的魚平分為5份，扔掉多余的一條，然后只拿走了自己的一份；接著C、D、E依次醒來，也都按同樣的辦法分魚，問這5人至少合伙捕到多少條魚？每個人醒來后所看到的魚是多少條？

問題分析

假設5個人合伙捕了x條魚，則“A第一個醒來，他將魚平分為5份，把多余的一條扔回河中，然后拿著自己的一份回家去了”之后，還剩下4(x-1)/5條魚，
這里實際包含了一個隱含條件：假設Xn為第n(n=1、2、3、4、5)個人分魚前魚的總數，則(Xn-1)/5必須為正整數，否則不合題意，（Xn-1)/5為正整數即(X?l)mod5=0必須成立，
根據題意，應該有下面等式：
X4=4(X5-1)/5
X3=4(X4-1)/5
X2-4(X3-1)/5
X1=4(X2-1)/5

#include<iostream>
using namespace std;
int fish(int n, int x)
{
               if((x-1)%5 == 0)
             {
               if(n == 1)
               return 1;  
               else
               return fish(n-1, (x-1)/5*4); 
             }
           return 0;  //x不是符合題意的解，回傳0
}
int main()
{
int i=0, flag=0, x;
do
{   i=i+1;
    x=i*5+1;  //x最小值為6，以后每次增加5
    if(fish(5, x))  //將x傳入分魚遞回函式進行檢驗
        {  
             flag=1;  //找到第一個符合題意的x則置標志位為1
             cout<<"五個人合伙捕到的魚總數為"<<x;
        }
}
while(!flag);  //未找到符合題意的x，繼續回圈，否則退出回圈
return 0;
}

遞推演算法 “步步為營” 學習之旅 任重道遠