C語言遞歸

C語言函數可以自我調用。如果函數內部一個語句調用了函數自己，則稱這個函數是“遞歸”。遞歸是以自身定義的過程。也可稱為“循環定義”。
遞歸的例子很多。例如定義整數的遞歸方法是用數字1，2，3，4，5，6，7，8，9加上或減去一個整數。例如，數字15是7+8；數字21是9+12；數字12是9+3。
一種可遞歸的計算機語言，它的函數能夠自己調用自己。一個簡單的例子就是計算整數階乘的函數factor()數N的階乘是1到N之間所有數字的乘積。例如3的階乘是1×2×3，即是６。
factor()和其等效函數fact()如例4-10所示。

非遞歸函數fact()的執行應該是易于理解的。它應用一個從1開始到指定數值結束的循環。
在循環中，用“變化”的乘積依次去乘每個數。
factor()的遞歸執行比fact()稍復雜。當用參數1調用factor()時，函數返回1；除此之外的其它值調用將返回factor(n-1)*n這個乘積。為了求出這個表達式的值，用（n-1）調用factor()一直到n等于1，調用開始返回。
計算2的階乘時對factor()的首次調用引起了以參數1對factor()的第二次調用。這次調用返回1，然后被2乘（n的初始值），答案是2（把printf()語句插入到factor()中，察看各級調用及其中間答案，是很有趣的）。
當函數調用自己時，在棧中為新的局部變量和參數分配內存，函數的代碼用這些變量和參數重新運行。遞歸調用并不是把函數代碼重新復制一遍，僅僅參數是新的。當每次遞歸調用返回時，老的局部變量和參數就從棧中消除，從函數內此次函數調用點重新啟動運行?？蛇f歸的函數被說成是對自身的“推入和拉出”。
大部分遞歸例程沒有明顯地減少代碼規模和節省內存空間。另外，大部分例程的遞歸形式比非遞歸形式運行速度要慢一些。這是因為附加的函數調用增加了時間開銷（在許多情況下，速度的差別不太明顯）。對函數的多次遞歸調用可能造成堆棧的溢出。不過溢出的可能性不大，因為函數的參數和局部變量是存放在堆棧中的。每次新的調用就會產生一些變量的復制品。這個堆棧沖掉其它數據和程序的存儲區域的可能性是存在的。但是除非遞歸程序運行失控，否則不必為上述情況擔心。
遞歸函數的主要優點是可以把算法寫的比使用非遞歸函數時更清晰更簡潔，而且某些問題，特別是與人工智能有關的問題，更適宜用遞歸方法。遞歸的另一個優點是，遞歸函數不會受到懷疑，較非遞歸函數而言，某些人更相信遞歸函數。編寫遞歸函數時，必須在函數的某些地方使用if語句，強迫函數在未執行遞歸調用前返回。如果不這樣做，在調用函數后，它永遠不會返回。在遞歸函數中不使用if語句，是一個很常見的錯誤。在開發過程中廣泛使用printf()和getchar()可以看到執行過程，并且可以在發現錯誤后停止運行。

原文轉自：http://www.kjueaiud.com