對C語言中遞歸算法的深入解析

2020-01-26 15:59:57

字體：大中小

來源：轉載

供稿：網友

許多教科書都把計算機階乘和菲波那契數列用來說明遞歸，非常不幸我們可愛的著名的老潭老師的《C語言程序設計》一書中就是從階乘的計算開始的函數遞歸。導致讀過這本經書的同學們，看到階乘計算第一個想法就是遞歸。但是在階乘的計算里，遞歸并沒有提供任何優越之處。在菲波那契數列中，它的效率更是低的非常恐怖。

這里有一個簡單的程序，可用于說明遞歸。程序的目的是把一個整數從二進制形式轉換為可打印的字符形式。例如：給出一個值4267，我們需要依次產生字符‘4'，‘2'，‘6'，和‘7'。就如在printf函數中使用了%d格式碼，它就會執行類似處理。

我們采用的策略是把這個值反復除以10，并打印各個余數。例如，4267除10的余數是7，但是我們不能直接打印這個余數。我們需要打印的是機器字符集中表示數字‘7'的值。在ASCII碼中，字符‘7'的值是55，所以我們需要在余數上加上48來獲得正確的字符，但是，使用字符常量而不是整型常量可以提高程序的可移植性。‘0'的ASCII碼是48，所以我們用余數加上‘0'，所以有下面的關系：

          ‘0'+ 0 =‘0'
          ‘0'+ 1 =‘1'
          ‘0'+ 2 =‘2'
      　　　    ...
從這些關系中，我們很容易看出在余數上加上‘0'就可以產生對應字符的代碼。接著就打印出余數。下一步再取商的值，4267/10等于426。然后用這個值重復上述步驟。

這種處理方法存在的唯一問題是它產生的數字次序正好相反，它們是逆向打印的。所以在我們的程序中使用遞歸來修正這個問題。

我們這個程序中的函數是遞歸性質的,因為它包含了一個對自身的調用。乍一看，函數似乎永遠不會終止。當函數調用時，它將調用自身，第2次調用還將調用自身，以此類推，似乎永遠調用下去。這也是我們在剛接觸遞歸時最想不明白的事情。但是，事實上并不會出現這種情況。

這個程序的遞歸實現了某種類型的螺旋狀while循環。while循環在循環體每次執行時必須取得某種進展，逐步迫近循環終止條件。遞歸函數也是如此，它在每次遞歸調用后必須越來越接近某種限制條件。當遞歸函數符合這個限制條件時，它便不在調用自身。

在程序中，遞歸函數的限制條件就是變量quotient為零。在每次遞歸調用之前，我們都把quotient除以10，所以每遞歸調用一次，它的值就越來越接近零。當它最終變成零時，遞歸便告終止。

/*接受一個整型值（無符號0，把它轉換為字符并打印它，前導零被刪除*/

復制代碼代碼如下:

#include <stdio.h>

int binary_to_ascii( unsigned int value)
{
          unsigned int quotient;

   　　quotient = value / 10;
   　　if( quotient != 0)
       　　　　binary_to_ascii( quotient);
   　　putchar ( value % 10 + '0' );
}

遞歸是如何幫助我們以正確的順序打印這些字符呢？下面是這個函數的工作流程。
1. 將參數值除以10
2. 如果quotient的值為非零，調用binary-to-ascii打印quotient當前值的各位數字
3. 接著，打印步驟1中除法運算的余數

注意在第2個步驟中，我們需要打印的是quotient當前值的各位數字。我們所面臨的問題和最初的問題完全相同，只是變量quotient的值變小了。我們用剛剛編寫的函數（把整數轉換為各個數字字符并打印出來）來解決這個問題。由于quotient的值越來越小，所以遞歸最終會終止。

一旦你理解了遞歸，閱讀遞歸函數最容易的方法不是糾纏于它的執行過程，而是相信遞歸函數會順利完成它的任務。如果你的每個步驟正確無誤，你的限制條件設置正確，并且每次調用之后更接近限制條件，遞歸函數總是能正確的完成任務。

但是，為了理解遞歸的工作原理，你需要追蹤遞歸調用的執行過程，所以讓我們來進行這項工作。追蹤一個遞歸函數的執行過程的關鍵是理解函數中所聲明的變量是如何存儲的。當函數被調用時，它的變量的空間是創建于運行時堆棧上的。以前調用的函數的變量扔保留在堆棧上，但他們被新函數的變量所掩蓋，因此是不能被訪問的。

當遞歸函數調用自身時，情況于是如此。每進行一次新的調用，都將創建一批變量，他們將掩蓋遞歸函數前一次調用所創建的變量。當我追蹤一個遞歸函數的執行過程時，必須把分數不同次調用的變量區分開來，以避免混淆。

程序中的函數有兩個變量：參數value和局部變量quotient。下面的一些圖顯示了堆棧的狀態，當前可以訪問的變量位于棧頂。所有其他調用的變量飾以灰色的陰影，表示他們不能被當前正在執行的函數訪問。

假定我們以4267這個值調用遞歸函數。當函數剛開始執行時，堆棧的內容如下圖所示：

執行除法之后，堆棧的內容如下：

接著，if語句判斷出quotient的值非零，所以對該函數執行遞歸調用。當這個函數第二次被調用之初，堆棧的內容如下：

堆棧上創建了一批新的變量，隱藏了前面的那批變量，除非當前這次遞歸調用返回，否則他們是不能被訪問的。再次執行除法運算之后，堆棧的內容如下：

quotient的值現在為42，仍然非零，所以需要繼續執行遞歸調用，并再創建一批變量。在執行完這次調用的出發運算之后，堆棧的內容如下：

此時，quotient的值還是非零，仍然需要執行遞歸調用。在執行除法運算之后，堆棧的內容如下：

不算遞歸調用語句本身，到目前為止所執行的語句只是除法運算以及對quotient的值進行測試。由于遞歸調用這些語句重復執行，所以它的效果類似循環：當quotient的值非零時，把它的值作為初始值重新開始循環。但是，遞歸調用將會保存一些信息（這點與循環不同），也就好是保存在堆棧中的變量值。這些信息很快就會變得非常重要。

現在quotient的值變成了零，遞歸函數便不再調用自身，而是開始打印輸出。然后函數返回，并開始銷毀堆棧上的變量值。

每次調用putchar得到變量value的最后一個數字，方法是對value進行模10取余運算，其結果是一個0到9之間的整數。把它與字符常量‘0'相加，其結果便是對應于這個數字的ASCII字符，然后把這個字符打印出來。

輸出4：

接著函數返回，它的變量從堆棧中銷毀。接著，遞歸函數的前一次調用重新繼續執行，她所使用的是自己的變量，他們現在位于堆棧的頂部。因為它的value值是42，所以調用putchar后打印出來的數字是2。

輸出42：

接著遞歸函數的這次調用也返回，它的變量也被銷毀，此時位于堆棧頂部的是遞歸函數再前一次調用的變量。遞歸調用從這個位置繼續執行，這次打印的數字是6。在這次調用返回之前，堆棧的內容如下：

輸出426：

現在我們已經展開了整個遞歸過程，并回到該函數最初的調用。這次調用打印出數字7，也就是它的value參數除10的余數。

輸出4267：

然后，這個遞歸函數就徹底返回到其他函數調用它的地點。
如果你把打印出來的字符一個接一個排在一起，出現在打印機或屏幕上，你將看到正確的值：4267
使用遞歸一定要有跳出的條件:
這是一個最簡單的遞歸, 不過它會一直執行, 可用 Ctrl+C 終止.

復制代碼代碼如下:

#include <stdio.h>
void prn(int num) {
    printf("%d/n", num);
    if (num > 0) prn(--num);  
}
int main(void)
{
    prn(9);
    getchar();
    return 0;
}

復制代碼代碼如下:

實例: 翻轉字符串
#include <stdio.h>
void revers(char *cs);
int main(void)
{
    revers("123456789");
    getchar();    
    return 0;
}
void revers(char *cs)
{
    if (*cs)
    { 
        revers(cs + 1);
        putchar(*cs);
    }
}

復制代碼代碼如下:

實例: 階乘
#include <stdio.h>
int factorial(int num);
int main(void)
{
    int i;
    for (i = 1; i <= 9; i++)
    printf("%d: %d/n", i, factorial(i));
    getchar();    
    return 0;
}
int factorial(int num)
{
    if (num == 1)
        return(1);
    else
        return(num * factorial(num-1));
}

復制代碼代碼如下:

實例: 整數到二進制
#include <stdio.h>
void IntToBinary(unsigned num);
int main(void)
{
    IntToBinary(255); /* 11111111 */
    getchar();
    return 0;
}
void IntToBinary(unsigned num) {
    int i = num % 2;
    if (num > 1) IntToBinary(num / 2);
    putchar(i ? '1' : '0'); 
//    putchar('0' + i);  /* 可代替上面一句 */
}

復制代碼代碼如下:

剖析遞歸:
#include <stdio.h>
void prn(unsigned n);
int main(void)
{
    prn(1);
    getchar();
    return 0;
}
void prn(unsigned n) {
    printf("%d: %p/n", n, &n);  /* A */
    if (n < 4) 
        prn(n+1);               /* B */
    printf("%d: %p/n", n, &n);  /* C */
}

例輸出效果圖:

分析:
程序運行到 A, 輸出了第一行.
此時 n=1, 滿足 < 4 的條件, 繼續執行 B 開始了自調用(接著會輸出第二行); 注意 n=1 時語句 C 還有待執行.
...如此循環, 一直到 n=4, A 可以執行, 但因不滿足條件 B 執行不了了; 終于在 n=4 時得以執行 C.
但此時內存中有四個函數都等待返回(分別是 n=1、2、3、4 時), 咱們分別叫它 f1、f2、f3、f4.
f4 執行 C 輸出了第五行, 函數返回, 返回給 f3(此時 n=3), f3 得以繼續執行 C, 輸出了第六行.
f3 -> f2 -> 繼續 C, 輸出了第七行.
f2 -> f1 -> 繼續 C, 輸出了第八行, 執行完畢!

如此看來, 遞歸函數還是很費內存的(有時不如直接使用循環), 但的確很巧妙.

上一篇：淺析C語言中sscanf 的用法

下一篇：深入C語言內存區域分配(進程的各個段)詳解