前面講了函數呼叫，那麼函數到底是如何呼叫的？
函數呼叫是通過棧實現的。在呼叫函數時，系統會將被調函數所需的程式空間安排在一個棧中。每當呼叫一個函數時，就在棧頂為它分配一個儲存區。每當從一個函數退出時就釋放它的儲存區。
也就是說，當前正在執行的函數的儲存區是在棧頂的。因為棧是
先進後出的（或者說是
後進先出的），所以當有多個函數巢狀呼叫時，會按照先呼叫後返回的原則（或者說是後呼叫先返回的原則）進行返回。
遞回也是一種函數呼叫，只不過是函數自己呼叫自己，是一種特殊的函數呼叫，呼叫自己同呼叫別人是一模一樣的。
因為遞回也是函數呼叫，所以遞回也是用棧實現的。下面來寫一個程式，看看函數是如何自己呼叫自己的：
# include <stdio.h>
void Func(int n); //函數宣告
int main(void)
{
int n;
printf("想輸出幾個我愛你:");
scanf("%d", &n);
Func(n);
return 0;
}
void Func(int n)
{
if (n > 0)
{
printf("i love youn");
Func(n-1);
}
else
{
return ;
}
}
輸出結果是：
想輸出幾個我愛你:5
i love you
i love you
i love you
i love you
i love you
這就是“自己呼叫自己”。從這個程式可以看出，自己呼叫自己必須要滿足一個條件，就是必須要知道什麼時候結束呼叫。不然函數就會一直不停地呼叫，造成“死遞回”。
死遞回，
是指遞回的時候沒有出口，不知道什麼時候停下來，不停地自己呼叫自己，直到棧滿沒有地方放了為止。這時計算機也宕機了（除了這個條件之外還有另外一個條件，後續再講）。
使用遞迴必須要滿足的兩個條件
並不是所有的問題都能用遞迴解決。要使用遞迴就必須要具備兩個條件。
遞迴的思想是：為了解決當前問題 F(n)，就需要解決問題 F(n–1)，而 F(n–1) 的解決依賴於 F(n–2) 的解決……就這樣逐層分解，分解成很多相似的小事件，當最小的事件解決完之後，就能解決高層次的事件。這種“逐層分解，逐層合併”的方式就構成了遞迴的思想。
使用遞迴最主要的是要找到遞回的出口和遞迴的方式。所以遞回通常分為兩部分：
遞迴的方式和
遞迴的終止條件（最小事件的解）。這兩個部分是遞迴的關鍵！
遞迴的方式，就是指遞迴公式，即對問題的分解，同時也是向遞回終止條件收斂的規則。而遞迴的終止條件通常就是得出的最小事件的解。遞回終止條件的作用就是不讓遞回無限地進行下去，最後必須要能“停”下來。
綜上所述，使用遞迴必須要滿足的兩個條件就是：
如何學習遞回
大多數人在學習遞回的時候一般都會有一個問題，“怎麼知道什麼時候可以用遞迴，什麼時候不可以用遞迴？”
很多人在學習遞回的時候都會有這個困惑。雖然遞迴的思想也掌握了，也知道使用遞迴必須要具備兩個條件，但就是不會用，無法用遞迴解決新的問題。
那麼到底怎麼知道一個問題是否可以用遞迴解決呢？其實，一個問題是否可以用遞回來解決，這是一個數學問題，這個問題不需要我們考慮，換句話說，不要去考慮一個問題能不能用遞迴解決，我們所要做的就是掌握那些已知的、非常經典的遞迴演算法。
遞回和迴圈的關係
遞回和迴圈存在很多關係。理論上講，所有的迴圈都可以轉化成遞回，但是利用遞迴可以解決的問題，使用迴圈不一定能解決。比如編寫樹和圖的程式就必須用遞迴，雖然迴圈也可以實現，但那樣做絕對是程式設計師的噩夢。
迴圈又稱
疊代。遞迴演算法與疊代演算法設計思路的主要區別在於：函數或演算法是否具備收斂性！當且僅當一個演算法存在預期的收斂效果時，採用遞迴演算法才是可行的。否則就不能使用遞迴演算法。所謂收斂性就是指要有終止條件，不能無休止地遞迴下去。
遞回的優缺點
遞回的優點是簡化程式設計，結構簡潔清晰，容易程式設計，可讀性強，容易理解。在很多情況下使用遞迴是必要的，它往往能把複雜問題分解為更簡單的步驟，而且能夠反映問題的本質。我們一開始可能發現遞回理解起來也不容易，這是因為我們的“見識”太少了！等將來學習樹和圖的時候你才能真正領會到遞回是多麼的“好理解”！
又比如漢諾塔，用遞迴的話基本上可以理解，但是如果不用遞迴而用回圈的話，程式根本不知道從何處著手！
但是
遞回的缺點也很明顯：速度慢，執行效率低，對儲存空間的佔用比迴圈多。嚴格講，迴圈幾乎不浪費任何儲存空間，而遞回浪費的空間實在是太大了，而且速度慢。
因為遞回是用棧機制實現的，每深入一層都要佔用一塊棧資料區域。對巢狀層數深的一些演算法，遞回就會顯得力不從心，最後都會以記憶體崩潰而告終。而且遞回也帶來了大量的函數呼叫，這也有許多額外的時間開銷。函數呼叫要傳送實參，要為被調函數分配儲存空間，還要儲存返回的值，又要釋放空間並將值返回給主調函數，這些都太浪費空間和時間。
雖然遞回有那麼多缺點，但是沒有辦法，有些問題太複雜，不用遞迴就解決不了！
與遞回相比，迴圈的缺點是不容易理解，遇複雜問題時編寫困難。但它的優點是速度快、效率高、不浪費空間。迴圈的執行時間只因迴圈次數增加而增加，沒有其他額外開銷，空間上同樣。
對於初學者而言，我們所遇到的遞迴演算法一般都比較簡單，能用遞迴解決的一般都能用迴圈解決，所以初學程式設計的時候大家不要總想著使用遞迴。
下面給大家編寫幾個程式，列舉幾個例子，主要通過例子讓大家對遞回有一個了解。
1) 用遞迴求 n 的階乘。
n！也可以寫成 n×(n–1)！，這就是遞迴公式。
# include <stdio.h>
long Factorial(int n); //函數宣告
int main(void)
{
int n;
printf("請輸入n的值:");
scanf("%d", &n);
printf("%d! = %ldn", n, Factorial(n));
return 0;
}
long Factorial(int n) //階乘的英文為factorial
{
if (n < 0)
{
return -1;
}
else if (0==n || 1==n) /*關係運算子的優先順序大於邏輯運算子的優點級, 所以不用加括號*/
{
return 1;
}
else
{
return n * Factorial(n-1);
}
}
輸出結果是：
請輸入n的值:10
10! = 3628800
n 的值不要太大，不然容易溢位，long 型別也放不下。
2) 用遞迴實現 1+2+3+…+100 的和
求和的遞迴公式跟求階乘的遞迴公式很相似：Sum(n)=n+Sum(n–1)。
# include <stdio.h>
int Sum(int n); //函數宣告
int main(void)
{
int n;
printf("請輸入n的值:");
scanf("%d", &n);
printf("sum = %dn", Sum(n));
return 0;
}
int Sum(int n)
{
if (n <= 0)
{
return -1;
}
else if (1 == n)
{
return 1;
}
else
{
return n+Sum(n-1);
}
}
輸出結果是：
請輸入n的值:100
sum = 5050
3) 用遞迴求斐波那契數列。
所謂斐波那契數列是指數列中每一個數值都是其前兩個數值之和，即：
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368……
# include <stdio.h>
long Fibonacci(int n); //函數宣告
int main(void)
{
int n;
printf("請輸入n的值:");
scanf("%d", &n);
printf("第n項的值為：%ldn", Fibonacci(n));
return 0;
}
long Fibonacci(int n)
{
if (n < 0)
{
return -1;
}
else if (0 == n)
{
return 0;
}
else if (1 == n)
{
return 1;
}
else
{
return Fibonacci(n-1)+Fibonacci(n-2);
}
}
輸出結果是：
請輸入n的值:21
第n項的值為：10946
通過上面這幾個程式我們發現遞迴都有一個共同的特點，就是遞迴公式全部都是寫在 return 語句後面的，而且最小事件的解都會返回一個具體的值。如果最小事件的解不返回一個具體值的話，那麼遞回就無法停下來。