圖片來源於網絡

一開始你肯定覺得讀這句話好繞口，好費力。
其實你用遞迴來讀就很簡單了：
遞迴要有一個終點（小鯉魚）
當遞迴尚未達到終點的時候，函數會反覆呼叫自己。
顯然，輸出「我的小鯉魚」這句話是遞迴終止條件。
那麼寫成程式碼就是:

#include <stdio.h> void Recursion(int depth){ printf(“抱着”); if (!depth) printf(“我的小鲤鱼”); else Recursion(–depth); printf(“的我”); } int main(){ printf(“吓得我抱起了\n”); Recursion(2); putchar(’\n’); }

目前我找到的對遞迴最恰當的比喻，就是查字典。我們使用的字典，本身就是遞迴，為了解釋一個詞，需要使用更多的詞。當你查一個詞，發現這個詞的解釋中某個詞仍然不懂，於是你開始查這第二個詞，可惜，第二個詞裡仍然有不懂的詞，於是查第三個詞，這樣查下去，直到有一個詞的解釋是你完全能看懂的，那麼遞迴走到了盡頭，然後你開始後退，逐個明白之前查過的每一個詞，最終，你明白了最開始那個詞的意思。。。

箭頭線代表程式實際運行步驟。

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

• 什麼是遞迴？

1. 定義

**Wiki [1]：**Recursion is the process of repeating items in a self-similar way.

具體到電腦中去 [2]：

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

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

2. 跟迴圈的區別

單看上面wiki的定義，貌似跟通常所說的無限死迴圈很像，他們的區別在哪？

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

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

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

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

3. 遞迴思想

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

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

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

這篇博文[3]作者歸納為：

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

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

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

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

—-以上均來自網友回答