12-递归

13.7　递归

另一个常见并且重要的函数用法是递归，递归是指那些调用自身的函数。当递归函数的输入集合不断缩小的时候，这项技术就会变得异常强大。

接下来看一个不太现实的例子：干草寻针。如果有一堆干草，要从中找一枚针，大家可能会这样做：

（1）如果找到针了，跳到第3步。

（2）从草堆中拿走一根干草，回到第1步。

（3）完成。

它的基本原理是不断地削减草堆，直到找到针为止。而这本质上是递归。下面看看如何使用代码实现这个例子：

function findNeedle(haystack) {
   if(haystack.length === 0) return "no haystack here!";
   if(haystack.shift() === 'needle') return "found it!"
   return findNeedle(haystack);   // haystack 又少了一个元素
}
findNeedle(['hay', 'hay', 'hay', 'hay', 'needle', 'hay', 'hay']);

这个递归函数中需要注意的关键点是，它处理了所有的可能性： haystack 是空的（这样就没有东西可找了），第一个元素就是针（找到了！），或者第一个元素不是针（那么针就在数组中的其他地方，所以移除了第一个元素，然后重复该函数：记住 Array.prototype.shift 移除的是数组第一个元素）。

注意：递归函数一定要有一个结束条件，不然它会一直递归下去，直到JavaScript解释器认为调用栈太深了（会导致程序崩溃）。在 findNeedle 函数中，有两个结束条件：找到了，或者干草堆没有干草了。因为每次递归调用都会减少草堆的体积，所以最终达到结束条件是不可避免的。

再来看一个历史悠久的实用例子：计算一个数的阶乘。某个数的阶乘等于这个数和小于它的所有正整数相乘，阶乘的表示方式是在数字后加一个感叹号（!）。所以4!指的是4×3×2×1 =24。下面是使用递归函数的实现方式：

function fact(n) {
   if(n === 1) return 1;
   return n * fact(n-1);
} 

代码里面有一个结束条件（ n === 1 ），并且每次递归调用的时候，n的值都会减1。所以n最终会达到1（如果传入的是0或者负数，该函数将会无限执行下去直至崩溃，当然可以添加一些错误条件来防止这种事情的发生）。