定义

程序调用自身的编程技巧称为递归(recursion)。

阶乘

以阶乘为例：

  1. function factorial(n) {
  2.     if (n == 1) return n;
  3.     return n * factorial(n - 1)
  4. }
  5.  
  6. console.log(factorial(5)) // 5 * 4 * 3 * 2 * 1 = 120

示意图(图片来自 wwww.penjee.com)：

阶乘

斐波那契数列

在《JavaScript专题之函数记忆》中讲到过的斐波那契数列也使用了递归：

  1. function fibonacci(n){
  2.     return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
  3. }
  4.  
  5. console.log(fibonacci(5)) // 1 1 2 3 5

递归条件

从这两个例子中，我们可以看出：

构成递归需具备边界条件、递归前进段和递归返回段，当边界条件不满足时，递归前进，当边界条件满足时，递归返回。阶乘中的 n == 1 和 斐波那契数列中的 n < 2 都是边界条件。

总结一下递归的特点：

  • 子问题须与原始问题为同样的事，且更为简单；
  • 不能无限制地调用本身，须有个出口，化简为非递归状况处理。
    了解这些特点可以帮助我们更好的编写递归函数。

执行上下文栈

在《JavaScript深入之执行上下文栈》中，我们知道：

当执行一个函数的时候，就会创建一个执行上下文，并且压入执行上下文栈，当函数执行完毕的时候，就会将函数的执行上下文从栈中弹出。

试着对阶乘函数分析执行的过程，我们会发现，JavaScript 会不停的创建执行上下文压入执行上下文栈，对于内存而言，维护这么多的执行上下文也是一笔不小的开销呐！那么，我们该如何优化呢？

答案就是尾调用。

尾调用

尾调用，是指函数内部的最后一个动作是函数调用。该调用的返回值，直接返回给函数。

举个例子：

  1. // 尾调用
  2. function f(x){
  3.     return g(x);
  4. }

然而

  1. // 非尾调用
  2. function f(x){
  3.     return g(x) + 1;
  4. }

并不是尾调用，因为 g(x) 的返回值还需要跟 1 进行计算后，f(x)才会返回值。

两者又有什么区别呢？答案就是执行上下文栈的变化不一样。

为了模拟执行上下文栈的行为，让我们定义执行上下文栈是一个数组：

  1.     ECStack = [];

我们模拟下第一个尾调用函数执行时的执行上下文栈变化：

  1. // 伪代码
  2. ECStack.push(<f> functionContext);
  3.  
  4. ECStack.pop();
  5.  
  6. ECStack.push(<g> functionContext);
  7.  
  8. ECStack.pop();

我们再来模拟一下第二个非尾调用函数执行时的执行上下文栈变化：

  1. ECStack.push(<f> functionContext);
  2.  
  3. ECStack.push(<g> functionContext);
  4.  
  5. ECStack.pop();
  6.  
  7. ECStack.pop();

也就说尾调用函数执行时，虽然也调用了一个函数，但是因为原来的的函数执行完毕，执行上下文会被弹出，执行上下文栈中相当于只多压入了一个执行上下文。然而非尾调用函数，就会创建多个执行上下文压入执行上下文栈。

函数调用自身，称为递归。如果尾调用自身，就称为尾递归。

所以我们只用把阶乘函数改造成一个尾递归形式，就可以避免创建那么多的执行上下文。但是我们该怎么做呢？

阶乘函数优化

我们需要做的就是把所有用到的内部变量改写成函数的参数，以阶乘函数为例：

  1. function factorial(n, res) {
  2.     if (n == 1) return res;
  3.     return factorial(n - 1, n * res)
  4. }
  5.  
  6. console.log(factorial(4, 1)) // 24

然而这个很奇怪呐……我们计算 4 的阶乘，结果函数要传入 4 和 1，我就不能只传入一个 4 吗？

这个时候就要用到我们在《JavaScript专题之偏函数》中编写的 partial 函数了：

  1. var newFactorial = partial(factorial, _, 1)
  2.  
  3. newFactorial(4) // 24

应用

如果你看过 JavaScript 专题系列的文章，你会发现递归有着很多的应用。

作为专题系列的第十八篇，我们来盘点下之前的文章中都有哪些涉及到了递归：

1.《JavaScript 专题之数组扁平化》：

  1. function flatten(arr) {
  2.     return arr.reduce(function(prev, next){
  3.         return prev.concat(Array.isArray(next) ? flatten(next) : next)
  4.     }, [])
  5. }

2.《JavaScript 专题之深浅拷贝》：

  1. var deepCopy = function(obj) {
  2.     if (typeof obj !== 'object') return;
  3.     var newObj = obj instanceof Array ? [] : {};
  4.     for (var key in obj) {
  5.         if (obj.hasOwnProperty(key)) {
  6.             newObj[key] = typeof obj[key] === 'object' ? deepCopy(obj[key]) : obj[key];
  7.         }
  8.     }
  9.     return newObj;
  10. }

3.JavaScript 专题之从零实现 jQuery 的 extend：

  1. // 非完整版本，完整版本请点击查看具体的文章
  2. function extend() {
  3.  
  4.     ...
  5.  
  6.     // 循环遍历要复制的对象们
  7.     for (; i < length; i++) {
  8.         // 获取当前对象
  9.         options = arguments[i];
  10.         // 要求不能为空 避免extend(a,,b)这种情况
  11.         if (options != null) {
  12.             for (name in options) {
  13.                 // 目标属性值
  14.                 src = target[name];
  15.                 // 要复制的对象的属性值
  16.                 copy = options[name];
  17.  
  18.                 if (deep && copy && typeof copy == 'object') {
  19.                     // 递归调用
  20.                     target[name] = extend(deep, src, copy);
  21.                 }
  22.                 else if (copy !== undefined){
  23.                     target[name] = copy;
  24.                 }
  25.             }
  26.         }
  27.     }
  28.  
  29.     ...
  30.  
  31. };

4.《JavaScript 专题之如何判断两个对象相等》：

  1. // 非完整版本，完整版本请点击查看具体的文章
  2. // 属于间接调用
  3. function eq(a, b, aStack, bStack) {
  4.  
  5.     ...
  6.  
  7.     // 更复杂的对象使用 deepEq 函数进行深度比较
  8.     return deepEq(a, b, aStack, bStack);
  9. };
  10.  
  11. function deepEq(a, b, aStack, bStack) {
  12.  
  13.     ...
  14.  
  15.     // 数组判断
  16.     if (areArrays) {
  17.  
  18.         length = a.length;
  19.         if (length !== b.length) return false;
  20.  
  21.         while (length--) {
  22.             if (!eq(a[length], b[length], aStack, bStack)) return false;
  23.         }
  24.     }
  25.     // 对象判断
  26.     else {
  27.  
  28.         var keys = Object.keys(a),
  29.             key;
  30.         length = keys.length;
  31.  
  32.         if (Object.keys(b).length !== length) return false;
  33.         while (length--) {
  34.  
  35.             key = keys[length];
  36.             if (!(b.hasOwnProperty(key) && eq(a[key], b[key], aStack, bStack))) return false;
  37.         }
  38.     }
  39.  
  40. }

5.《JavaScript 专题之函数柯里化》：

  1. // 非完整版本，完整版本请点击查看具体的文章
  2. function curry(fn, args) {
  3.     length = fn.length;
  4.  
  5.     args = args || [];
  6.  
  7.     return function() {
  8.  
  9.         var _args = args.slice(0),
  10.  
  11.             arg, i;
  12.  
  13.         for (i = 0; i < arguments.length; i++) {
  14.  
  15.             arg = arguments[i];
  16.  
  17.             _args.push(arg);
  18.  
  19.         }
  20.         if (_args.length < length) {
  21.             return curry.call(this, fn, _args);
  22.         }
  23.         else {
  24.             return fn.apply(this, _args);
  25.         }
  26.     }
  27. }

写在最后

递归的内容远不止这些，比如还有汉诺塔、二叉树遍历等递归场景，本篇就不过多展开，真希望未来能写个算法系列。

专题系列

JavaScript专题系列目录地址：https://github.com/mqyqingfeng/Blog。

JavaScript专题系列预计写二十篇左右，主要研究日常开发中一些功能点的实现，比如防抖、节流、去重、类型判断、拷贝、最值、扁平、柯里、递归、乱序、排序等，特点是研(chao)究(xi) underscore 和 jQuery 的实现方式。

如果有错误或者不严谨的地方，请务必给予指正，十分感谢。如果喜欢或者有所启发，欢迎 star，对作者也是一种鼓励。