很多人大一剛學(xué)C語(yǔ)言程序基礎(chǔ)設(shè)計(jì)的時(shí)候，一定會(huì)接觸到遞歸。那時(shí)候的你可能會(huì)懵逼抽象，理解后會(huì)贊不要太神奇，但實(shí)際在做題中不會(huì)用遞歸，不知道怎么用遞歸來(lái)解決問(wèn)題。
然而，遞歸算法是各路神仙鐘愛(ài)的算法，很多問(wèn)題如果能用遞歸模型簡(jiǎn)化，那么代碼寫(xiě)起來(lái)會(huì)異常的簡(jiǎn)單順暢，比如樹(shù)的前序后序中序，排序，以及漢諾塔問(wèn)題等，因?yàn)槿绻挥眠f歸，就要寫(xiě)很多行的循環(huán)代碼。幾乎所有的語(yǔ)言都繞不開(kāi)遞歸，他們都支持函數(shù)的自調(diào)用，通過(guò)調(diào)用自身來(lái)進(jìn)行遞歸，能夠簡(jiǎn)單明了闡明問(wèn)題。
遞歸是計(jì)算機(jī)科學(xué)中十分重要的概念，能用來(lái)解決很多科學(xué)難題。大都數(shù)編程書(shū)上的教材例子是費(fèi)波納契數(shù)
遞歸分為遞歸頭和遞歸體。遞歸頭就是什么時(shí)候不調(diào)用自身方法，如果沒(méi)有遞歸頭，將會(huì)現(xiàn)如死循環(huán)，也就是我們必須要設(shè)置停止條件。
遞歸體就是不斷調(diào)用自己的自身方法。
基本遞歸都能取代循環(huán)，只要你能把問(wèn)題用遞歸模型簡(jiǎn)化，雖然如此但是真正在項(xiàng)目中用遞歸的程序員往往會(huì)被人鞭笞，因?yàn)檫f歸在項(xiàng)目中要用之謹(jǐn)慎，代碼簡(jiǎn)潔的遞歸也有很大的副作用，而這些副作用缺點(diǎn)往往是致命性的。所以更多的時(shí)候在程序設(shè)計(jì)中不建議你用遞歸方法。
遞歸在效率上大部分場(chǎng)景都不是最佳的
遞歸是不斷調(diào)用函數(shù)自身，往往會(huì)消耗時(shí)間和空間。每一次調(diào)用，都得在內(nèi)存棧中分配空間以保存參數(shù)、返回地址以及臨時(shí)變量，而往棧中壓入數(shù)據(jù)和彈出數(shù)據(jù)都需要時(shí)間。有可能你這段代碼里有很多局部變量，這些變量的內(nèi)存在棧里，每遞歸一次，就要分配一次內(nèi)存，當(dāng)遞歸次數(shù)增加時(shí)，是非?？膳碌?。特別是申請(qǐng)大塊內(nèi)存時(shí)，往往占掉了CPU和內(nèi)存，導(dǎo)致進(jìn)程崩掉藍(lán)屏。
遞歸中很多計(jì)算都是重復(fù)的，由于其本質(zhì)是把一個(gè)問(wèn)題分解成兩個(gè)或者多個(gè)小問(wèn)題，多個(gè)小問(wèn)題存在相互重疊的部分，則存在重復(fù)計(jì)算，如fibonacci斐波那契數(shù)列的遞歸實(shí)現(xiàn)。
遞歸在性能上也不是最佳的，會(huì)造成極大的浪費(fèi)
調(diào)用?？赡軙?huì)溢出，其實(shí)每一次函數(shù)調(diào)用會(huì)在內(nèi)存棧中分配空間，而每個(gè)進(jìn)程的棧的容量是有限的，當(dāng)調(diào)用的層次太多時(shí)，就會(huì)超出棧的容量，從而導(dǎo)致棧溢出。所以說(shuō)，在一些內(nèi)存空間有限的場(chǎng)景，這是不被允許的。
這兩個(gè)特性，導(dǎo)致了遞歸的思想只能用于解決一些獨(dú)立的問(wèn)題，比如在一些獨(dú)立的場(chǎng)景里，在不考慮效率和性能的場(chǎng)合下，用來(lái)解決一些問(wèn)題。往往用遞歸的場(chǎng)景，基本就不安排其他的算法，專(zhuān)門(mén)會(huì)騰出比較大的空間給遞歸服務(wù)。
附：這里舉個(gè)例子，用遞歸來(lái)解決漢諾塔問(wèn)題。
（這部分由csdn部分版權(quán)聲明：本文為CSDN博主「bfhonor」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接及本聲明。原文鏈接：https://blog.csdn.net/qq_44096670/article/details/112003723）
漢諾塔問(wèn)題是
編程實(shí)現(xiàn)把 A 的 n 個(gè)盤(pán)子移動(dòng)到 C（盤(pán)子編號(hào)是 [1, n] ）
每次只能移動(dòng)1個(gè)盤(pán)子
大盤(pán)子只能放在小盤(pán)子下面
1、漢諾塔 — 1個(gè)盤(pán)子
2、漢諾塔 — 2個(gè)盤(pán)子
3、漢諾塔 — 3個(gè)盤(pán)子
看到這里你肯定知道了這個(gè)以前玩過(guò)的游戲，漢諾塔往往也是在acm練習(xí)題中必修的課。
漢諾塔 — 思路
其實(shí)分 2 種情況討論即可
（1）當(dāng) n == 1時(shí)，直接將盤(pán)子從 A 移動(dòng)到C
（2）當(dāng) n > 1時(shí)，可以拆分成3大步驟
①將 n– 1 個(gè)盤(pán)子從 A 移動(dòng)到B
② 將編號(hào)為 n 的盤(pán)子從 A 移動(dòng)到C
③將 n– 1 個(gè)盤(pán)子從 B 移動(dòng)到C
? 步驟①③ 明顯是個(gè)遞歸調(diào)用
運(yùn)行結(jié)果：將1號(hào)盤(pán)子從A移動(dòng)到C將2號(hào)盤(pán)子從A移動(dòng)到B將1號(hào)盤(pán)子從C移動(dòng)到B將3號(hào)盤(pán)子從A移動(dòng)到C將1號(hào)盤(pán)子從B移動(dòng)到A將2號(hào)盤(pán)子從B移動(dòng)到C將1號(hào)盤(pán)子從A移動(dòng)到C
