本期是我們函數部分的最后一節，其實我們在上兩節已將函數的大致內容介紹完畢了，本節我們主要來介紹遞歸的知識。由于本節知識點較少，而需要大家動手操作的地方較多，我們主要以舉例子的方式來介紹，接下來我們開始本期的學習。

本期我們主要學習函數遞歸相關的知識

• 函數遞歸

什么是遞歸？

程序調用自身的編程技巧稱為遞歸（recursion）。遞歸作為一種算法在程序設計語言中廣泛應用。一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來解決，遞歸策略只需少量的程序就可描述出解題過程所需的多次重復計算，大大地減少了程序的代碼量。遞歸的主要思考方式為：把大事化小

遞歸的兩個必要條件

1.存在限制條件，當滿足這個限制條件時，遞歸便不再繼續。

2.每次遞歸調用之后逐漸接近此限制條件。

所有函數遞歸都需要滿足上述兩個條件，否則函數就會出現問題，例如下面的程序：

int main()
{
  printf("hehe\\n");
  main ();//調用自身————遞歸
  return 0;
}

如果我們寫出了這樣的遞歸后去運行，我們就會發現程序報錯，且有關鍵詞**“stack overflow”**,這就是遞歸常見的錯誤 **“棧溢出” ** 。這里簡單地介紹一下什么是棧溢出。

我們在執行程序時需要向內存申請空間，空間主要被分成三部分：棧區，堆區，靜態區。在函數調用時是從棧區申請空間的，上述代碼由于“main”函數重復調用自身而沒有結束限制條件，違背了上面提到的遞歸的兩個條件，導致棧區空間被使用完，造成棧溢出。

用最通俗的話來說，如果我們前面講過的函數嵌套是一個函數調用另一個函數的話，那么函數遞歸就是函數通過自身調用來實現程序，下面我為大家舉幾個遞歸相關的例子

**例一：

【 接收一個整型值，按照順序打印它的每一位。】

** 例如：輸入1234，打印出1 2 3 4

#include 
void print(int n)//函數只是執行操作，不需要有返回值，所以返回值類型是“void”
{
  if(n>9)
  {
    print(n/10);//遞歸的具體實現
  }
  printf("%d ",n%10);
}
int main ()
{ 
  int a=0;
  scanf_s("%d",&a);
  print(a);//調用該函數
  return 0;
}

如此我們就成功地完成了任務，上述代碼“print”通過不斷調用自身來完成了打印整型值的任務，那我們看一下此遞歸是否滿足了我們上面提到的兩個必要條件，只要“n<9”,函數便不再遞歸，明顯滿足限制條件。

我們接下來再看一個例子：

**例二：

【 在不創建臨時變量的情況下編寫一個函數求一字符串的長度。】**

這道題可能剛入手有些發懵，我們先看一下在創建臨時變量是如何求字符串長度的:

#include 
int strlen(char* str)
{
  int count=0;//臨時變量
  while(*str != '\\0')
  {
    count++;
    str++;
  }
  return count;
}
int main()
{
  char arr[]="bit";
  int len=strlen(arr);
  printf("len=%d\\n",len);
  return 0;
}

上述代碼雖正確，但使用了臨時變量，接下來我們嘗試使用本節學習的遞歸知識來解決此問題：

int strlen(char* str)
{
  if(*str != '\\0');
  {
    return (1+strlen(str+1));//仔細體會此處遞歸的用法
  }
  else 
  return 0;
}
int main()
{
  char arr[]="bit";
  int len=strlen(arr);
  printf("len=%d\\n",len);
  return 0;
}

總而言之，遞歸其實就是函數通過調用自身來解決一些復雜的問題，它的原理非常簡單，但想熟練使用卻需要我們大量的練習。

在我們解決問題時，相較于不使用遞歸，遞歸的代碼量會顯得非常簡潔，接下來的例子為大家展示遞歸函數的簡潔性。

**例三：

【求n的階乘】**

這里我先使用迭代方式來編寫程序：

#include
int fac1(int x)
{
  int i=0;
  int ret=1;
  for(i=1;i<=x;i++)
  {
    ret=i*ret;
  }
  return ret;
}
int main()
{
   int a=0;
   scanf_s("%d",&a);
   int ret=fac1(a);
   printf("%d",ret);
   return 0;
}

上述代碼使用了迭代的形式來編寫代碼，所謂迭代，其實就是函數內部的循環結構。我們在編程時使用迭代也能解決問題，但單單從代碼的簡潔性上來說，迭代是遠遠比不上遞歸的。接下來我們使用遞歸來解決上述問題：

#include
int fac2(int x)
{
  if(x<=1)
  return (x*fac(x-1));
}
int main()
{
   int a=0;
   scanf_s("%d",&a);
   int ret=fac2(a);
   printf("%d",ret);
   return 0;
}

如上述代碼，我們僅用了一個if語句就完美地解決了問題，而上述的迭代卻定義了兩個臨時變量加上使用了一個for循環才解決問題，遞歸寫法的簡潔性可見一斑了。

但并不是所有的代碼都適合用遞歸來寫，請看下面的例子：

**例四：

【求第n個斐波那契數】**

所謂斐波那契數，就是從1，1開始，一個數等于前兩個數之和。

如 1，1，2，3，5，8，13，21......

其實此問題很好解決：

int fib(int n)
{
  if (n<=2)
    return 1;
  else
    return fib(n-1)+fib(n+1);
}
int main ()
{
  int a=0;
  int ret = 0;
  scanf_s("%d",&a);
  ret=fib(n);
  printf("%d ",ret);
  return 0;
}

經過測試，代碼是可以完成任務的，但當我們想求第50個以上的斐波那契數時，我們會發現程序會運算很長時間，這時我們就會發現一個問題：在使用迭代運行程序時會造成計算力的大量浪費，這時使用遞歸就不是明智之舉了，接下來我們使用迭代來編寫該代碼：

int fib(int n)
{
  int a=1;
  int b=1;
  int c=1;
  while(n>2)
  {
    c=a+b;
    a=b;
    b=c;
    n--;
  }
  return 0;
}
int main ()
{
  int a=0;
  int ret = 0;
  scanf_s("%d",&a);
  ret=fib(n);
  printf("%d ",ret);
  return 0;
}

這樣程序就可以順利運行了，我們這時就可以求可在int范圍內存儲的任意斐波那契數了。

到此，我們本節內容就結束了。遞歸和迭代這兩種方法各有利弊，我們要靈活使用，我們下期將繼續介紹C語言相關的知識。