阿珏酱

看了樓上很多答案，大多偏重於描述 遞迴 的現象，而沒說明為什麼要用遞迴，遞迴的思想到底是什麼。前陣子剛好看了點東西，試著整理下，如有錯誤之處，請不吝指正。

• 什麼是遞迴？

Wiki [1]： Recursion 是以自相似的方式重複項目的過程。

遞迴 （英語：Recursion），又譯為 迴歸 ，在數學與計算機科學中，是指在函數的定義中使用函數自身的方法。

英文的Recursion從詞源上分析只是"re- (again)" + "curs- （come, happen）" 也就是重複發生，再次重現的意思。而對應的中文翻譯 ”遞迴“ 卻表達了兩個意思：”遞“＋”歸“。這兩個意思，正是遞迴思想的精華所在。從這層次上來看，中文翻譯反而更達意。

2. 跟循環的區別

遞迴是靜中有動，有去有回。
循環是動靜如一，有去無回。

舉個例子，給你一把鑰匙，你站在門前面，問你用這把鑰匙能打開幾扇門。

遞迴：你打開面前這扇門，看到屋裡面還有一扇門（這門可能跟前面打開的門一樣大小（靜），也可能門小了些（動）），你走過去，發現手中的鑰匙還可以打開它，你推開門，發現裡面還有一扇門，你繼續打開，。。。， 若干次之後，你打開面前一扇門，發現只有一間屋子，沒有門了。你開始原路返回，每走回一間屋子，你數一次，走到入口的時候，你可以回答出你到底用這鑰匙開了幾扇門。

循環：你打開面前這扇門，看到屋裡面還有一扇門，（這門可能跟前面打開的門一樣大小（靜），也可能門小了些（動）），你走過去，發現手中的鑰匙還可以打開它，你推開門，發現裡面還有一扇門，（前面門如果一樣，這門也是一樣，第二扇門如果相比第一扇門變小了，這扇門也比第二扇門變小了（動靜如一，要麼沒有變化，要麼同樣的變化）），你繼續打開這扇門，。。。，一直這樣走下去。入口處的人始終等不到你回去告訴他答案。

3. 遞迴思想

遞迴就是有去（遞去）有回（歸來）。

具體來說，為什麼可以”有去“？
這要求遞迴的問題需要是可以用同樣的解題思路來回答類似但略有不同的問題（上面例子中的那把鑰匙可以開後面門上的鎖）。

為什麼可以”有回“？
這要求這些問題不斷從大到小，從近及遠的過程中，會有一個終點，一個臨界點，一個baseline，一個你到了那個點就不用再往更小，更遠的地方走下去的點，然後從那個點開始，原路返回到原點。

遞迴的基本思想是 把規模大的問題轉化為規模小的相似的子問題來解決 。在函數實現時，因為解決大問題的方法和解決小問題的方法往往是同一個方法，所以就產生了函數調用它自身的情況。另外這個解決問題的函數 必須有明顯的結束條件 ，這樣就不會產生無限遞迴的情況了。

4. 什麼時候需要用遞迴？

當有些問題的定義本身就是遞迴形式的時候，最是適合用遞迴來解決。

計算機專業的同學最最熟悉的莫過於” 樹 “的定義了[4,5]。還有一些定義，比如階乘，Fibonacci數列[6]，等等。用遞迴來解決這些問題，往往幾行代碼就搞定了一些看起來相當”嚇人“的問題。當然，遞迴的性能問題是另一回事，棧的分配，函數調用代價都是在具體工程實踐中要考慮的。但現在只是討論遞迴思想的話，不妨先放下那些，欣賞下遞迴的美。