柚子快報(bào)激活碼778899分享：C語(yǔ)言之函數(shù)遞歸
柚子快報(bào)激活碼778899分享：C語(yǔ)言之函數(shù)遞歸
一、什么是遞歸？
在C語(yǔ)言中，遞歸就是函數(shù)自己調(diào)用自己。例如：
#include
int main()
{
printf("hehe\n");
main();//main函數(shù)中又調(diào)用了main函數(shù)
return 0;
}
?上面代碼就是一個(gè)簡(jiǎn)單的遞歸程序，只不過(guò)上面的遞歸只是為了演示遞歸的基本形式，不是為了解決問(wèn)題，代碼最終也會(huì)陷入死循環(huán)，導(dǎo)致棧溢出（Stack overflow）。
每一次函數(shù)調(diào)用都會(huì)占用一塊內(nèi)存空間： 函數(shù)棧幀空間（運(yùn)行時(shí)堆棧）——在棧區(qū)上申請(qǐng)的空間
上面代碼算是遞歸，但是是一個(gè)錯(cuò)誤的釋放，這里導(dǎo)致棧溢出。
所以函數(shù)是不能這樣無(wú)限遞歸下去的，遞歸必須是有條件的！
1.遞歸的思想
遞歸的特點(diǎn)：使用少量的代碼，就能完成非常復(fù)雜的任務(wù)。
遞歸的思考方式是把大事化小的過(guò)程（把大型復(fù)雜的問(wèn)題拆分為小問(wèn)題，拆分到不能再拆為止）。
遞歸中的遞是遞推的意思，歸是回歸的意思。
2.遞歸的限制條件
有2個(gè)必要條件：
①遞歸存在限制條件，當(dāng)滿足這個(gè)限制條件時(shí)，遞歸便不再繼續(xù)。
②每次遞歸調(diào)用之后越來(lái)越接近這個(gè)限制條件。
二、遞歸舉例
舉例1.求n的階乘（不考慮溢出），0的階乘為0
Ⅰ.分析
n的階乘公式：n!=n*(n-1)!
舉例：5！=5*4*3*2*1
? ? ? ? ? ?4！=4*3*2*1
所以：5！=5*4！
這樣就把一個(gè)較大的問(wèn)題轉(zhuǎn)化為一個(gè)與原問(wèn)題相似，但規(guī)模較小的問(wèn)題來(lái)求解。
n的階乘的遞歸公式如下：?
Ⅱ.代碼實(shí)現(xiàn)
#include
int Fact(int n) //或int Fact(unsigned int n)
{
if (n == 0)
return 1;
else
return n * Fact(n - 1);
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fact(n);
printf("%d\n", ret);
return 0;
}
運(yùn)行結(jié)果不考慮n太大的情況，n太大存在溢出
分析：①這里遞歸的條件是：n>0,遞歸停下來(lái)的條件是：n=0
? ? ? ? ? ?②不斷接近跳出條件
Ⅲ.畫(huà)圖推演
舉例2.順序打印一個(gè)整數(shù)的每一位
輸入一個(gè)整數(shù)n，打印這個(gè)按照順序打印整數(shù)的每一位。
例如：? 輸入：1234? ?輸出：1 2 3 4
Ⅰ.分析
如果n是一位數(shù)，n的每一位就是n自己，如果n超過(guò)一位數(shù)，就得拆分每一位。
1234%10就得到4，然后1234/10就等到123，就相當(dāng)于去掉了4
然后繼續(xù)對(duì)123%10就得到了3，再除10就去掉了3，以此類推，不斷%10和/10，直到得到每一位
但是這樣得到的數(shù)字順序是倒著的。
?我們假設(shè)寫(xiě)一個(gè)函數(shù)Print打印n的每一位：
Print(1234)——>Print(123)? ? ? +4
???????????????????????????Print(12)? ? ? +3
???????????????????????????Print(1)? ? ? +2
Print(1234)可以拆分為兩步（其它類似）：
1.Print（1234/10）? ?//打印123的每一位
2.Print（1234%10） //打印4
Ⅱ.代碼實(shí)現(xiàn)
#include
void Print(int n)
{
if (n > 9)
{
Print(n / 10);
printf("%d ", n % 10);
}
else
{
printf("%d ", n % 10);
}
}
int main()
{
int n = 0;
scanf("%d", &n);
Print(n); //Print函數(shù)用來(lái)打印n的每一位
return 0;
}
簡(jiǎn)化一下：?
#include
void Print(int n)
{
if (n > 9)
{
Print(n / 10);
}
printf("%d ", n % 10);
}
int main()
{
int n = 0;
scanf("%d", &n);
Print(n); //Print函數(shù)用來(lái)打印n的每一位
return 0;
}
?分析：①遞歸的停止條件：n<=9
? ? ? ? ? ? ②n=n/10(每次都在接近停止條件)
Ⅲ.畫(huà)圖推演
三、遞歸與迭代
遞歸是一種很好的編程技巧，但也可能被誤用，就像遞歸舉例1一樣，看到推到的公式，很容易寫(xiě)成遞歸的形式：
int Fact(int n)
{
if(n==0)
return 1;
else
return n*Fact(n-1);
}
Fact函數(shù)可以產(chǎn)生正確的結(jié)果，但是在遞歸函數(shù)調(diào)用的過(guò)程中涉及一些運(yùn)行時(shí)的開(kāi)銷。
????????在C語(yǔ)言中每一次函數(shù)調(diào)用，都需要為本次函數(shù)調(diào)用在棧區(qū)申請(qǐng)一塊內(nèi)存空間來(lái)保存函數(shù)調(diào)用期間的各種局部變量的值，這塊空間被稱為運(yùn)行時(shí)堆棧，或者函數(shù)棧幀。
????????函數(shù)不返回，函數(shù)對(duì)應(yīng)的棧幀空間就?直占?，所以如果函數(shù)調(diào)?中存在遞歸調(diào)?的話，每?次遞歸函數(shù)調(diào)?都會(huì)開(kāi)辟屬于??的棧幀空間，直到函數(shù)遞歸不再繼續(xù)，開(kāi)始回歸，才逐層釋放棧幀空間。
????????所以如果采?函數(shù)遞歸的?式完成代碼，遞歸層次太深，就會(huì)浪費(fèi)太多的棧幀空間，也可能引起棧溢出（stack overflow）的問(wèn)題。
?所以如果不想使用遞歸就要想其他的辦法，通常是迭代的方式（通常是循環(huán)的方式）。
例如：計(jì)算n的階乘，也可以 產(chǎn)生1~n數(shù)字累計(jì)乘在一起。
#include
int Fact(int n)
{
int i = 0;
int ret = 1;
for (i = 1; i <= n; i++)
{
ret *= i;
}
return ret;
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fact(n);
printf("%d\n", ret);
return 0;
}
上面的代碼能完成任務(wù)，并且效率比遞歸的方式更好。
有時(shí)候，寫(xiě)一個(gè)代碼，雖然遞歸難以想到，但是使用遞歸寫(xiě)出的代碼會(huì)非常簡(jiǎn)單，往往一個(gè)代碼使用遞歸可能是幾行代碼，但是寫(xiě)成非遞歸（迭代）的方式，就是十幾行甚至幾十行代碼。因此遞歸實(shí)現(xiàn)的簡(jiǎn)潔性便可以補(bǔ)償它帶來(lái)的運(yùn)行時(shí)的開(kāi)銷。
如果遞歸的不恰當(dāng)書(shū)寫(xiě)，會(huì)導(dǎo)致一些無(wú)法接受的后果，那我們就要放棄使用遞歸，使用迭代的方式解決問(wèn)題！
舉例3：求第n個(gè)斐波那契數(shù)
求第n個(gè)斐波那契數(shù)是不適合使用遞歸求解的，但是斐波那契數(shù)的問(wèn)題是通過(guò)遞歸的形式描述的：
看到公式，我們很容易寫(xiě)成遞歸的形式：
#include
int Fib(int n)
{
if (n <= 2)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fib(n);
printf("%d\n", ret);
return 0;
}
當(dāng)我們輸入50時(shí)，需要很長(zhǎng)時(shí)間才能算出結(jié)果，這個(gè)計(jì)算所花費(fèi)的時(shí)間是我們難以接受的，這也說(shuō)明遞歸的寫(xiě)法是非常低效的，為什么呢？
其實(shí)遞歸程序會(huì)不斷展開(kāi)，在展開(kāi)的過(guò)程中，我們很容易就能發(fā)現(xiàn)，在遞歸的過(guò)程中會(huì)有重復(fù)計(jì)算，而且遞歸層次越深，冗余計(jì)算就會(huì)越多。
我們可以看到，在計(jì)算第40個(gè)斐波那契數(shù)的時(shí)候，使?遞歸?式，第3個(gè)斐波那契數(shù)就被重復(fù)計(jì)算了39088169次，這些計(jì)算是非常冗余的。所以斐波那契數(shù)的計(jì)算，使用遞歸是非常不明智的，我們就得想迭代的方式解決。
我們知道斐波那契數(shù)的前2個(gè)都是1，然后前2個(gè)數(shù)相加就是第3個(gè)數(shù)，那么我們從前往后，從小到大計(jì)算就行了。
#include
int Fib(int n)
{
int a = 1;
int b = 1;
int c = 1;
while (n >= 3)
{
c = a + b;
a = b;
b = c;
n--;
}
return c;
}
int main()
{
int n = 0;
scanf("%d", &n);
int c = Fib(n);
printf("%d\n", c);
return 0;
}
使用迭代的方式實(shí)現(xiàn)效率就會(huì)高很多。
有時(shí)候，遞歸雖好，但也會(huì)出現(xiàn)一些問(wèn)題，所以我們不要迷戀遞歸，適可而止就好。
柚子快報(bào)激活碼778899分享：C語(yǔ)言之函數(shù)遞歸
相關(guān)文章
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場(chǎng)。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
Americanas美洲跨境
