遞歸是一種強大的方法，它允許一個對象以其自身更小的形式來定義自己。

讓我們來觀察一下自然界中出現的遞歸現象：蕨類植物的葉子，每片葉子葉脈中的小分支都是整片葉子的較小縮影；又或者兩個反光的物體，相互映射對方漸遠的影像。這樣的例子使我們明白，盡管大自然的力量是強大的，在許多方面它那種出乎意料的簡潔更讓我們覺得優美。同樣的道理也可以用在遞歸算法上，從很多方面來說遞歸算法都是簡潔而優美的，而且非常強大。

在計算機科學領域中，遞歸是通過函數來實現的。遞歸函數是一種可以調用自身的函數。

基本遞歸

假設我們想計算整數n的階乘。n的階乘可能寫作n!，其結果是1~n之間的各數之積。比如，4!=4 x 3 x 2 x 1。一種方法是循環遍歷其中的每一個數，然后與它之前的數相乘作為結果再參與下一次計算。這種方法稱為迭代法，可以正式定義為：

n! = n(n-1)(n-2)...(1)

看待這個問題的另一種方式是將n!定義為更小的階乘形式。我們將n!定義為n-1階乘的n倍。再把(n-1)!定義為n-1倍的(n-2)!，(n-2)!看作(n-2)倍的(n-3)!，一直到n=1時，我們就計算完了。這就是遞歸的方式，可以正式定義為：

	1	如果 n=0,n=1
f(n)=
	nf(n)	如果 n>1

圖1： 以遞歸的方式計算4的階乘

上圖（1）展示了利用遞歸計算4！的過程。它也說明了遞歸過程中的兩個基本階段：遞推和回歸。在遞推階段，每一個遞歸調用通過進一步調用自己來記住這次遞歸過程。當其中有調用滿足終止條件時，遞推結束。比如，在計算n!時，終止條件是當n=1和n=0，此時函數只需簡單的返回1即可。每一個遞歸函數都必須擁有至少一個終止條件；否則遞推階段永遠不會結束了。一旦遞推階段結束，處理過程就進入回歸階段，在這之前的函數調用以逆序的方式回歸，直到最初調用的函數為止，此時遞歸過程結束。

以遞歸的方式計算n的階乘的函數實現：

C函數fact的工作方式如下：它接受一個整數n作為參數，如果n小于0，該函數直接返回0，這代表一個錯誤。如果n等于0或1，該函數返回1，這是因為0!和1!都等于1，以上是終止遞歸的條件。否則，函數返回n-1的階乘的n倍。而n-1的階乘又會以遞歸的方式再次調用fact來計算，如此繼續。

代碼實例（1）：fact.c

/*fact.c*/ #include "fact.h" int fact(int n){ if (n<0)return 0; else if(n==0)return 1; else if(n==1)return 1; else return n*f(n-1); }

為理解遞歸究竟是如何工作的，有必要先看看C語言中函數的執行方式。我們先來看看C程序在內存中的組織方式（見圖2-a）。基本上，一個可執行程序由4個區域組成：代碼段、靜態數據區、堆與棧。代碼段包含程序運行時所執行的機器指令。靜態數據區包含在程序生命周期內一直持久的數據，比如全局變量和靜態局部變量。堆包含程序運行時動態分配的存儲空間，比如malloc分配的內存。棧包含函數調用的信息。

當C中調用了一個函數時，棧中會分配一塊空間來保存與這個調用相關的信息。每一個調用都被當做是活躍的。棧上的那塊存儲空間稱為活躍記錄（見圖2-b），或稱為棧幀。棧幀由5個區域組成：輸入參數、返回值空間、計算表達式時用到的臨時存儲空間、函數調用時保存的狀態信息以及輸出參數。輸入參數是傳遞到活躍記錄中的參數；輸出參數是傳遞給在活躍記錄中調用的函數所使用的。一個活躍記錄中的輸出參數就成為棧中下一個活躍記錄的輸入參數。函數調用所產生的活躍記錄將一直存在于棧中直到這個函數調用結束。

圖2： a)? C程序在內存中的組織形式? b)? 一份活躍記錄

我們以示例fact.c為例，考慮一下當計算4!時棧中都發生了什么（見圖3）？初始調用fact會在棧中產生一個活躍記錄，輸入參數n=4。由于這個調用沒有滿足函數的終止條件，因此fact將繼續以n=3為參數遞歸調用。這將在棧上創建另一個活躍記錄，但這次輸入參數n=3。這里，n=3也是第一個活躍期中的輸出參數，因為正是在第一個活躍期內調用fact產生了第二個活躍期。這個過程將一直繼續，直到n的值變為1，此時滿足終止條件，fact將返回1。

圖3：遞歸計算4!時的C程序的棧

一旦n=1時的活躍期結束，n=2時的遞歸計算結果就是2X1=2，因而n=2時的活躍期也將結束，返回值為2。結果就是n=3時的遞歸計算結果表示為3X2=6，因此n=3時的活躍期結束，返回值為6。最終，當n=4時的遞歸計算結果將表示為6X4=24，n=4時的活躍期將結束，返回值為24。此時，函數已經從最初的調用中返回，遞歸過程結束。

棧是用來存儲函數調用信息的絕好方案。這正是由于其后進先出的特點精確滿足了函數調用和返回的順序。然而，使用棧也有一些缺點，棧維護了每個函數調用的信息直到函數返回后才釋放，這需要占用相當大的空間，尤其是在程序中使用了許多遞歸調用的情況下。除此之外，因為有大量的信息需要保存和恢復，因此生產和銷毀活躍記錄需要耗費一定的時間。如此一來，當函數調用的開銷變的很大時，我們就需要考慮應該采用迭代的方案。幸運的是，我們可以使用一種稱為尾遞歸的特殊遞歸方式來避免前面提到的這些缺點。

尾遞歸?

如果一上函數中所有遞歸形式的調用都出現在函數的末尾，我們稱這個遞歸函數是尾遞歸的。當遞歸調用是整個函數體中最后執行的語句且它的返回值不屬于表達式的一部分時，這個遞歸調用就是尾遞歸。

尾遞歸函數的特點是在回歸過程中不用做任何操作。

當編譯器檢測到一個函數調用是尾遞歸的時候，它就覆蓋當前的活躍記錄而不是在棧中去創建一個新的。編譯器可以做到這一點，因為遞歸調用是當前活躍期內最后一條待執行的語句，于是當這個調用返回時棧幀中并沒有其他事情可做，因此也就沒有保存棧幀的必要了。通過覆蓋棧幀而不是在其之上重新添加一個，這樣所使用的棧空間就大大縮減了，這使得實際的運行效率會變得更高。因此， 只要有可能我們就需要將遞歸函數寫成尾遞歸的形式。

回憶之前對計算n!的定義：在每個活躍期計算n倍的(n-1)!的值，讓n=n-1并持續這個過程直到n=1為止。這種定義不是尾遞歸的，因為每個活躍期的返回值都依賴于用n乘以下一個活躍期的返回值，因此每次調用產生的棧幀不得不保存在棧上直到下一個子調用的返回值確定。現在讓我們考慮以尾遞歸的形式來定義計算n!的過程。函數可以定義成如下形式：

	a	如果? n=0,n=1
f(n,a)=
	f(n-1,na)	如果? n>1

這種定義還需要接受第二個參數a，除此以外并沒有太大區別。a（初始化為1)維護遞歸層次的深度。這就避免了每次還需要將返回值再乘以n。而是在每次遞歸調用中令n=n-1并且a=na。繼續遞歸調用，直到n=1，這滿足結束條件，此時直接返回a即可。下圖（圖4）說明了用尾遞歸計算4!的過程。注意在回歸的過程中不需要做任何的操作，這是所有尾遞歸函數的標志。

圖4：以尾遞歸的方式計算4!

代碼實例（2）：facttail.c

facttail.c接受一個整數n并以尾遞歸的形式計算n的階乘。這個函數還接受一個參數a，a的初始值為1。函數使用a來維護遞歸層次的深度，除此之外它和fact很相似。

/*facttail.c*/ #include "facttail.h" int facttail(int n,int a) {if(n<0)return 0;else if(n==0)return 1;else if(n==1)return a;elsereturn facttail(n-1,n*a); } facttail.c函數是尾遞歸的，因為對facttail的單次遞歸調用是函數返回前最后執行的一條語句。但這并不是必需的，換句話說，在遞歸調用之后還可以有其他語句執行，只是它們只能在遞歸調用沒有執行時才可以執行。下圖(圖5)展示了當使用尾遞歸函數計算4!時棧的使用情況，我們可以和上面講的未使用尾遞歸時棧的使用情況作一下對比：

圖5：以尾遞歸形式計算4!時棧的使用情況

遞歸和反向計算

下面我們來考慮一個使用遞歸處理反序的問題（在這類問題中使用遞歸比使用循環更簡單）。

問題是這樣的，編寫一個函數將一個整數轉換成二進制形式。二進制的意思是指數值以2為底數進行表示。

解決上述問題，需要使用一個算法(algorithm)。因為奇數的二進制形式的最后一位一定是1，而偶數的二進制數的最后一位是0，所以可以通過5%2得出5的進制形式中最后一位數字是1或者是0。一般來講，對于數值n，其二進制數的最后一位是n%2，因此計算出的第一個數字恰好是需要輸出的最后一位。這就需要使用一個遞歸函數實現。在函數中，首先在遞歸調用之前計算n%2的數值，然后在遞歸調用語句之后進行輸出，這樣計算出的第一個數值反而在最后一個輸出。

為了得出下一個數字，需要把原數值除以2。這種計算就相當于在十進制下把小數點左移一位。如果此時得出的數值是偶數，則下一個二進制數是0；若得出的數值是奇數，則下一個二進制數是1.例如，5/2的數值是2（整數除法），所以下一位值是0。這時已經得到了數值01.重復以上計算，即使用2/2得出1，而1%2的數值是1，因此下一位數是1.這時得到的數值是101.那么何時停止這種計算呢？因為只要被2除的結果大于或等于2，那么就還需要一位二進制位進行表示，所以只有被2除的結果小于2時才停止計算。每次除以2就可以得出一位二進制位值，直到計算出最后一位為止。

代碼實例（3）：binary.c

/*binary.c --以二進制形式輸出整數*/ #include <stdio.h> void to_binary(unsigned long n); int main(void) {unsigned long number;printf("Enter an integer (q to quit): \n");while(scanf("%ul",&number)==1){printf("Binary equivalent: ");to_binary(number);putchar('\n');printf("Enter an integer (q to quit): \n");}printf("Done.\n");return 0; } void to_binary(unsigned long n)/*遞歸函數*/ {int r ;r = n%2;if(n>=2)to_binary(n/2);putchar('0'+r); /*以字符形式輸出*/return 0; }

示例程序中，如果r 是0，表達式‘0’+r就是字符‘0’；當r為1時，則該表達式的值為字符‘1’。得出這種結果的前提假設是字符‘1’的數值編碼比字符‘0’的數值編碼大1.ASCII和EBCDIC兩種編碼都滿足上述條件。更一般的方式，你可以使用如下方法：

putchar(r ? '1' : '0' );

當然，不使用遞歸也能實現這個算法。但是由于本算法先計算出最后一位的數值，所以在顯示結果之前必須對所有的數值進行存儲。

遞歸的優缺點

其優點是在于為某些編程問題提供了最簡單的方法，而缺點是一些遞歸算法會很快耗盡內存。同時，使用遞歸的程序難于閱讀和維護。從下面的例子，可以看出遞歸的優缺點。

斐波納契數列定義如下：第一個和第二個數字都是1，而后續的每個數字是前兩個數字之和。例如，數列中前幾個數字是1，1，2，3，5，8，13.下面我們創建一個函數，它接受一個正整數n作為參數，返回相應的斐波納契數值。

首先，關于遞歸深度，遞歸提供了一個簡單的定義。如果調用函數Fionacci（），當n為1或2時Fabonacci（n）應返回1；對于其他數值應返回Fibonacci（n-1)+Fabonacci(n-2) ：

代碼實例（4）

long Fabonacci(int n) {if(n>2)return Fibonacci(n-1)+Fibonacci(n-2);else return 1; }

這個C遞歸只是講述了遞歸的數學定義。同時本函數使用了雙重遞歸（double recursion）；也就是說，函數對本身進行了兩次調用。這就會導致一個弱點。

為了具體說明這個弱點，先假設調用函數Fibonacci（40）。第1級遞歸會創建變量n。接著它兩次調用Fibonacci（），在第2級遞歸中又創建兩個變量n。上述的兩次調用中的每一次又進行了再次調用，因而在第3級調用中需要4個變量n，這時變量總數為7.因為每級調用需要的變量數是上級的兩倍，所以變量的個數是以指數規律增長的！這種情況下，指數增長的變量數會占用大量內存，這就可能導致程序癱瘓。當然，以上是一個比較極端的例子，但它也表明了必須小心使用遞歸，尤其效率處于第一位時。

相關主題

遞歸樹：畫圖表能幫助我們形象地理解函數的調用順序。遞歸樹在形式上有所不同，展示遞歸計算階乘的圖1和圖4都是遞歸樹。遞歸樹最常用在包含兩個或更多個遞歸調用的函數中。

總結

以上是生活随笔為你收集整理的算法精解-C语言描述 递归和尾递归 （图解+实例）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。