javaScript之递归

发表于 更新于 阅读次数：

递归条件

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

总结下递归的特点：

  1. 子问题必须和原始问题有同样的事，且更为简单；
  2. 不能无限制地调用本身，须有一个出口，化简为非递归状况处理。

执行上下文栈

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

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

答案就是尾调用

尾调用

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

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

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

两者的区别在哪？答案就是–> 执行上下文栈的变化不一样。

这里使用一个数组来模拟执行上下文栈的行为。

1
ECStack = [];
1
2
3
4
5
6
7
8
9
// 尾调用
// 伪代码
ECStack.push(<f> functionContext)

ECStack.pop();

ECStack.push(<g> functionContext)

ECStack.pop()
1
2
3
4
5
6
7
8
9
// 非尾调用
// 伪代码
ECStack.push(<f> functionContext)

ECStac.push(<g> functionContext)

ECStack.pop()

ECStack.pop()

也就是说尾调用会在压入执行上下文栈后，因为原函数执行完毕而立马弹出，非尾调用则因为需要先进行运算，此时碰到了一个函数又会产生一个执行上下文，并且压入栈中，如果一直没有函数执行完，就会一直在执行上下文栈中层层压入。

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

我们只需要把阶乘改造成一个尾递归形式，就可以避免创建过多的执行上下文。

阶乘函数优化

1
2
3
4
5
//原阶乘函数
function factorial(n) {
  if (n == 1) return n;
  return n * factorial(n - 1);
}
1
2
3
4
5
//改造后的阶乘
function factorial(n, res) {
  if (n == 1) return res;
  return factorial(n - 1, n * res);
}

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

这个时候可以使用 偏函数 partial 函数了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function partial(fn) {
  var args = [].slice.call(arguments, 1);
  return function() {
    var position = 0,
      len = args.length;
    for (var i = 0; i < len; i++) {
      args[i] = args[i] === "_" ? arguments[position++] : args[i];
    }
    while (position < arguments.length) args.push(arguments[position++]);
    return fn.apply(this, args);
  };
}

function factorial(n, res) {
  if (n == 1) return res;
  return factorial(n - 1, n * res);
}
var newFactorial = partial(factorial, "_", 1);
console.log(newFactorial(4)); // 24

递归的一些应用

  1. 数组扁平化
1
2
3
4
5
function flatten(arr) {
  return arr.reduce(function(prev, next) {
    return prev.concat(Array.isArray(next) ? faltten(next) : next);
  }, []);
}
  1. 深浅拷贝
1
2
3
4
5
6
7
8
9
10
11
var deepCopy = function(obj) {
    if(typeof obj !== "object") return;
    // instanceof 用来检测Array.prototype 是否存在于参数 obj 的原型链上
    var newObj = obj instanceof Array ? [] : {};
    for(var key in obj) {
        if(obj.hasOwnProperty(key)) {
            newObject[key] = typeof obj[key] === 'object' ? deepCopy(obj[key] : obj[key])
        }
    }
    return newObj;
}
  1. 从零实现 jQuery 的 extend
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
var class2type = {};
var toString = class2type.toString;
var hasOwn = class2type.hasOwnProperty;

function isPlainObject(obj) {
    var proto, Ctor;
    if(!obj || toString.call(obj) !== "[object Object]") {
        return false;
    }
    //返回其原型的对象
    prop = Object.getPrototypeOf(obj);
    if(!prop) {
        return true;
    }
    Ctor = hasOwn.call(proto, "constructor") && proto.constructor;
    return typeof Ctor === "function" && hasOwn.toString.call(Ctor) === hasOwn.toString.call(Object);
}

/*
* extend(deep, clone, copy)
*
*/
function extend() {
    //默认不进行深拷贝
    var deep = false;
    var name, options, src, copy, clone, copyIsArray;
    var length = arguments.length;
    //记录要复制的对象的下标
    var i = 1;
    // 第一个参数不传布尔值，第二个参数是target
    target = arguments[0] || {};
    //如果第一个参数是布尔值，第二个参数是 target
    if(typeof target == 'boolean') {
        deep = target;
        target = arguments[i] || {};
        i ++;
    }
    // 如果target不是对象，我们是无法进行复制的，所以设置为{}
    if(typeof of target !== 'object' && !isFunction(target)) {
        target = {};
    }

    // 循环遍历要复制的对象们
    for(; i < length; i++) {
        //获取当前对象
        options = arguments[i];
        if(options != null) {
            for(name in options) {
                //目标属性值
                src = target[name];
                // 要复制的对象的属性
                copy = options[name];

                // 解决循环引用的问题
                if(target == copy) {
                    continue;
                }
                // 要递归的对象必须是 plainObject 或着数组
                if(deep && copy && isPlainObject(copy) || ((copyIsArray = Array.isArray(copy)))) {
                    // 要复制的对象属性值需要与目标属性值相同
                    if(copyIsArray) {
                        copyIsArray false;
                        clone = src && Array.isArray(src) ? src : [];
                    }else {
                        clone = src && isPlainObject(src) ? src : {};
                    }
                    target[name] = extend(deep, clone, copy);
                }else if(copy !== undefined) {
                    target[name] = copy;
                }
            }
        }
    }
    return target;
}
  1. 判断两个对象相等
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
var toString = Object.prototype.toString;

function isFunction(obj) {
  return toString.call(obj) === "[object Function]";
}

function eq(a, b, aStack, bStack) {
  // === 结果为 true 的区别出 +0 和 -0
  if (a === b) return a !== 0 || 1 / a === 1 / b;

  // typeof null 的结果为 object ，这里做判断，是为了让有 null 的情况尽早退出函数
  if (a == null || b == null) return false;

  // 判断 NaN
  if (a !== a) return b !== b;

  // 判断参数 a 类型，如果是基本类型，在这里可以直接返回 false
  var type = typeof a;
  if (type !== "function" && type !== "object" && typeof b != "object")
    return false;

  // 更复杂的对象使用 deepEq 函数进行深度比较
  return deepEq(a, b, aStack, bStack);
}

function deepEq(a, b, aStack, bStack) {
  // a 和 b 的内部属性 [[class]] 相同时 返回 true
  var className = toString.call(a);
  if (className !== toString.call(b)) return false;

  switch (className) {
    case "[object RegExp]":
    case "[object String]":
      return "" + a === "" + b;
    case "[object Number]":
      if (+a !== +a) return +b !== +b;
      return +a === 0 ? 1 / +a === 1 / b : +a === +b;
    case "[object Date]":
    case "[object Boolean]":
      return +a === +b;
  }

  var areArrays = className === "[object Array]";
  // 不是数组
  if (!areArrays) {
    // 过滤掉两个函数的情况
    if (typeof a != "object" || typeof b != "object") return false;

    var aCtor = a.constructor,
      bCtor = b.constructor;
    // aCtor 和 bCtor 必须都存在并且都不是 Object 构造函数的情况下，aCtor 不等于 bCtor， 那这两个对象就真的不相等啦
    if (
      aCtor !== bCtor &&
      !(
        isFunction(aCtor) &&
        aCtor instanceof aCtor &&
        isFunction(bCtor) &&
        bCtor instanceof bCtor
      ) &&
      ("constructor" in a && "constructor" in b)
    ) {
      return false;
    }
  }

  aStack = aStack || [];
  bStack = bStack || [];
  var length = aStack.length;

  // 检查是否有循环引用的部分
  while (length--) {
    if (aStack[length] === a) {
      return bStack[length] === b;
    }
  }

  aStack.push(a);
  bStack.push(b);

  // 数组判断
  if (areArrays) {
    length = a.length;
    if (length !== b.length) return false;

    while (length--) {
      if (!eq(a[length], b[length], aStack, bStack)) return false;
    }
  }
  // 对象判断
  else {
    var keys = Object.keys(a),
      key;
    length = keys.length;

    if (Object.keys(b).length !== length) return false;
    while (length--) {
      key = keys[length];
      if (!(b.hasOwnProperty(key) && eq(a[key], b[key], aStack, bStack)))
        return false;
    }
  }

  aStack.pop();
  bStack.pop();
  return true;
}
  1. 函数柯里化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// 第三版
function curry(fn, args, holes) {
  length = fn.length;

  args = args || [];

  holes = holes || [];

  return function() {
    var _args = args.slice(0),
      _holes = holes.slice(0),
      argsLen = args.length,
      holesLen = holes.length,
      arg,
      i,
      index = 0;

    for (i = 0; i < arguments.length; i++) {
      arg = arguments[i];
      // 处理类似 fn(1, _, _, 4)(_, 3) 这种情况，index 需要指向 holes 正确的下标
      if (arg === _ && holesLen) {
        index++;
        if (index > holesLen) {
          _args.push(arg);
          _holes.push(argsLen - 1 + index - holesLen);
        }
      }
      // 处理类似 fn(1)(_) 这种情况
      else if (arg === _) {
        _args.push(arg);
        _holes.push(argsLen + i);
      }
      // 处理类似 fn(_, 2)(1) 这种情况
      else if (holesLen) {
        // fn(_, 2)(_, 3)
        if (index >= holesLen) {
          _args.push(arg);
        }
        // fn(_, 2)(1) 用参数 1 替换占位符
        else {
          _args.splice(_holes[index], 1, arg);
          _holes.splice(index, 1);
        }
      } else {
        _args.push(arg);
      }
    }
    if (_holes.length || _args.length < length) {
      return curry.call(this, fn, _args, _holes);
    } else {
      return fn.apply(this, _args);
    }
  };
}

var _ = {};

var fn = curry(function(a, b, c, d, e) {
  console.log([a, b, c, d, e]);
});

// 验证 输出全部都是 [1, 2, 3, 4, 5]
fn(1, 2, 3, 4, 5);
fn(_, 2, 3, 4, 5)(1);
fn(1, _, 3, 4, 5)(2);
fn(1, _, 3)(_, 4)(2)(5);
fn(1, _, _, 4)(_, 3)(2)(5);
fn(_, 2)(_, _, 4)(1)(3)(5);