您好,登錄后才能下訂單哦!
這篇文章主要講解了“C語(yǔ)言函數(shù)的遞歸怎么調(diào)用”,文中的講解內(nèi)容簡(jiǎn)單清晰,易于學(xué)習(xí)與理解,下面請(qǐng)大家跟著小編的思路慢慢深入,一起來(lái)研究和學(xué)習(xí)“C語(yǔ)言函數(shù)的遞歸怎么調(diào)用”吧!
程序調(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è)必要條件:
存在限制條件,當(dāng)滿足這個(gè)限制條件的時(shí)候,遞歸便不再繼續(xù)。
每次遞歸調(diào)用之后越來(lái)越接近這個(gè)限制條件。
int main() { printf("hehe\n"); main(); return 0; }
函數(shù)自己調(diào)用自己,一直打印 “hehe” 但是一會(huì)程序自己會(huì)停下來(lái)。這不是真正的遞歸,是一個(gè)死循環(huán)(不滿住遞歸的兩個(gè)條件)
遞歸實(shí)現(xiàn):接收一個(gè)整型值(無(wú)符號(hào)),按照順序打印它的每一位。
例如:
輸入:1234
輸出:4321
void print(unsigned int n) { if (n > 9) { print(n / 10); } printf("%d", n % 10); } int main() { unsigned int num = 0; scanf("%u", &num); //遞歸-函數(shù)自己調(diào)用自己 print(num); return 0; }
基本的實(shí)現(xiàn)邏輯如圖:
寫(xiě)遞歸代碼的時(shí)候注意:
不能死遞歸,都有跳出條件,每次遞歸逼近跳出條件
遞歸層次不能太深(可能會(huì)棧溢出)
求第n個(gè)斐波那契數(shù),(可以遞歸實(shí)現(xiàn)也可以迭代實(shí)現(xiàn))(不考慮溢出)
我們知道像:1,1,2,3,5,8,13,21,34…… 這樣第n個(gè)數(shù)等于第n-1個(gè)數(shù)加上n-2個(gè)數(shù)的和的一個(gè)數(shù)列就是斐波那契數(shù)列
遞歸實(shí)現(xiàn)求斐波那契數(shù),直接看代碼:
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)我們求很小的斐波那契數(shù)時(shí),計(jì)算機(jī)計(jì)算很快。但是當(dāng)我們要求的一個(gè)很大的,比如第50個(gè)斐波那契數(shù),計(jì)算機(jī)就會(huì)算很久(大概要五分鐘)。大家可以試一試。
為什么會(huì)這么慢呢。因?yàn)檫f歸實(shí)現(xiàn)效率太低,要重復(fù)大量的計(jì)算(計(jì)算層次太多)。
代碼實(shí)現(xiàn)的基本邏輯如圖:
我們可以看一下代碼在計(jì)算過(guò)程中 n=3(計(jì)算第三個(gè)斐波那契數(shù)) 這一步要執(zhí)行的次數(shù):
在計(jì)算第40個(gè)斐波那契數(shù)時(shí),要計(jì)算三千多萬(wàn)次第三個(gè)斐波那契數(shù)??上攵f歸實(shí)現(xiàn)的效率有多低。而且計(jì)算太大還會(huì)造成程序崩潰。
循環(huán)迭代實(shí)現(xiàn)求斐波那契數(shù),直接看代碼:
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 c; } int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d\n", ret); return 0; }
循環(huán)迭代的方式計(jì)算很快
提示:
很多問(wèn)題是以迭代的形式進(jìn)行解釋的,這只是因?yàn)樗确沁f歸的形式更為清晰。
但是很多問(wèn)題的迭代實(shí)現(xiàn)往往比遞歸實(shí)現(xiàn)的效率更低。雖然代碼的可讀性稍微差些。
當(dāng)一個(gè)問(wèn)題相當(dāng)復(fù)雜時(shí),難以用迭代實(shí)現(xiàn)時(shí),此時(shí)遞歸實(shí)現(xiàn)的簡(jiǎn)潔性便可以補(bǔ)償它所帶來(lái)的運(yùn)行開(kāi)銷。
感謝各位的閱讀,以上就是“C語(yǔ)言函數(shù)的遞歸怎么調(diào)用”的內(nèi)容了,經(jīng)過(guò)本文的學(xué)習(xí)后,相信大家對(duì)C語(yǔ)言函數(shù)的遞歸怎么調(diào)用這一問(wèn)題有了更深刻的體會(huì),具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云,小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。