函數(shù)與遞歸-3

本期是我們函數(shù)部分的最后一節(jié)，其實(shí)我們?cè)谏蟽晒?jié)已將函數(shù)的大致內(nèi)容介紹完畢了，本節(jié)我們主要來(lái)介紹遞歸的知識(shí)。由于本節(jié)知識(shí)點(diǎn)較少，而需要大家動(dòng)手操作的地方較多，我們主要以舉例子的方式來(lái)介紹，接下來(lái)我們開(kāi)始本期的學(xué)習(xí)。

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

• 函數(shù)遞歸

什么是遞歸？

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

遞歸的兩個(gè)必要條件

1.存在限制條件，當(dāng)滿足這個(gè)限制條件時(shí)，遞歸便不再繼續(xù)。

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

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

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

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

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

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

**例一：

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

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

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

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

我們接下來(lái)再看一個(gè)例子：

**例二：

【 在不創(chuàng)建臨時(shí)變量的情況下編寫一個(gè)函數(shù)求一字符串的長(zhǎng)度。】**

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

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

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

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

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

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

**例三：

【求n的階乘】**

這里我先使用迭代方式來(lái)編寫程序：

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

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

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

如上述代碼，我們僅用了一個(gè)if語(yǔ)句就完美地解決了問(wèn)題，而上述的迭代卻定義了兩個(gè)臨時(shí)變量加上使用了一個(gè)for循環(huán)才解決問(wèn)題，遞歸寫法的簡(jiǎn)潔性可見(jiàn)一斑了。

但并不是所有的代碼都適合用遞歸來(lái)寫，請(qǐng)看下面的例子：

**例四：

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

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

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

其實(shí)此問(wèn)題很好解決：

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)過(guò)測(cè)試，代碼是可以完成任務(wù)的，但當(dāng)我們想求第50個(gè)以上的斐波那契數(shù)時(shí)，我們會(huì)發(fā)現(xiàn)程序會(huì)運(yùn)算很長(zhǎng)時(shí)間，這時(shí)我們就會(huì)發(fā)現(xiàn)一個(gè)問(wèn)題：在使用迭代運(yùn)行程序時(shí)會(huì)造成計(jì)算力的大量浪費(fèi)，這時(shí)使用遞歸就不是明智之舉了，接下來(lái)我們使用迭代來(lái)編寫該代碼：

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

這樣程序就可以順利運(yùn)行了，我們這時(shí)就可以求可在int范圍內(nèi)存儲(chǔ)的任意斐波那契數(shù)了。

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