在我告訴你什么是遞歸之前，你應(yīng)該讀一下這篇文章：遞歸，遞歸，遞歸。

如果你沒有這么做，那么表揚(yáng)一下自己。如果你那么做了，也不要擔(dān)心---你現(xiàn)在知道遞歸是什么了！

人們常常開玩笑說為了理解遞歸，你必須先理解遞歸。--John D.Cook

當(dāng)我第一次開始編程的時候，我一直在思考遞歸。我以前把它當(dāng)做有魔力的的咒語，或者一些只有頂級的開發(fā)者在解決最困難問題時才會使用的高級指令技術(shù)。

事實(shí)證明，它并不是那么有魔力。但是好的開發(fā)者會理解它。并且優(yōu)秀的開發(fā)者知道什么時候使用它最合適。

那么遞歸究竟是什么？

你有沒有過一遍又一遍的練習(xí)某一件事情直到某一個點(diǎn)“搞定它”？你就是在從事一個遞歸的過程。

簡單地說，就是在達(dá)到某一個既定目標(biāo)之前你重復(fù)的執(zhí)行某一個任務(wù)或者一系列步驟。那就是遞歸的本質(zhì)。

用代碼來說，遞歸函數(shù)就是一個調(diào)用自己的函數(shù)。

在深入任何代碼之前，我們通過一個基本的例子來理解遞歸函數(shù)的結(jié)構(gòu)。因?yàn)槲液芟矚g鋼琴，我們將編寫一個函數(shù)叫做 practicePiano。

每一次這個函數(shù)調(diào)用的時候都會通過參數(shù)傳入一個人（person），由這個人來練習(xí)鋼琴。因?yàn)槲椰F(xiàn)在沒有足夠的時間練習(xí)，所以我會練習(xí)一小部分（音階、和弦）：

practicePiano(person){
  practiceScales(person);  
  practiceChords(person);
}
practicePiano('Michael');

我調(diào)用了這個函數(shù)一次，所以我可以練習(xí)一次，但是我需要練習(xí)多次才能練得更好。

practicePiano('Michael');
practicePiano('Michael');
practicePiano('Michael');
practicePiano('Michael');
practicePiano('Michael');
practicePiano('Michael');
practicePiano('Michael');
practicePiano('Michael');
...

這很棒，但是它破壞了最偉大的編程宗旨之一：不要重復(fù)你自己（DRY）。

我能夠練習(xí)多次，但是每當(dāng)我想練習(xí)更多的時候，我不得不添加更多對 practicePiano 的調(diào)用。

可以解決這個問題的一種方法就是在函數(shù)內(nèi)部調(diào)用它自己，所以每次我調(diào)用 practicePiano，我就可以練習(xí)更多次：

practicePiano(person){
  practiceScales(person);  
  practiceChords(person);
//Recursive magic here!
  practicePiano(person);
}
//Now we only need one of these!
practicePiano('Michael');

這太酷了！我只需要調(diào)用一次這個函數(shù)就可以。唯一的問題是：一旦我調(diào)用了這個函數(shù)。。。我就停不下來。在我確實(shí)無法練習(xí)之前不會停下來。

//Our code above would behave as follows:
  practiceScales('Michael');  
  practiceChords('Michael');
//Recursive Call
  practiceScales('Michael');  
  practiceChords('Michael');
//Recursive Call
  practiceScales('Michael');  
  practiceChords('Michael');
//Recursive Call
//..till I can't physically practice anymore

當(dāng)你的電腦也達(dá)到類似的無法繼續(xù)的點(diǎn)時，通常會返回這個錯誤：

RangeError: Maximum call stack size exceeded

這等同于你的電腦說：“我沒有空間了，我必須關(guān)門歇業(yè)了”。它將每次函數(shù)調(diào)用以棧的形式記錄在內(nèi)存中。但是由于調(diào)用永不停止，棧就會填滿，電腦必須停止。（這就是注明的網(wǎng)站 Stack Overflow 的來由）

所以回到我那個永無休止的鋼琴練習(xí)，怎樣才能防止我的雙手脫落。

這就是你可能已經(jīng)聽說過的基本情況的重要性。

在遞歸函數(shù)中，基本情況就是你一直嘗試完成的目標(biāo)或者說你一直想完成的任務(wù)?；厩闆r的任務(wù)就是告訴你的函數(shù)什么時候應(yīng)該停止。

在我們的任務(wù)中，目標(biāo)就是一直練習(xí)到我疲倦為止。

practicePiano(person){
  
 if (tired(person)){ //When I am finally tired
    console.log("Guess you can take a break now...");
    return ;  //This will return out of the function and stop the recursive call
  }
  practiceScales(person);  
  practiceChords(person);
//Recursive magic here!
  practicePiano(person);
}
//Now when we call this here...I'll only practice over and over again until I'm tired
practicePiano('Michael');

這就是大多數(shù)開發(fā)者遇到錯誤的地方。盡管我們現(xiàn)在的鋼琴練習(xí)類比只是一個簡化版本，它帶來了一個非常重要的點(diǎn)：如果我永不疲倦會怎么樣？那么我們編寫的基本情況就不能解決我們的“最大調(diào)用棧超出限制”的錯誤。

在深入代碼之前，花點(diǎn)時間來考慮所有可能（并且應(yīng)該）停止遞歸調(diào)用的場景是非常重要的。

作為開發(fā)者，你會編寫復(fù)雜的算法，它們可能會接收可變的輸入并且使用遞歸來達(dá)到某一目標(biāo)。

你可能會編寫一個或者多個你相信通過遞歸調(diào)用能夠達(dá)到的基本情況。但是事實(shí)可能并非這樣。

來看一下我們的鋼琴練習(xí)程序：

practicePiano(person){
  
 if (tired(person)){
    console.log("Guess you can take a break now...");
    return ;  
  }
 if (handsFallOff(person)){
   console.log("Go see a doctor about that"); 
   return ; 
}
  practiceScales(person);  
  practiceChords(person);

  practicePiano(person);
}
practicePiano('Cyborg-Michael'); 
//Cyborg-Michael never gets tired
//Nor do his hands ever fall off
//Back to being stuck practicing forever...

以此為例，非常重要一點(diǎn)就是 ：你在編寫基本情況時考慮縝密并且確保你的函數(shù)會以某種方式運(yùn)行總能到達(dá)基本情況。

在我們的例子中，一個邏輯的基本條件應(yīng)該是能夠彈奏貝多芬第五交響曲的一小段。

重構(gòu)一下我們的代碼：

practicePiano(person, song){
  
 if (tired(person)){
    console.log("Guess you can take a break now...");
    return ;  
  }
 if (handsFallOff(person)){
   console.log("Go see a doctor about that"); 
   return ; 
}
 if (song(person)){
   console.log("Great Job! Time to learn this on the guitar!"); 
   return ; 
}
  practiceScales(person);  
  practiceChords(person);
  practicePiano(person, song);
}
practicePiano('Cyborg Michael', BeethovenFifth); 
//The Cyborg version of me never gets tired
//Nor do my hands ever fall off
//But, being a cyborg...I can learn Beethoven's 5th pretty quickly

這就是遞歸解決方案的強(qiáng)大之處。只使用幾行代碼，我就可以完成一些任務(wù)，完成這個任務(wù)我不知道需要多少步。我可能需要練習(xí)100遍，然而我的電子版本可能只需要5遍，但是這個解決方案對我們倆都適用。

所以總結(jié)一下，只需要記住以下幾點(diǎn)：

• 1、遞歸允許你通過簡單的重復(fù)一個任務(wù)來達(dá)到某一個目標(biāo)
• 2、基本情況應(yīng)該足夠縝密，確保你的遞歸函數(shù)能夠達(dá)到某一個結(jié)論（而不是一直運(yùn)轉(zhuǎn)）。
• 3、遞歸會幫助你的代碼保持 DRY（再次說明，你還會多次聽到這個縮略詞，所以請記住它代表“不要重復(fù)你自己”---哎，我又重復(fù)自己了）

更多遞歸

我將在后續(xù)的數(shù)據(jù)結(jié)構(gòu)文章中更多的探討遞歸。在這次深入學(xué)習(xí)中，我們將一起來探討在你的日常開發(fā)中怎么使用時間復(fù)雜度分析。我們也將分析各種循環(huán)方法來理解為什么有的方法會更好。

另外，在這里我們沒有機(jī)會討論的一個主題就是階乘問題。階乘問題是你使用遞歸解決方案最頻繁的地方。你可以在 SitePoint 的這篇非常棒的文章中找到更多關(guān)于階乘問題的解決方法。

本文譯自Recursion, Recursion, Recursion