函數(shù)與遞歸-3

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

本期我們主要學習函數(shù)遞歸相關(guān)的知識

• 函數(shù)遞歸

什么是遞歸？

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

遞歸的兩個必要條件

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

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

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

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

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

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

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

**例一：

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

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

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

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

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

**例二：

【 在不創(chuàng)建臨時變量的情況下編寫一個函數(shù)求一字符串的長度?！?*

這道題可能剛?cè)胧钟行┌l(fā)懵，我們先看一下在創(chuàng)建臨時變量是如何求字符串長度的:

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

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

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

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

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

**例三：

【求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;
}

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

#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循環(huán)才解決問題，遞歸寫法的簡潔性可見一斑了。

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

**例四：

【求第n個斐波那契數(shù)】**

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

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

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

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范圍內(nèi)存儲的任意斐波那契數(shù)了。

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