圖解遞迴
遞迴可能是大多數程式設計初學者的第一道大坎，它本身並不困難，但是因為執行方式略微特別而一時摸不到頭腦，其實適應了之後用起來也能得心應手，並且能更加方便的解決許多單純用迴圈較難解決的問題。
很多講述遞迴的文章中，把分析遞迴問題放在了第一位，著重講解了分析遞迴問題，找出結束條件，遞迴關係等，但是忽略了程式本身的執行方式，在我看來分析問題與程式執行過程一樣重要，兩者缺一不可，只會分析問題，很容易寫出有BUG的程式，同時也不易深入理解，只理解遞迴執行過程，不會分析問題，那就是紙上談兵，實際上也什麼都沒學到。
這篇文章重點在於幫助理解遞迴程式本身的執行過程，其實遞迴函式和普通函式的呼叫並沒有什麼區別，所以先理解普通函式的呼叫，再理解遞迴就不難了。
舉個例子，一個普通的呼叫
void
funC
（）
{
puts
（
“funC”
）；
}
void
funB
（）
{
funC
（）；
puts
（
“funB”
）；
}
void
funA
（）
{
funB
（）；
puts
（
“funA”
）；
}
假如呼叫函式funA，那麼它就會呼叫函式funB，funB再呼叫funC，funC打印出“funC”，此時funC執行完畢返回至funB繼續執行，打印出“funB”，然後funB執行完畢返回至funA，funA列印“funA”，執行完畢，執行結果如圖所示。
可以看出來，每次呼叫一次函式，都是等它徹底執行完畢之後，才會返回去繼續執行，那麼如果將每個函式“展開”，大概就像這樣
每一個大框代表一次函式呼叫，這樣可以很直觀的看出程式執行過程（按圖從上至下即可）。“每呼叫一次函式，都是等它徹底執行完畢之後，才會返回去繼續執行”這句話的含義，體現在圖中就是一個框被整個包裹在另一個框之中。
其實遞迴也是如此，從根本上來說，遞迴呼叫其實呼叫的並不是本身，你寫在程式裡的一個函式，呼叫它其實並不是真的執行了它，而是開闢了一份空間，把其中的資料（包括引數，和函數里的一些變數等），存在其中，然後根據你寫的程式碼去修改這些資料，每次呼叫一個函式，就會開闢一份這樣的空間，執行完畢之後釋放，而遞迴的時候，每一次遞迴呼叫都會開闢一份這樣的空間，互相獨立，所以才有本段開頭的一句話，所以，如果一次遞迴呼叫共呼叫了N次，你就可以理解為你寫了N個函式，只不過它們長得一樣罷了。
舉個例子，經典的遞迴求階乘，如果我們想要算出n！，只需要先算出（n-1）！再乘n就可以了（遞迴求階乘其實是相當差的一個方法，這裡僅做舉例）：
int
fact
（
int
n
）
{
if
（
n
==
0
）
return
1
；
else
return
fact
（
n
-
1
）
*
n
；
}
fact（4）的執行過程如下：
當計算fact（1）時，就是先算出了fact（0）=1，然後才能知道fact（1）是1*1=1。
當計算fact（2）是，也是先算出了fact（1）=1，然後才能知道fact（2）是1*2=2。
其他也類似。
從圖中還可以看出來，每一次遞迴呼叫，都是徹底執行完這一次呼叫，才會返回（經過一個函式框的下邊框就意味著返回了）。
再舉一個例子，經典的河內塔問題：有三根柱子，編號分別是A，B，C，A柱子上有N個空心圓盤，圓盤大小互不相同，且最下面的最大，最上面的最小，由下向上大小遞減放置，現在你需要把所有的圓盤移動至C柱子上，移動過程中每次只能挪動一個圓盤，且這個圓盤必須處於一個柱子的最上端，並且時刻保證大圓盤不能位於小圓盤的上面，求一個挪動方案，且該方案步數最少。
乍一看，這個問題似乎十分困難，但利用遞迴的思想可以輕易解決：
首先，我們用一個這樣的二元組
定義一個函式f（n，x，y，z），它會輸出把n個圓盤從柱子x挪到柱子z上的方案，y柱子充當中轉站，該問題只需要呼叫f（N，‘A’，‘B’，‘C’）即可解決。
顯然，如果最大圓盤固定位置不動，那麼它對其他圓盤的挪動沒有影響，於是，N-1個盤子的挪動其實就是這個問題本身，只不過規模小了1，寫成程式碼就是：
void
f
（
int
n
，
char
x
，
char
y
，
char
z
）
{
if
（
n
==
0
）
return
；
//沒有盤子需要挪動，直接返回
f
（
n
-
1
，
x
，
z
，
y
）；
//最大的盤子要挪到z上，上面的n-1個挪到y上給最大的圓盤讓路
printf
（
“<%c，%c>
\n
”
，
x
，
z
）；
//挪動最大的盤子
f
（
n
-
1
，
y
，
x
，
z
）；
//再把那n-1個從y上挪到z上
}
以上程式碼寫起來較為簡潔自然，但是不利於圖解（因為圖會很囉嗦，平白多出一層），圖解時應用以下程式碼
void f（int n，char x，char y，char z）
{
if（n==1）
{
printf（“<%c，%c>\n”，x，z）； //只有一塊圓盤，直接挪動即可
return；
}
f（n-1，x，z，y）； //最大的盤子要挪到z上，上面的n-1個挪到y上給最大的圓盤讓路
printf（“<%c，%c>\n”，x，z）； //挪動最大的盤子
f（n-1，y，x，z）； //再把那n-1個從y上挪到z上
}
這段程式碼跟上面的程式碼沒有本質區別，只不過結束條件從沒有盤子，變成了剩一個盤子。
上圖為兩個盤子的挪動方案
上圖為三個盤子的挪動方案