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

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

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

這個(gè)乘法問題，是在前一個(gè)乘法的基礎(chǔ)上，再做乘法運(yùn)算，也就是

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

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

#include 


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


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

在這個(gè)案例中，設(shè)n=5，他的執(zhí)行過程如圖所示。

由外到里，再由里到外。

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

再看一個(gè)案例，例如，要求一個(gè)復(fù)雜的多項(xiàng)式

F(1)=1，F(xiàn)(2)=1

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

根據(jù)數(shù)學(xué)方程，實(shí)現(xiàn)起來也非常簡單

#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;
}

執(zhí)行過程如圖所示。

審核編輯：劉清