一、先热个身数学家高斯的在念小学的时候，他的数学老师出了一道题：对自然数1到100求和。高斯用首尾相加的办法很快的算出了答案，不过我们这次要扮演高斯的同学，老老实实的从1加到100。 首先试一下循环的思路： function sum(n) {
let count = 0;
for (let i = 1; i <= n; i++) {
count += i;
}
return count;
}
sum(100); // 5050可以看到循环体只有一行代码 count += i; 如果把 function sum(n) {
return n + sum(n-1);
}
// 这里的 sum(n-1) 不能写成 sum(n--)但仅仅这样是不够的，还差一个关键代码块——开关 递归本身是一个无限循环，需要添加控制条件，让程序在合适的时候退出循环 function sum(n) {
if (n === 1) {
return n;
}
return n + sum(n-1);
}
sum(100); // 5050
二、三大要素上面的例子已经完成了一个简单的递归，回头总结一下，我们主要做了两件事：
其实在这之前，我们还做了一件事，这件事很重要，但常常会被我们忽略掉：
这三大要素是写递归的必要条件，而其中的第三点，是写好一个递归的必要条件。 以经典的树组件作为案例，来印证一下这三要素。 树组件的主要功能，就是将一个规范的具有层级的数组，渲染成树列表
由此我们能明确这个函数的主要功能：接收一个数组入参，返回一个完整的树组件 好像大概可能应该也许有点问题？ 还是先来观察数组吧。每个元素的 这样一来就能很容易的提取出重复的逻辑：渲染树节点，以 为了更好的 UI 展示，还需要记录树节点的层级来计算当前节点的缩进。 我们只是在渲染树节点，而不是渲染整个树！ 之所以能渲染出整个树，是因为在函数执行的过程中，产生了很多的树节点，这些树节点组成了一个树。 所以我们这个函数功能应该是：接收一个数组作为必要参数，和一个数值作为可选参数，并返回一个树节点。 重新捋一下思路，这个渲染树组件的函数就清晰多了： renderTree = (list, level = 1) => {
return list.map(x => {
const { children, id } = x || {};
if (children) { // 递归的结束条件
return (
<TreeNode key={`${id}`} level={level}>
{/* 调用自身，形成递归 */}
{renderTreeNodes(children, level + 1)}
</TreeNode>
);
}
// 递归的出口
return <TreeNode key={`${id}`} level={level}></TreeNode>
})
}三、递归优化 - 手动缓存当我们去分析一个循环的时候，能清晰的看出这个函数的内部逻辑和执行次数。 而递归则不然，它的结构更加简洁，但也增加了理解成本。比如下面这个递归，你能一眼看出它的执行次数么？ function Fibonacci (n) {
return n <= 2 ? 1 : Fibonacci(n - 1) + Fibonacci(n - 2);
}这就是著名的 Fibonacci 数列，我尽力避免拿它举例，后来发现这个例子最为简单直观。
我们试着执行一下 居然执行了 109 次？ 其实回头分析一下 -- f(5) | -- f(4) | | -- f(3) | | | -- f(2) | | | -- f(1) | | -- f(2) | -- f(3) | | -- f(2) | | -- f(1) 叶子节点会被重复计算，层次越深，计算的次数就越多 这里有两个优化思路，第一种是从当前的逻辑上，添加一层缓存，如果当前入参已经计算过，就直接返回结果。 // 缓存函数
function memozi(fn){
const obj = {};
return function(n){
obj[n] = obj[n] || fn(n);
return obj[n];
}
}
const Fibonacci = memozi(function(n) {
return n <= 2 ? 1 : Fibonacci(n - 1) + Fibonacci(n - 2);
})
只执行了10次！这已经达到了循环的执行次数。 这是一种空间换时间的思想，增加了额外的变量来记录状态，不过函数的实际调用次数并没有减少，只是在 怎么才能真正实现 O(n) 的时间复杂度呢？ 四、递归优化 - 自下而上上面所有的递归都是自上而下的递归，从 能不能从最小值开始计算呢？ 在明确了 从而得到一个基本逻辑： function foo(x = 1, y = 1) {
return foo(y, x + y);
}这里的 然后加入 function Fibonacci(n, x = 1, y = 1) {
return n <= 2 ? y : Fibonacci(n - 1, y, x + y);
}
我们仅仅是稍微调整了函数的逻辑，就达到了 O(n) 的时间复杂度。这种自下而上的思想，其实是动态规划的体现。 动态规划是一种寻求最优解的数学方法，它经常会被当做一种算法，但它其实并不像“二分查找”、“冒泡排序”一样有着固定的范式。实际上动态规划是一种方法论，它提供的是一种解决问题的思路。 简单来说，动态规划将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解。而且动态规划是自下而上求解，先计算子问题，再由这些子问题计算父问题，直至求解出原问题的解，将时间复杂度优化为 O(n)。 动态规划有三个重要概念：
光看名词就觉得有点似曾相识。没错，这就是前文提到的递归三要素中的“缩小问题规模”和“结束条件”。 而动态规划的第三个概念，才是其核心所在：
所谓状态转移方程，就是子问题与父问题之间的关系，或者说：如何用子问题推导出父问题。 通常我们用递归都是自上而下，是先遇到了父问题，再去解决子问题。而动态规划是先解决子问题，再通过状态转移方程求解出父问题，也就是自下而上。这种自下而上的递归也被称为“递推”。 动态规划的适用范围，也是自下而上的适用范围：
只要满足这两点，就可以用自下而上的思路来优化。 不过上面自下而上求解 Fibonacci 数列的函数，除了动态规划之外，还使用了尾调用。 五、递归优化 - 尾调用函数在调用的时候，会在调用栈 (call stack) 中存有记录，每一条记录叫做一个调用帧 (call frame)。每调用一个函数，就向栈中 push 一条记录，函数执行结束后依次向外弹出，直到清空调用栈。 function foo () { console.log('wise'); }
function bar () { foo(); }
function baz () { bar(); }
baz();
造成这种结果是因为每个函数在调用另一个函数的时候，并没有 如果对上面的例子做如下修改： function foo () { console.log('wise'); }
function bar () { return foo(); }
function baz () { return bar(); }
baz();
上面的改动其实是函数式编程中的一个重要概念，当一个函数执行时的最后一个步骤是返回另一个函数的调用，这就叫做尾调用(PTC)。如果是在递归里面使用，即在函数的末尾调用自身，就是尾递归。 回头来看最开始的求 1~n 之和的例子： function sum(n) {
if (n === 1) {
return n;
}
return n + sum(n-1);
}
sum(100); // 5050如果执行 Uncaught RangeError: Maximum call stack size exceeded 将这个递归升级为尾递归： function sum(n, count = 0) {
if (n === 1) {
return count + n;
}
return sum(n-1, count+n);
}
现在调用栈中的调用帧始终只有一条，相对节省内存，这样的递归就靠谱了许多 尾调用对递归的意义重大，但在实际运用的时候却备受阻碍。 首先需要使用严格模式 Chrome V8 团队给出的解释是：
不过即使如此，Chrome 和 Mozilla 依然认可尾调用优化所带来的的性能提升，只是在引擎层面还没有找到一个很安全可靠的方案来支持尾调用优化。微软曾经提议从语法上来指定尾调用（类似于 虽然大部分的浏览器还不支持尾递归，但我们在开发的时候依然可以优先使用尾调用，毕竟运行的效果是一样的，而一旦程序在支持尾递归的环境下运行，就会有更快的运行速度。更重要的是，当我们尝试使用尾递归的时候，通常会自然而然的用到自下而上的思想。 六、小结我们一般认为递归会比循环的性能要差，是因为函数调用本身是有开销的。 但如果能实现尾递归，那么递归的效率应该至少和循环一样好。 对于不能使用尾调用的递归，即使写成了循环的形式，也只是拿一个栈来模拟递归的过程。会带来一定的效率提升，但也会造成代码的冗余。 关于循环和（优化之后的）递归之间的取舍，我觉得可以从以下几个方面判断：
我认为递归其实是一种思维方式。所谓的“递归比循环慢”，指的是递归的各种实现。 掌握递归的意义不在于编码本身，而在于知道如何编码。
参考资料：《递归优化：尾调用和Memoization》—— LumiereXyloto |
|
|
