定義

英文定義:Recursion is the process of repeating items in a self-similar way.

具體到計(jì)算機(jī)中去：

遞歸：又稱為遞回,在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中,是指在函數(shù)的定義中使用函數(shù)自身的方法.

[以上定義來源為wiki].

英文的Recursion表達(dá)的是重復(fù)發(fā)生,再次重現(xiàn)的意思.而對(duì)應(yīng)的中文翻譯”遞歸”確表達(dá)了兩個(gè)意思:” 遞”+”歸”.這兩個(gè)意思,正是遞歸思想的精髓.

遞歸思想

遞歸的基本思想是：把規(guī)模大的問題轉(zhuǎn)化為規(guī)模小的相似的子問題來解決.這種思想與數(shù)學(xué)中的歸納法十分相近。

遞歸在程序中的表現(xiàn)：在函數(shù)實(shí)現(xiàn)遞歸時(shí),因?yàn)榻鉀Q大問題的方法和解決小問題的方法往往是同一個(gè)方法,所以就產(chǎn)生了函數(shù)調(diào)用它自身的情況.需要注意的是,遞歸函數(shù)必須有明顯的結(jié)束條件(base case),避免產(chǎn)生無限遞歸的情況.

經(jīng)典示例：N的階乘問題

??? 我們知道5!=5*4*3*2*1;4!=4*3*2*1;…

?????????? ?5!=5*4!...

??? 從上面我們可以歸納出N!=N*(N-1)!,由此函數(shù)的代碼如下：

public static long factorial(int n){if(n==1) // base casereturn 1;else // reduction stepreturn n*factorial(n-1);}

Base case:基線條件,遞歸的終止條件

Reduction step:遞歸操作,對(duì)問題的定義.

遞歸vs循環(huán)

???????? 從大多數(shù)情況來看,遞歸和循環(huán)是可以相互轉(zhuǎn)換的.例如上面的階乘問題,如果計(jì)算的階乘的方法是n!=n*(n-1)*….*2*1,就明顯是一個(gè)循環(huán)的過程,如果計(jì)算階乘的方法是n=n*(n-1)!,這就歸納出了一個(gè)遞歸定義。循環(huán)要求思考一個(gè)問題怎么做,而遞歸要求思考一個(gè)問題的定義（某Lisp開發(fā)者說的）.

???????? 實(shí)際開發(fā)中,循環(huán)更加常見,但有些情況下,可能需要將循環(huán)轉(zhuǎn)為遞歸(面試).遞歸與循環(huán)其實(shí)想通的地方挺多,它們都需要初始條件和終止條件.用遞歸解決循環(huán)問題,需要明確基線條件和定義遞歸問題(每一步遞歸操作的算法),本人在面試過程中遇到過一個(gè)這樣問題：求兩個(gè)數(shù)的最大公約數(shù),不使用循環(huán).其實(shí),從后面那句”不使用循環(huán)”就明顯是考遞歸的。Java代碼如下:

// 輾轉(zhuǎn)相除法求兩個(gè)數(shù)的最大公約數(shù)public static int gcd(int num1,int num2){// check argsif(num1==0 || num2==0){return 0;}// num1>num2int tmp = num1;num1 = Math.max(num1,num2);num2 = Math.min(tmp, num2);int p = num1%num2;/*while(p!=0){num1 = num2;num2 = p ;p = num1%num2;}*/if(p!=0)return gcd(num2,p);return num2;}

?

從上面可以看到,循環(huán)轉(zhuǎn)遞歸時(shí)要把握兩個(gè)點(diǎn)：

• 循環(huán)的終止條件與遞歸中的基線條件
• 循環(huán)中的算法與遞歸的算法

應(yīng)用

當(dāng)問題的定義本身就是遞歸形式的時(shí)候,可以考慮使用遞歸.數(shù)據(jù)結(jié)構(gòu)里面的“樹”就是典型的遞歸定義。還有如上面說的階乘,漢諾塔問題,斐波拉契數(shù)列等.都可以使用來遞歸解決問題.

使用遞歸可以使用緊湊和優(yōu)雅的代碼來解決看起來很”嚇人”的問題.但實(shí)際中,遞歸并不十分常見.首先,函數(shù)執(zhí)行過程中,棧空間的分配是有限的,如果遞歸的深度過大,就會(huì)造成棧空間的溢出.其次,遞歸提高了程序的書寫效率,但并不意味著執(zhí)行效率的提高.一般來說,遞歸的執(zhí)行效率未必比循環(huán)高,因?yàn)樵跅Ｉ祥_辟新空間、分配局部變量都是需要時(shí)間開銷的,特別是遞歸深度很大的時(shí)候。所以,學(xué)習(xí)遞歸主要是學(xué)習(xí)其思想—把規(guī)模大的問題轉(zhuǎn)化為規(guī)模小的相似子問題來解決。

借鑒知乎上某資深碼農(nóng)的一句話,個(gè)人覺得說的很好：

???????? 當(dāng)你的問題分析透徹，何時(shí)使用遞歸就會(huì)自然明了。遞歸只是一種函數(shù)調(diào)用的技巧，不是解決問題的公式。一個(gè)問題可以用遞歸做，也可以不用遞歸做，遞歸不是必須的。所以，理解你需要解決的問題，想清楚解決問題的步驟方法，你會(huì)突然發(fā)現(xiàn)，原來可以用遞歸來簡(jiǎn)化問題。不要一開始就想著如何用遞歸。

參考資料：

? ?http://zh.wikipedia.org/wiki/%E9%80%92%E5%BD%92

? ?http://www.zhihu.com/question/20507130

? ?http://www.zhihu.com/question/20096035

? ?http://www.ibm.com/developerworks/cn/linux/l-recurs.html

轉(zhuǎn)載于:https://www.cnblogs.com/heavenyes/p/3822663.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的浅谈递归的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。