2.3 遞歸算法思想

知識點講解：光盤：視頻講解\第2章\遞歸算法思想.avi

因為遞歸算法思想往往用函數(shù)的形式來體現(xiàn)，所以遞歸算法需要預(yù)先編寫功能函數(shù)。這些函數(shù)是獨立的功能，能夠?qū)崿F(xiàn)解決某個問題的具體功能，當(dāng)需要時直接調(diào)用這個函數(shù)即可。在本節(jié)的內(nèi)容中，將詳細(xì)講解遞歸算法思想的基本知識。

2.3.1 遞歸算法基礎(chǔ)

在計算機編程應(yīng)用中，遞歸算法對解決大多數(shù)問題是十分有效的，它能夠使算法的描述變得簡潔而且易于理解。遞歸算法有如下3個特點。

① 遞歸過程一般通過函數(shù)或子過程來實現(xiàn)。

② 遞歸算法在函數(shù)或子過程的內(nèi)部，直接或者間接地調(diào)用自己的算法。

③ 遞歸算法實際上是把問題轉(zhuǎn)化為規(guī)模縮小了的同類問題的子問題，然后再遞歸調(diào)用函數(shù)或過程來表示問題的解。

在使用遞歸算法時，讀者應(yīng)該注意如下4點。

① 遞歸是在過程或函數(shù)中調(diào)用自身的過程。

② 在使用遞歸策略時，必須有一個明確的遞歸結(jié)束條件，這稱為遞歸出口。

③ 遞歸算法通常顯得很簡潔，但是運行效率較低，所以一般不提倡用遞歸算法設(shè)計程序。

④ 在遞歸調(diào)用過程中，系統(tǒng)用棧來存儲每一層的返回點和局部量。如果遞歸次數(shù)過多，則容易造成棧溢出，所以一般不提倡用遞歸算法設(shè)計程序。

2.3.2 實踐演練——解決“漢諾塔”問題

為了說明遞歸算法的基本用法，接下來將通過一個具體實例的實現(xiàn)過程，詳細(xì)講解遞歸算法思想在編程中的基本應(yīng)用。

實例2-5 使用遞歸算法解決“漢諾塔”問題

源碼路徑 光盤\daima\2\hannuo.c

問題描述：寺院里有3根柱子，第一根有64個盤子，從上往下盤子越來越大。方丈要求小和尚A1把這64個盤子全部移動到第3根柱子上。在移動的時候，始終只能小盤子壓著大盤子，而且每次只能移動一個。

方丈發(fā)布命令后，小和尚A1就馬上開始了工作，下面看他的工作過程。

（1）聰明的小和尚A1在移動時，覺得很難，另外他也非常懶惰，所以找來A2來幫他。他覺得要是A2能把前63個盤子先移動到第二根柱子上，自己再把最后一個盤子直接移動到第三根柱子，再讓A2把剛才的前63個盤子從第二根柱子上移動到第三根柱子上，整個任務(wù)就完成了。所以他找了另一個小和尚A2，然后下了如下命令：

① 把前63個盤子移動到第二根柱子上；

② 把第64個盤子移動到第三根柱子上后；

③ 把前63個盤子移動到第三根柱子上；

（2）小和尚A2接到任務(wù)后也覺得很難，所以他也和A1想的一樣：要是有一個人能把前62個盤子先移動到第三根柱子上，再把最后一個盤子直接移動到第二根柱子，再讓那個人把剛才的前62個盤子從第三根柱子上移動到第三根柱子上，任務(wù)就算完成了。所以他也找了另外一個小和尚A3，然后下了如下命令：

① 把前62個盤子移動到第三根柱子上；

② 自己把第63個盤子移動到第二根柱子上后；

③ 把前62個盤子移動到第二根柱子上；

（3）小和尚A3接了任務(wù)，又把移動前61個盤子的任務(wù)“依葫蘆畫瓢”的交給了小和尚A4，這樣一直遞推下去，直到把任務(wù)交給了第64個小和尚A64為止。

（4）此時此刻，任務(wù)馬上就要完成了，唯一的工作就是A63和A64的工作了。

小和尚A64移動第1個盤子，把它移開，然后小和尚A63移動給他分配的第2個盤子。

小和尚A64再把第1個盤子移動到第2個盤子上。到這里A64的任務(wù)完成，A63完成了A62交給他的任務(wù)的第一步。

算法分析：從上面小和尚的工作過程可以看出，只有A64的任務(wù)完成后，A63的任務(wù)才能完成，只有小和尚A2～小和尚A64的任務(wù)完成后，小和尚A1剩余的任務(wù)才能完成。只有小和尚A1剩余的任務(wù)完成，才能完成方丈吩咐給他的任務(wù)。由此可見，整個過程是一個典型的遞歸問題。接下來我們以有3個盤子來分析。

第1個小和尚命令：

① 第2個小和尚先把第一根柱子前2個盤子移動到第二根柱子，借助第三根柱子；

② 第1個小和尚自己把第一根柱子最后的盤子移動到第三根柱子；

③ 第2個小和尚你把前2個盤子從第二根柱子移動到第三根柱子。

非常顯然，第②步很容易實現(xiàn)。

其中第一步，第2個小和尚有2個盤子，他就命令：

① 第3個小和尚把第一根柱子第1個盤子移動到第三根柱子（借助第二柱子）；

② 第2個小和尚自己把第一根柱子第2個盤子移動到第二根柱子上；

③ 第3個小和尚把第1個盤子從第三根柱子移動到第二根柱子。

同樣，第②步很容易實現(xiàn)，但第3個小和尚只需要移動1個盤子，所以他也不用再下派任務(wù)了（注意：這就是停止遞歸的條件，也叫邊界值）。

第③步可以分解為，第2個小和尚還是有2個盤子，于是命令：

① 第3個小和尚把第二根柱子上的第1個盤子移動到第一根柱子；

② 第2個小和尚把第2個盤子從第二根柱子移動到第三根柱子；

③ 第3個小和尚你把第一根柱子上的盤子移動到第三根柱子。

分析組合起來就是：1→3,1→2,3→2，借助第三根柱子移動到第二根柱子；1→3是自私人留給自己的活；2→1,2→3,1→3是借助別人幫忙，第一根柱子移動到第三根柱子一共需要七步來完成。

如果是4個盤子，則第一個小和尚的命令中第①步和第③步各有3個盤子，所以各需要7步，共14步，再加上第1個小和尚的第①步，所以4個盤子總共需要移動7+1+7=15步；同樣，5個盤子需要15+1+15=31步，6個盤子需要31+1+31=63步……由此可以知道，移動n個盤子需要（2n-1）步。

假設(shè)用hannuo（n, a, b, c）表示把第一根柱子上的n個盤子借助第2根柱子移動到第3根柱子。由此可以得出如下結(jié)論。

第①步的操作是hannuo(n-1,1,3,2)，第③步的操作是hannuo(n-1,2,1,3)。

具體實現(xiàn)：根據(jù)上述算法分析，編寫實現(xiàn)文件hannuo.c，具體代碼如下所示。

        move(int n, int x, int y, int z)//移動函數(shù)，根據(jù)遞歸算法編寫
        {
        if (n==1)
        printf("%c-->%c\n", x, z);
        else
          {
        move(n-1, x, z, y);
        printf("%c-->%c\n", x, z);
              {
        getchar(); }
        move(n-1, y, x, z);
          }
        }
        main()
        {
        int h;
          printf("輸入盤子個數(shù)： "); //提示輸入盤子個數(shù)
        scanf("%d", &h);
          printf("移動%2d個盤子的步驟如下：\n", h);
          move(h, 'a', 'b', 'c'); //調(diào)用前面定義的函數(shù)開始移動，依次輸出一定步驟
        system("pause");
        }

執(zhí)行后先輸入移動盤子的個數(shù)，按下【Enter】鍵后將會顯示具體步驟。執(zhí)行效果如圖2-6所示。

圖2-6 “漢諾塔”問題執(zhí)行效果

2.3.3 實踐演練——解決“階乘”問題

為了說明遞歸算法的基本用法，接下來將通過一個具體實例的實現(xiàn)過程，詳細(xì)講解使用遞歸算法思想解決階乘問題的方法。

實例2-6 使用遞歸算法解決“階乘”問題

源碼路徑 光盤\daima\2\yunsuan.c

問題描述：階乘（factorial）是基斯頓·卡曼（Christian Kramp）于1808年發(fā)明的一種運算符號。自然數(shù)由1～n的n個數(shù)連乘積叫作n的階乘，記作n!。

例如所要求的數(shù)是4，則階乘式是1×2×3×4，得到的積是24，即24就是4的階乘。

例如所要求的數(shù)是6，則階乘式是1×2×3×…×6，得到的積是720，即720就是6的階乘。

例如所要求的數(shù)是n，則階乘式是1×2×3×…×n，設(shè)得到的積是x, x就是n的階乘。

在下面列出了0～10的階乘。

0! =1

1! =1

2! =2

3! =6

4! =24

5! =120

6! =720

7! =5040

8! =40320

9! =362880

10! =3628800

算法分析：假如計算6的階乘，則計算過程如圖2-7所示。

圖2-7 計算6的階乘的過程

具體實現(xiàn)：根據(jù)上述算法分析，使用遞歸法編寫文件jiecheng.c，具體代碼如下所示。

        #include <stdio.h>
        int fact(int n);
        int main()
        {
            int i;
            printf("輸入要計算階乘的一個整數(shù)：");
            scanf("%d", &i);
            printf("%d的階乘結(jié)果為：%d\n", i, fact(i));
            getch();
            return 0;
        }
        int fact(int n)
        {
            if(n<=1)
            return 1;
            else
            return n*fact(n-1);
        }

執(zhí)行后如果輸入“6”并按下【Enter】鍵，則會輸出6的階乘是720，執(zhí)行效果如圖2-8所示。

圖2-8 計算6的階乘的執(zhí)行效果