前言

递归是一种解决问题的方法，它解决问题的各个小部分，直到解决最初的大问题。通常涉及函数调用自身。 

能够像下面这样直接调用自身的方法或函数，是递归函数：

能够像下面这样间接调用自身的函数，也是递归函数： 

假设现在必须要执行recursiveFunction，结果是什么？单单就上述情况而言，它会一直 执行下去。因此，每个递归函数都必须要有边界条件，即一个不再递归调用的条件（停止点）， 以防止无限递归。

JavaScript调用栈大小的限制

如果忘记加上用以停止函数递归调用的边界条件，会发生什么呢？递归并不会无限地执行下 去；浏览器会抛出错误，也就是所谓的栈溢出错误（stack overflow error）。每个浏览器都有自己的上限，可用以下代码测试： 

在Chrome v37中，这个函数执行了20955次，而后浏览器抛出错误RangeError: Maximum call stack size exceeded（超限错误：超过最大调用栈大小）。Firefox v27中，函数执行了343429次，然后浏览器抛出错误 InternalError: too much recursion（内部错误：递归次数过多）。 

根据操作系统和浏览器的不同，具体数值会所有不同，但区别不大。

ECMAScript 6有尾调用优化（tail call optimization）。如果函数内最后一个操作是调用函数（就 像示例中加粗的那行），会通过“跳转指令”（jump） 而不是“子程序调用”（subroutine call）来 控制。也就是说，在ECMAScript 6中，这里的代码可以一直执行下去。所以，具有停止递归的边 界条件非常重要。 

有关尾调用优化的更多相关信息，请访问http://goo.gl/ZdTZzg。

动态规划

动态规划（Dynamic Programming，DP）是一种将复杂问题分解成更小的子问题来解决的优化技术。

要注意动态规划和分而治之（归并排序和快速排序算法中用到的那种）是不同的方法。分而治之方法是把问题分解成相互独立的子问题，然后组合它们的答案，而动态规划则是将问题分解成相互依赖的子问题。 

用动态规划解决问题时，要遵循三个重要步骤：

 1. 定义子问题；

 2.实现要反复执行而解决子问题的部分

 3. 识别并求解出边界条件。 

能用动态规划解决的一些著名的问题如下。 

背包问题：给出一组项目，各自有值和容量，目标是找出总值最大的项目的集合。这个 问题的限制是，总容量必须小于等于“背包”的容量。 

最长公共子序列：找出一组序列的最长公共子序列（可由另一序列删除元素但不改变余 下元素的顺序而得到）。 

矩阵链相乘：给出一系列矩阵，目标是找到这些矩阵相乘的最高效办法（计算次数尽可 能少）。相乘操作不会进行，解决方案是找到这些矩阵各自相乘的顺序。 

硬币找零：给出面额为d1…dn的一定数量的硬币和要找零的钱数，找出有多少种找零的 方法。 

图的全源最短路径：对所有顶点对(u, v)，找出从顶点u到顶点v的最短路径。 

接下来的例子，涉及硬币找零问题的一个变种。 

最少硬币找零问题 

最少硬币找零问题是硬币找零问题的一个变种。硬币找零问题是给出要找零的钱数，以及可 用的硬币面额d1…dn及其数量，找出有多少种找零方法。最少硬币找零问题是给出要找零的钱数， 以及可用的硬币面额d1…dn及其数量，找到所需的最少的硬币个数。

例如，美国有以下面额（硬币）：d1=1，d2=5，d3=10，d4=25。

如果要找36美分的零钱，我们可以用1个25美分、1个10美分和1个便士（1美分）。 

如何将这个解答转化成算法？

最少硬币找零的解决方案是找到n所需的最小硬币数。但要做到这一点，首先得找到对每个 x<n的解。然后，我们将解建立在更小的值的解的基础上。 

来看看算法： 

为了更有条理，我们创建了一个类，解决给定面额的最少硬币找零问题。让我们一步步解读这个算法。 

MinCoinChange类接收coins参数（行{1}），代表问题中的面额。对美国的硬币系统而言， 它是[1, 5, 10, 25]。我们可以随心所欲传递任何面额。此外，为了更加高效且不重复计算值， 我们使用了cache（行{2}）。 

接下来是makeChange方法，它也是一个递归函数，找零问题由它解决。首先，若amount 不为正（< 0），就返回空数组（行{3}）；方法执行结束后，会返回一个数组，包含用来找零的各 个面额的硬币数量（最少硬币数）。接着，检查cache缓存。若结果已缓存（行{4}），则直接返 回结果；否则，执行算法。 

我们基于coins参数（面额）解决问题。因此，对每个面额（行{5}），我们都计算newAmount （行{6}）的值，它的值会一直减小，直到能找零的最小钱数（别忘了本算法对所有的x < amount 都会计算makeChange结果）。若newAmount是合理的值（正值），我们也会计算它的找零结果（行 {7}）。 

最后，我们判断newAmount是否有效，minValue （最少硬币数）是否是最优解，与此同时 minValue和newAmount是否是合理的值（{行10}）。若以上判断都成立，意味着有一个比之前 更优的答案（行{11}，以5美分为例，可以给5便士或者1个5美分镍币，1个5美分镍币是最优解）。最后，返回最终结果（行{12}）。 

测试一下这个算法：

要知道，如果我们检查cache变量，会发现它存储了从1到36美分的所有结果。以上代码的 结果是[1, 10, 25]。 

学到了吧？学到就是赚到。

如果觉得文章对你有点帮助，请微信搜索「 极光训练营 」第一时间阅读，并且还可以加入技术交流群与千位大咖一起交流学习