一．例子（用從C＋＋描述）：
行號 程序
0 p (int w)
1 {if（ w>o）
2 { cout<<w;
3 p(w-1);
4 p(w-1);
5 }
6 }
結束
執行語句 p(4) 後的打印結果：4 3 2 1 1 2 1 1 3 2 1 1 2 1 1
二．說明：
1．遞歸調用與普通的調用原理相同，只不過是每次調用的函數都是自己本身。
2．我們完全可以自己編程設置堆棧（用戶堆棧），來實現與“遞歸調用”相同的功能。
3． 3.在“遞歸調用”時，系統會自動設置和管理堆棧（系統堆棧），而
無需我們的干預，但這同時增加了“遞歸調用”的神秘性。為了更好
地 地理解“遞歸調用”，現將系統堆棧以表格的方式表示出來。
4．對於“堆棧”格式的一些說明
堆棧的格式為：
方格a
方格b
方格c
函數調用完返回的行號
調用的函數
W 的值
每調用一次函數就“入棧”一次；函數執行完了，就“出棧”一次
三．程序解釋：
1．開始調用p(4)，此時執行的語句有：1、2、3
結束
P(4)
4
執行p(4)的語句2：cout<<w;打印4（這是第一個結果）
但是由於語句3，在執行過程中還要調用p(3)，只有p(3)執行完了，才能繼續執行p(4)。
2．開始調用P(3)，此時執行的語句有：1、2、3
4
P(3)
3
結束
P(4)
4
當p（3）執行完了，就會執行p(4)中的語句4（所以在方格a中，填“4”）。
執行p(3)的語句2：cout<<w; 打印3（這是第二個結果）
同上面的情況相同，當執行到語句3，還要調用p(2)，只有p(2)執行完了，才能繼續執行p(3)。
3．開始調用P(2)，此時執行的語句有：1、2、3
4
P(2)
2
4
P(3)
3
結束
P(4)
4
執行p(2)的語句2：cout<<w;打印2（這是第三個結果）
同上面的情況相同，當執行到語句3，還要調用p(1)，只有p(1)執行完了，才能繼續執行p(2)。
4．開始調用P(1)，此時執行的語句有：1、2、3
4
P(1)
1
4
P(2)
2
4
P(3)
3
結束
P(4)
4
執行p(2)的語句2：cout<<w;打印1（這是第四個結果）
同上面的情況相同，當執行到語句3，還要調用p(0)，只有p(0)執行完了，才能繼續執行p(1)。
5．開始調用P(0)，此時執行的語句有：1
4
P(0)
0
4
P(1)
1
4
P(2)
2
4
P(3)
3
結束
P(4)
4
因為w＝0不滿足語句1，所以直接跳到語句5、6，從而p(0)執行完畢，p(0)要進行“出棧”操作。
6．此時執行的語句有：4
4
P(1)
1
4
P(2)
2
4
P(3)
3
結束
P(4)
4
由於p(0)執行完成，且p(0)的方格a中為4，因此繼續執行p(1)的語句4 ：p(w-1)； 又由於p(1)方格c中w值為1，所以調用p(0)。
7．開始調用p(0)
5
P(0)
0
4
P(1)
1
4
P(2)
2
4
P(3)
3
結束
P(4)
4
當p（0）執行完了，就會執行p(1)中的語句5（所以在方格a中，填“5”）。
因為w＝0不滿足語句1，所以直接跳到語句5、6，從而p(0)執行完畢，p(0)要進行“出棧”操作。
8．此時執行的語句有：5
4
P(1)
1
4
P(2)
2
4
P(3)
3
結束
P(4)
4
由於p(0)執行完成，且p(0)的方格a中為5，因此繼續執行p(1)的語句5 （最後一句），所以p(1)執行完畢，p(1)要進行“出棧”操作。
9．
4
P(2)
2
4
P(3)
3
結束
P(4)
4
由於p(1)執行完成，且p(1)的方格a中為4，因此繼續執行p(2)的語句4 ：p(w-1)； 又由於p(2)方格c中w值為2，所以調用p(1)。
10．開始調用P(1)，此時執行的語句有：1、2、3
5
P(1)
1
4
P(2)
2
4
P(3)
3
結束
P(4)
4
當p（1）執行完了，就會執行p(2)中的語句5（所以在方格a中，填“5”）。
執行p(1)的語句2：cout<<w;打印1（這是第五個結果）
當執行到語句3，還要調用p(0)，只有p(0)執行完了，才能繼續執行p(1)。
11．始調用P(0)，此時執行的語句有：1
4
P(0)
0
5
P(1)
1
4
P(2)
2
4
P(3)
3
結束
P(4)
4
因為w＝0不滿足語句1，所以直接跳到語句5、6，從而p(0)執行完畢，p(0)要進行“出棧”操作。
12．此時執行的語句有：4
5
P(1)
1
4
P(2)
2
4
P(3)
3
結束
P(4)
4
由於p(0)執行完成，且p(0)的方格a中為4，因此繼續執行p(1)的語句4 ：p(w-1)；又由於p(1)方格c中w值為1，所以調用p(0)。
13．開始調用p(0)
5
P(0)
0
5
P(1)
1
4
P(2)
2
4
P(3)
3
結束
P(4)
4
當p（0）執行完了，就會執行p(1)中的語句5（所以在方格a中，填“5”）。
因為w＝0不滿足語句1，所以直接跳到語句5、6，從而p(0)執行完畢，p(0)要進行“出棧”操作。
14．此時執行的語句有：5
5
P(1)
1
4
P(2)
2
4
P(3)
3
結束
P(4)
4
由於p(0)執行完成，且p(0)的方格a中為5，因此繼續執行p(1)的語句5 （最後一句），所以p(1)執行完畢，p(1)要進行“出棧”操作。
15．
4
P(2)
2
4
P(3)
3
結束
P(4)
4
由於p(1)執行完成，且p(1)的方格a中為5，因此繼續執行p(2)的語句5 （最後一句），所以p(2)執行完畢，p(2)要進行“出棧”操作。
注意：其實步驟10～15重復了步驟4～9,因為它們都調用的P(1)
16．
4
P(3)
3
結束
P(4)
4
由於p(2)執行完成，且p(2)的方格a中為4，因此繼續執行p(3)的語句4 ：p(w-1)； 又由於p(3)方格c中w值為3，所以調用p(2)。
17．開始調用P(2)，此時執行的語句有：1、2、3
5
P(2)
2
4
P(3)
3
結束
P(4)
4
當p（2）執行完了，就會執行p(3)中的語句5（所以在方格a中，填“5”）。
執行p(2)的語句2：cout<<w;打印2（這是第六個結果）
同上面的情況相同，當執行到語句3，還要調用p(1)，只有p(1)執行完了，才能繼續執行p(2)。
18．開始調用p(1)
省略……
注意：其實步驟17～29重復了3～15,因為它們都調用的P(2)
在這步驟中，又打印了2 1 1（見步驟3、4、10）
四．結論與分析：
步驟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
結果
4
3
2
1
1
2
1
1
3
2
1
1
2
1
1
第5個結果重復第4個結果，這是因為他們都調用了p(1)
第6、7、8個結果重復第3、4、5個結果，這是因為他們都調用了p(2)
第9～15個結果重復第2～8個結果，這是因為他們都調用了p(3)
