在我告诉你什么是递归之前，你应该读一下这篇文章：递归，递归，递归。
如果你没有这么做，那么表扬一下自己。如果你那么做了，也不要担心---你现在知道递归是什么了！
人们常常开玩笑说为了理解递归，你必须先理解递归。--John D.Cook
当我第一次开始编程的时候，我一直在思考递归。我以前把它当做有魔力的的咒语，或者一些只有顶级的开发者在解决最困难问题时才会使用的高级指令技术。
事实证明，它并不是那么有魔力。但是好的开发者会理解它。并且优秀的开发者知道什么时候使用它最合适。
那么递归究竟是什么？
你有没有过一遍又一遍的练习某一件事情直到某一个点“搞定它”？你就是在从事一个递归的过程。
简单地说，就是在达到某一个既定目标之前你重复的执行某一个任务或者一系列步骤。那就是递归的本质。
用代码来说，递归函数就是一个调用自己的函数。
在深入任何代码之前，我们通过一个基本的例子来理解递归函数的结构。因为我很喜欢钢琴，我们将编写一个函数叫做 practicePiano。
每一次这个函数调用的时候都会通过参数传入一个人（person），由这个人来练习钢琴。因为我现在没有足够的时间练习，所以我会练习一小部分（音阶、和弦）：
practicePiano(person){
practiceScales(person);
practiceChords(person);
}
practicePiano('Michael');
我调用了这个函数一次，所以我可以练习一次，但是我需要练习多次才能练得更好。
practicePiano('Michael');
practicePiano('Michael');
practicePiano('Michael');
practicePiano('Michael');
practicePiano('Michael');
practicePiano('Michael');
practicePiano('Michael');
practicePiano('Michael');
...
这很棒，但是它破坏了最伟大的编程宗旨之一：不要重复你自己（DRY）。
我能够练习多次，但是每当我想练习更多的时候，我不得不添加更多对 practicePiano 的调用。
可以解决这个问题的一种方法就是在函数内部调用它自己，所以每次我调用 practicePiano，我就可以练习更多次：
practicePiano(person){
practiceScales(person);
practiceChords(person);
//Recursive magic here!
practicePiano(person);
}
//Now we only need one of these!
practicePiano('Michael');
这太酷了！我只需要调用一次这个函数就可以。唯一的问题是：一旦我调用了这个函数。。。我就停不下来。在我确实无法练习之前不会停下来。
//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
当你的电脑也达到类似的无法继续的点时，通常会返回这个错误：
RangeError: Maximum call stack size exceeded
这等同于你的电脑说：“我没有空间了，我必须关门歇业了”。它将每次函数调用以栈的形式记录在内存中。但是由于调用永不停止，栈就会填满，电脑必须停止。（这就是注明的网站 Stack Overflow 的来由）
所以回到我那个永无休止的钢琴练习，怎样才能防止我的双手脱落。
这就是你可能已经听说过的基本情况的重要性。
在递归函数中，基本情况就是你一直尝试完成的目标或者说你一直想完成的任务。基本情况的任务就是告诉你的函数什么时候应该停止。
在我们的任务中，目标就是一直练习到我疲倦为止。
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');
这就是大多数开发者遇到错误的地方。尽管我们现在的钢琴练习类比只是一个简化版本，它带来了一个非常重要的点：如果我永不疲倦会怎么样？那么我们编写的基本情况就不能解决我们的“最大调用栈超出限制”的错误。
在深入代码之前，花点时间来考虑所有可能（并且应该）停止递归调用的场景是非常重要的。
作为开发者，你会编写复杂的算法，它们可能会接收可变的输入并且使用递归来达到某一目标。
你可能会编写一个或者多个你相信通过递归调用能够达到的基本情况。但是事实可能并非这样。
来看一下我们的钢琴练习程序：
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...
以此为例，非常重要一点就是 ：你在编写基本情况时考虑缜密并且确保你的函数会以某种方式运行总能到达基本情况。
在我们的例子中，一个逻辑的基本条件应该是能够弹奏贝多芬第五交响曲的一小段。
重构一下我们的代码：
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
这就是递归解决方案的强大之处。只使用几行代码，我就可以完成一些任务，完成这个任务我不知道需要多少步。我可能需要练习100遍，然而我的电子版本可能只需要5遍，但是这个解决方案对我们俩都适用。
所以总结一下，只需要记住以下几点：
- 1、递归允许你通过简单的重复一个任务来达到某一个目标
- 2、基本情况应该足够缜密，确保你的递归函数能够达到某一个结论（而不是一直运转）。
- 3、递归会帮助你的代码保持 DRY（再次说明，你还会多次听到这个缩略词，所以请记住它代表“不要重复你自己”---哎，我又重复自己了）
更多递归
我将在后续的数据结构文章中更多的探讨递归。在这次深入学习中，我们将一起来探讨在你的日常开发中怎么使用时间复杂度分析。我们也将分析各种循环方法来理解为什么有的方法会更好。
另外，在这里我们没有机会讨论的一个主题就是阶乘问题。阶乘问题是你使用递归解决方案最频繁的地方。你可以在 SitePoint 的这篇非常棒的文章中找到更多关于阶乘问题的解决方法。
