遞歸是一個非常重要的概念，但是并不是很好理解。

最常用的遞歸案例，就是求乘法的階乘，例如求n!的值。

n=1
n=1*2
n=1*2*3
n=1*2*3*4
...

這個乘法問題，是在前一個乘法的基礎上，再做乘法運算，也就是

fun(n)=fun(n-1) * n

這就是遞歸的公式，我們只要確定了fun()的實現，就能夠求出所有的值。

#include 


int fun(int n){
  if(n == 1) return 1;
  return fun(n-1) * n;
}


int main(){
  printf("%d\\n", fun(5));
  return 0;
}

在這個案例中，設n=5，他的執行過程如圖所示。

由外到里，再由里到外。

在設計遞歸算法的時候，需要注意，必須有出口條件，本案例中，階乘的出口條件是n=1的時候，乘積為1

再看一個案例，例如，要求一個復雜的多項式

F(1)=1，F(2)=1

F(n)=F(n-1)+F(n-2) n>2 求F(6) = ?

根據數學方程，實現起來也非常簡單

#include 


int f(int n){
  if(n == 1) return 1;
  if(n == 2) return 1;
  return f(n-1) + f(n-2);
}


int main(){
  printf("%d\\n", f(6));
  return 0;
}

執行過程如圖所示。

審核編輯：劉清