C語言 函數(shù)與遞歸（其三）
本期是我們函數(shù)部分的最后一節(jié)，其實我們在上兩節(jié)已將函數(shù)的大致內(nèi)容介紹完畢了，本節(jié)我們主要來介紹遞歸的知識。由于本節(jié)知識點較少，而需要大家動手操作的地方較多，我們主要以舉例子的方式來介紹，接下來我們開始本期的學(xué)習(xí)。
??本期我們主要學(xué)習(xí)函數(shù)遞歸相關(guān)的知識
函數(shù)遞歸
?什么是遞歸？
???程序調(diào)用自身的編程技巧稱為遞歸（recursion）。遞歸作為一種算法在程序設(shè)計語言中廣泛應(yīng)用。一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來解決，遞歸策略只需少量的程序就可描述出解題過程所需的多次重復(fù)計算，大大地減少了程序的代碼量。遞歸的主要思考方式為：把大事化小
遞歸的兩個必要條件
1.存在限制條件，當(dāng)滿足這個限制條件時，遞歸便不再繼續(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ù)重復(fù)調(diào)用自身而沒有結(jié)束限制條件，違背了上面提到的遞歸的兩個條件，導(dǎo)致棧區(qū)空間被使用完，造成棧溢出。
? ?用最通俗的話來說，如果我們前面講過的函數(shù)嵌套是一個函數(shù)調(diào)用另一個函數(shù)的話，那么函數(shù)遞歸就是函數(shù)通過自身調(diào)用來實現(xiàn)程序，下面我為大家舉幾個遞歸相關(guān)的例子
例一：
? ?【?接收一個整型值，按照順序打印它的每一位?！?br/>? 例如：輸入1234，打印出1 2 3 4
#include?<stdio.h>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;}
? ? 如此我們就成功地完成了任務(wù)，上述代碼“print”通過不斷調(diào)用自身來完成了打印整型值的任務(wù)，那我們看一下此遞歸是否滿足了我們上面提到的兩個必要條件，只要“n<9”,函數(shù)便不再遞歸，明顯滿足限制條件。
? ?我們接下來再看一個例子：
例二：
?【 在不創(chuàng)建臨時變量的情況下編寫一個函數(shù)求一字符串的長度?！?/strong>
? ? 這道題可能剛?cè)胧钟行┌l(fā)懵，我們先看一下在創(chuàng)建臨時變量是如何求字符串長度的:
#include <stdio.h>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é)學(xué)習(xí)的遞歸知識來解決此問題：
int?strlen(char*?str){??if(*str?!=?'\0');??{????return?(1+strlen(str+1));//仔細(xì)體會此處遞歸的用法??}??else ??return 0;}int main(){??char arr[]="bit"; ?int len=strlen(arr); ?printf("len=%d\n",len); ?return 0;}
? ?總而言之，遞歸其實就是函數(shù)通過調(diào)用自身來解決一些復(fù)雜的問題，它的原理非常簡單，但想熟練使用卻需要我們大量的練習(xí)。
? ?在我們解決問題時，相較于不使用遞歸，遞歸的代碼量會顯得非常簡潔，接下來的例子為大家展示遞歸函數(shù)的簡潔性。
例三：
? ?【求n的階乘】
? ?這里我先使用迭代方式來編寫程序：
#include<stdio.h>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)。我們在編程時使用迭代也能解決問題，但單單從代碼的簡潔性上來說，迭代是遠(yuǎn)遠(yuǎn)比不上遞歸的。接下來我們使用遞歸來解決上述問題：
#include<stdio.h>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)過測試，代碼是可以完成任務(wù)的，但當(dā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)的知識。
