很多人對遞歸的理解不太深刻。一直就停留在“自己調(diào)用自己”的程度上。這其實這只是遞歸的表象（嚴(yán)格來說連表象都概括得不全面，因為除了“自己調(diào)用自己”的遞歸外，還有交互調(diào)用的遞歸）。而遞歸的思想遠(yuǎn)不止這么簡單。

遞歸，并不是簡單的“自己調(diào)用自己”，也不是簡單的“交互調(diào)用”。它是一種分析和解決問題的方法和思想。簡單來說，遞歸的思想就是：把問題分解成為規(guī)模更小的、具有與原問題有著相同解法的問題。比如二分查找算法，就是不斷地把問題的規(guī)模變?。ㄗ兂稍瓎栴}的一半），而新問題與原問題有著相同的解法。

有些問題使用傳統(tǒng)的迭代算法是很難求解甚至無解的，而使用遞歸卻可以很容易的解決。比如漢諾塔問題。但遞歸的使用也是有它的劣勢的，因為它要進行多層函數(shù)調(diào)用，所以會消耗很多堆棧空間和函數(shù)調(diào)用時間。

既然遞歸的思想是把問題分解成為規(guī)模更小且與原問題有著相同解法的問題，那么是不是這樣的問題都能用遞歸來解決呢？答案是否定的。并不是所有問題都能用遞歸來解決。那么什么樣的問題可以用遞歸來解決呢？一般來講，能用遞歸來解決的問題必須滿足兩個條件：

• 可以通過遞歸調(diào)用來縮小問題規(guī)模，且新問題與原問題有著相同的形式。
• 存在一種簡單情境，可以使遞歸在簡單情境下退出。

如果一個問題不滿足以上兩個條件，那么它就不能用遞歸來解決。

為了方便理解，還是拿斐波那契數(shù)列來說下：求斐波那契數(shù)列的第N項的值。

這是一個經(jīng)典的問題，說到遞歸一定要提到這個問題。斐波那契數(shù)列這樣定義：f(0) = 0, f(1) = 1, 對n > 1, f(n) = f(n-1) + f(n-2)

這是一個明顯的可以用遞歸解決的問題。讓我們來看看它是如何滿足遞歸的兩個條件的：

1. 對于一個n>2, 求f(n)只需求出f(n-1)和f(n-2)，也就是說規(guī)模為n的問題，轉(zhuǎn)化成了規(guī)模更小的問題；
2. 對于n=0和n=1，存在著簡單情境：f(0) = 0, f(1) = 1。

因此，我們可以很容易的寫出計算費波納契數(shù)列的第n項的遞歸程序：

在編寫遞歸調(diào)用的函數(shù)的時候，一定要把對簡單情境的判斷寫在最前面，以保證函數(shù)調(diào)用在檢查到簡單情境的時候能夠及時地中止遞歸，否則，你的函數(shù)可能會永不停息的在那里遞歸調(diào)用了。