本文將介紹遞歸的概念和簡(jiǎn)單的例子，希望能夠幫助讀者理解計(jì)算機(jī)中難以理解的遞歸。
1.什么是遞歸
通常我們寫出很多函數(shù)之后，這些函數(shù)是用來(lái)提供給其他地方調(diào)用完成一些事情的。比如我們有函數(shù)gcd用來(lái)計(jì)算兩個(gè)數(shù)的最小公約數(shù)。如果我們要計(jì)算三個(gè)數(shù)的最小公約數(shù)呢？我們可以寫一個(gè)新的函數(shù)gcd2，假設(shè)三個(gè)數(shù)為a,b,c，可以調(diào)用gcd(a,b)得到a和b的最小公約數(shù)ab,再調(diào)用gcd(ab,c)得到三者的最小公約數(shù)。這種函數(shù)之間的調(diào)用是很常見(jiàn)的一種情況，也是模塊化編程的一種體現(xiàn)。而遞歸就顯得比較“奇葩”，并且它的代碼也比較難看懂，因?yàn)樗奶攸c(diǎn)就是：我調(diào)用我自己。
當(dāng)你看到這樣的代碼時(shí)，你是否會(huì)懵逼呢？
int f(int n){
if(n == 0) return 0;
return n + f(n-1);
}
在函數(shù)f的里面竟然調(diào)用了函數(shù)f自己。要怎么理解這個(gè)代碼呢？其實(shí)，代碼在執(zhí)行的時(shí)候，我們每調(diào)用一個(gè)新的函數(shù)，都會(huì)被記錄起來(lái)，比如前面的例子，我們是先調(diào)用了gcd2，再調(diào)用了gcd，這個(gè)順序其實(shí)系統(tǒng)是會(huì)幫我們記錄保存在一個(gè)“棧”里面。當(dāng)我們的主程序調(diào)用f(4)的時(shí)候會(huì)發(fā)生以下的情況：
一開(kāi)始調(diào)用f(4)的時(shí)候，要返回給主程序的是 4 + f(3) ，但此時(shí)f(3)的值未知，需要繼續(xù)調(diào)用f(3)，f(3)要返回給f(4)的返回值是 3 + f(2)，f(2)又不知道，繼續(xù)調(diào)用f(2)。同樣，f(2)返回 2 + f(1)， f(1)返回 1 + f(0)。到了f(0)的時(shí)候，n == 0 的判斷條件終于為真了，直接返回 0。f(1)收到了 f(0)的值后，計(jì)算完1+0后把結(jié)果交回給f(2),f(2)又計(jì)算完結(jié)果之后交給f(3)，f(3)計(jì)算之后給f(4)，f(4)計(jì)算出最終結(jié)果給我們的主程序。我們可以發(fā)現(xiàn)最終這個(gè)程序完成工作是“計(jì)算1加到n的和”。像這樣一層一層的調(diào)用自身，其實(shí)就是遞歸，而代碼中對(duì)n是否為0的判斷，也叫做遞歸邊界，使得遞歸能夠及時(shí)停止。想一下，如果沒(méi)有遞歸邊界，在調(diào)用完f(0)之后，還會(huì)繼續(xù)調(diào)用f(-1),f(-2),f(-3)，并且永遠(yuǎn)不會(huì)停止，這個(gè)時(shí)候，由于系統(tǒng)保存調(diào)用層次信息的“棧”是有容量限制的，無(wú)限遞歸最終必定會(huì)導(dǎo)致“棧溢出”，也就是到達(dá)了系統(tǒng)能夠存儲(chǔ)的極限了，程序會(huì)報(bào)錯(cuò)退出。
2. 裴波那契數(shù)列
在計(jì)算機(jī)中有一個(gè)經(jīng)典的斐波那契數(shù)列，數(shù)列的前兩個(gè)數(shù)為1和1，之后每個(gè)數(shù)都是前兩個(gè)數(shù)之和。現(xiàn)在要我們求出第10個(gè)裴波那契數(shù)。我們可以拿紙算一算就出來(lái)了，比如我現(xiàn)在直接在大腦里算出前10個(gè)為：1,1,2,3,5,8,13,21,34,55,因此第10個(gè)數(shù)就是55。然而，求第10個(gè)數(shù)這個(gè)問(wèn)題也可以用遞歸來(lái)實(shí)現(xiàn)。要知道第10個(gè)數(shù)，我們首先要知道第8和第9個(gè)數(shù)，要知道第8個(gè)數(shù)，需要知道第6和第7個(gè)數(shù)……就這樣一直往前反推，初始條件反而變成了退出條件。并且，為了能夠反推，計(jì)算機(jī)利用一種稱為“?！钡臄?shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)遞歸過(guò)程中產(chǎn)生的數(shù)據(jù)。現(xiàn)在讓你在大腦里模擬遞歸的過(guò)程，先是f(10),再是f(8)和f(9)，要求f(8)需要f(6)和f(7)，要求f(6)需要f(4)和f(5)……是不是多來(lái)幾層你就暈了？這也是我們比較難以理解遞歸的一個(gè)原因，因?yàn)槲覀儧](méi)辦法完全模擬出遞歸中反推的過(guò)程。"遞歸的實(shí)現(xiàn)"難以理解，尤其是利用計(jì)算機(jī)語(yǔ)言實(shí)現(xiàn)遞歸。因?yàn)?，?shí)現(xiàn)是反過(guò)來(lái)的，不是讓你從初始條件推，而是反過(guò)來(lái)一直推到初始條件，初始條件反而變成了退出條件。
初學(xué)者需要了解好遞歸這個(gè)概念，利用遞歸我們能夠?qū)懗鲈S多優(yōu)雅的代碼，但是像“計(jì)算1加到n的和”，或者是“計(jì)算裴波那契數(shù)列”這樣的問(wèn)題，完全可以用for循環(huán)寫，甚至直接用公式就實(shí)現(xiàn)，速度反而會(huì)更快，畢竟系統(tǒng)幫我們保存調(diào)用過(guò)程的信息也需要時(shí)間和空間。
