C語言日記——遞歸

首先，允許我從《c primer plus》中摘一句話：C允許函數調用它自己，這種調用稱為遞歸。

有一段時間一直搞不清楚遞歸的實質，直到看到如下代碼：

#include

int up_and_down(int n);

int main() {

up_and_down(1);

return 0;

}

int up_and_down(int n)

{

printf("Level %d:n location %p\n",n,&n); // #1

if (n < 4) up_and_down(n +

1);

printf("LEVEL %d:n location %p\n",n,&n); // #2

return 0;

}

運行結果：

Level 1:n location 012FFB3C

Level 2:n location 012FFB2C

Level 3:n location 012FFB1C

Level 4:n location 012FFB0C

LEVEL 4:n location 012FFB0C

LEVEL 3:n location 012FFB1C

LEVEL 2:n location 012FFB2C

LEVEL 1:n location 012FFB3C

請按任意鍵繼續. . .

這個結果當你認識遞歸后就不會覺得有半點奇怪了。

想要真正搞懂遞歸，這段代碼值得上機推敲，最好用調試一步步看看程序的執行順序。

這里講下我的個人理解：

首先程序執行主函數main()，在里面調用up_and_down()函數(此時參數為n=1，記住在主函數中該函數只調用了一次，雖然這句話有點多余但我還是覺得有必要提醒)

接著進入了被調函數up_and_down()(這里的被調函數是相對main()而言)

在up_and_down()中，首先打印#1(看上面代碼注釋)

然后執行up_and_down(1+1)，即在up_and_down(1)中調用up_and_down(2)

在這里up_and_down(1)為up_and_down(2)的主調函數，后者則為前者的被調函數

記住這點就好理解了，我們都知道在一個函數中，調用另一個函數執行完以后要返回主調函數

即在up_and_down(1)中調用up_and_down(2)

在up_and_down(2)中調用up_and_down(3)

在up_and_down(3)中調用up_and_down(4)

直到up_and_down(4)打印完#1后不符合(n<4)停止調用，隨即跳過if語句直接打印#2

在這里會發現#2是第一次打印，因為在前面幾次調用中都還沒運行到打印#2這段代碼

重點來了，打印完#2后意味著up_and_down(4)調用完畢了，則按照上面說的調用完后返回主調函數

而up_and_down(4)的主調函數是up_and_down(3)

返回up_and_down(3)后程序繼續運行，在up_and_down(3)中打印#2(因為在之前up_and_down(3)調用了up_and_down(4)，未來得及運行打印#2)

up_and_down(3)打印#2后就等于up_and_down(3)調用完畢了，這里我們又要記住up_and_down(3)是在up_and_down(2)中被調用的，調用完后返回up_and_down(3)的主調函數up_and_down(2)

同理up_and_down(2)調用完后返回至up_and_down(1)，而up_and_down(1)才是真正的主函數main()的被調函數，up_and_down(1)執行完畢后返回至main()函數，main()函數再繼續執行剩下的代碼，這里是return

0；

啰嗦了那么多，其實第一遍看完可能還是捋不清，在這里需要記住，遞歸其實就是函數自己不斷調用自己，弄清楚遞歸完一層要返回哪一層，代碼的執行順序都是從上往下的，耐心點一步步看下去兩三遍后就會恍然大悟。

以上純為個人理解，如有錯誤希望指出，大家一起學習，共同進步！