C語言函數(shù)遞歸
前言
上章節(jié)講到C語言的函數(shù),詳細(xì)內(nèi)容請(qǐng)參見上章節(jié)。本章節(jié)主要是給大家介紹下C語言函數(shù)中的難點(diǎn)函數(shù)遞歸。
遞歸概念
在C語言中，函數(shù)調(diào)用可以從main（）函數(shù)，其他函數(shù)或同一函數(shù)本身進(jìn)行。遞歸函數(shù)定義如下：一個(gè)函數(shù)調(diào)用函數(shù)自身稱為遞歸函數(shù)。應(yīng)該非常小心地使用遞歸函數(shù)，因?yàn)楫?dāng)一個(gè)函數(shù)自己調(diào)用它進(jìn)入無限循環(huán)時(shí)。當(dāng)函數(shù)進(jìn)入無限循環(huán)時(shí)，函數(shù)執(zhí)行永遠(yuǎn)不會(huì)完成。我們應(yīng)該定義退出函數(shù)調(diào)用的條件，以便遞歸函數(shù)終止。當(dāng)一個(gè)函數(shù)被自己調(diào)用時(shí)，第一個(gè)調(diào)用仍在執(zhí)行中，直到調(diào)用最后一個(gè)調(diào)用。每次調(diào)用函數(shù)調(diào)用時(shí)，該函數(shù)都會(huì)將執(zhí)行控件返回到上一個(gè)函數(shù)調(diào)用。舉個(gè)
從階乘看遞歸
階乘是基斯頓·卡曼（Christian Kramp，1760～1826）于 1808 年發(fā)明的運(yùn)算符號(hào)，是數(shù)學(xué)術(shù)語。一個(gè)正整數(shù)的階乘（factorial）是所有小于及等于該數(shù)的正整數(shù)的積，并且0的階乘為1。自然數(shù)n的階乘寫作n!。1808年，基斯頓·卡曼引進(jìn)這個(gè)表示法。亦即n!=1×2×3×...×n。階乘亦可以遞歸方式定義：0!=1，n!=(n-1)!×n。
在上面的示例程序中，factorial（）函數(shù)調(diào)用是從main（）函數(shù)啟動(dòng)的，其值為3.在factorial（）函數(shù)內(nèi)，函數(shù)調(diào)用factorial（2），factorial（1）和factorial（0）被調(diào)用遞歸。在該程序執(zhí)行過程中，函數(shù)調(diào)用factorial（3）仍在執(zhí)行中，直到函數(shù)調(diào)用factorial（2），factorial（1）和factorial（0）的執(zhí)行完成。類似地，函數(shù)調(diào)用factorial（2）仍在執(zhí)行中，直到函數(shù)調(diào)用factorial（1）和factorial（0）的執(zhí)行完成。以相同的方式，函數(shù)調(diào)用factorial（1）保持執(zhí)行，直到函數(shù)調(diào)用factorial（0）的執(zhí)行完成。上述程序的完整執(zhí)行過程如下圖所示：
遞歸函數(shù)的優(yōu)點(diǎn)是定義簡(jiǎn)單，邏輯清晰。理論上，所有的遞歸函數(shù)都可以寫成循環(huán)的方式，但循環(huán)的邏輯不如遞歸清晰。使用遞歸函數(shù)需要注意防止棧溢出。在計(jì)算機(jī)中，函數(shù)調(diào)用是通過棧（stack）這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的，每當(dāng)進(jìn)入一個(gè)函數(shù)調(diào)用，棧就會(huì)加一層棧幀，每當(dāng)函數(shù)返回，棧就會(huì)減一層棧幀。由于棧的大小不是無限的，所以，遞歸調(diào)用的次數(shù)過多，會(huì)導(dǎo)致棧溢出?？梢栽囋噁actorial(1000)。
解決遞歸調(diào)用棧溢出的方法是通過尾遞歸優(yōu)化，事實(shí)上尾遞歸和循環(huán)的效果是一樣的，所以，把循環(huán)看成是一種特殊的尾遞歸函數(shù)也是可以的。尾遞歸是指，在函數(shù)返回的時(shí)候，調(diào)用自身本身，并且，return語句不能包含表達(dá)式。這樣，編譯器或者解釋器就可以把尾遞歸做優(yōu)化，使遞歸本身無論調(diào)用多少次，都只占用一個(gè)棧幀，不會(huì)出現(xiàn)棧溢出的情況。
可以看到，return fact_iter(n- 1, n* result)僅返回遞歸函數(shù)本身，n- 1和n* result在函數(shù)調(diào)用前就會(huì)被計(jì)算，不影響函數(shù)調(diào)用。尾遞歸調(diào)用時(shí)，如果做了優(yōu)化，棧不會(huì)增長(zhǎng)，因此，無論多少次調(diào)用也不會(huì)導(dǎo)致棧溢出。
尾言
使用遞歸函數(shù)的優(yōu)點(diǎn)是邏輯簡(jiǎn)單清晰，缺點(diǎn)是過深的調(diào)用會(huì)導(dǎo)致棧溢出。針對(duì)尾遞歸優(yōu)化的語言可以通過尾遞歸防止棧溢出。尾遞歸事實(shí)上和循環(huán)是等價(jià)的，沒有循環(huán)語句的編程語言只能通過尾遞歸實(shí)現(xiàn)循環(huán)。標(biāo)準(zhǔn)的解釋器沒有針對(duì)尾遞歸做優(yōu)化，任何遞歸函數(shù)都存在棧溢出的問題。
作業(yè):
漢諾塔的移動(dòng)可以用遞歸函數(shù)非常簡(jiǎn)單地實(shí)現(xiàn)。
請(qǐng)編寫move(n, a, b, c)函數(shù)，它接收參數(shù)n，表示3個(gè)柱子A、B、C中第1個(gè)柱子A的盤子數(shù)量，然后打印出把所有盤子從A借助B移動(dòng)到C的方法。
駿馬是跑出來的,強(qiáng)兵是打出來的。駕馭命運(yùn)的舵是奮斗。不抱有一絲幻想,不放棄一點(diǎn)機(jī)會(huì),不停止一日前進(jìn)腳步。
