定义
程序调用自身的编程技巧称为递归(recursion)。
阶乘
以阶乘为例：
function factorial(n) {
if (n == 1) return n;
return n * factorial(n - 1)
}
console.log(factorial(5)) // 5 * 4 * 3 * 2 * 1 = 120
示意图：
image.png
斐波那契数列
斐波那契数列也使用了递归：
function fibonacci(n){
return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(5)) // 1 1 2 3 5
递归条件
从这两个例子中，我们可以看出：
构成递归需具备边界条件、递归前进段和递归返回段，当边界条件不满足时，递归前进，当边界条件满足时，递归返回。阶乘中的 n == 1 和 斐波那契数列中的 n < 2 都是边界条件。
总结一下递归的特点：
- 子问题须与原始问题为同样的事，且更为简单；
- 不能无限制地调用本身，须有个出口，化简为非递归状况处理。
了解这些特点可以帮助我们更好的编写递归函数。
执行上下文栈
我们知道：
当执行一个函数的时候，就会创建一个执行上下文，并且压入执行上下文栈，当函数执行完毕的时候，就会将函数的执行上下文从栈中弹出。
试着对阶乘函数分析执行的过程，我们会发现，JavaScript 会不停的创建执行上下文压入执行上下文栈，对于内存而言，维护这么多的执行上下文也是一笔不小的开销呐！那么，我们该如何优化呢？
答案就是尾调用。
尾调用
尾调用，是指函数内部的最后一个动作是函数调用。该调用的返回值，直接返回给函数。
举个例子：
// 尾调用
function f(x){
return g(x);
}
然而:
// 非尾调用
function f(x){
return g(x) + 1;
}
并不是尾调用，因为 g(x) 的返回值还需要跟 1 进行计算后，f(x)才会返回值。
两者又有什么区别呢？答案就是执行上下文栈的变化不一样。
为了模拟执行上下文栈的行为，让我们定义执行上下文栈是一个数组：
ECStack = [];
我们模拟下第一个尾调用函数执行时的执行上下文栈变化：
// 伪代码
ECStack.push(<f> functionContext);
ECStack.pop();
ECStack.push(<g> functionContext);
ECStack.pop();
我们再来模拟一下第二个非尾调用函数执行时的执行上下文栈变化：
ECStack.push(<f> functionContext);
ECStack.push(<g> functionContext);
ECStack.pop();
ECStack.pop();
也就说尾调用函数执行时，虽然也调用了一个函数，但是因为原来的的函数执行完毕，执行上下文会被弹出，执行上下文栈中相当于只多压入了一个执行上下文。然而非尾调用函数，就会创建多个执行上下文压入执行上下文栈。
函数调用自身，称为递归。如果尾调用自身，就称为尾递归。
所以我们只用把阶乘函数改造成一个尾递归形式，就可以避免创建那么多的执行上下文。但是我们该怎么做呢？
阶乘函数优化
我们需要做的就是把所有用到的内部变量改写成函数的参数，以阶乘函数为例：
function factorial(n, res) {
if (n == 1) return res;
return factorial(n - 1, n * res)
}
console.log(factorial(4, 1)) // 24
然而这个很奇怪呐……我们计算 4 的阶乘，结果函数要传入 4 和 1，我就不能只传入一个 4 吗？
这个时候就要用到所编写的 partial 函数了：
var newFactorial = partial(factorial, _, 1)
newFactorial(4) // 24
关于偏函数：
定义
维基百科中对偏函数 (Partial application) 的定义为：
In computer science, partial application (or partial function application) refers to the process of fixing a number of arguments to a function, producing another function of smaller arity.
翻译成中文：
在计算机科学中，局部应用是指固定一个函数的一些参数，然后产生另一个更小元的函数。
什么是元？元是指函数参数的个数，比如一个带有两个参数的函数被称为二元函数。
举个简单的例子：
function add(a, b) {
return a + b;
}
// 执行 add 函数，一次传入两个参数即可
add(1, 2) // 3
// 假设有一个 partial 函数可以做到局部应用
var addOne = partial(add, 1);
addOne(2) // 3
个人觉得翻译成“局部应用”或许更贴切些，以下全部使用“局部应用”。
柯里化与局部应用
这个例子和柯里化太像了，所以两者到底是有什么区别呢？
其实也很明显：
柯里化是将一个多参数函数转换成多个单参数函数，也就是将一个 n 元函数转换成 n 个一元函数。
局部应用则是固定一个函数的一个或者多个参数，也就是将一个 n 元函数转换成一个 n - x 元函数。
如果说两者有什么关系的话，描述就是：
Curried functions are automatically partially applied.
partial
我们今天的目的是模仿 underscore 写一个 partial 函数，比起 curry 函数，这个显然简单了很多。
也许你在想我们可以直接使用 bind 呐，举个例子：
function add(a, b) {
return a + b;
}
var addOne = add.bind(null, 1);
addOne(2) // 3
然而使用 bind 我们还是改变了 this 指向，我们要写一个不改变 this 指向的方法。
第一版
根据之前的表述，我们可以尝试着写出第一版：
// 第一版
// 似曾相识的代码
function partial(fn) {
var args = [].slice.call(arguments, 1);
return function() {
var newArgs = args.concat([].slice.call(arguments));
return fn.apply(this, newArgs);
};
};
我们来写个 demo 验证下 this 的指向：
function add(a, b) {
return a + b + this.value;
}
// var addOne = add.bind(null, 1);
var addOne = partial(add, 1);
var value = 1;
var obj = {
value: 2,
addOne: addOne
}
obj.addOne(2); // ???
// 使用 bind 时，结果为 4
// 使用 partial 时，结果为 5
第二版
然而正如 curry 函数可以使用占位符一样，我们希望 partial 函数也可以实现这个功能，我们再来写第二版：
// 第二版
var _ = {};
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);
};
};
我们验证一下：
var subtract = function(a, b) { return b - a; };
subFrom20 = partial(subtract, _, 20);
subFrom20(5);
写在最后
值得注意的是：underscore 和 lodash 都提供了 partial 函数，但只有 lodash 提供了 curry 函数。
应用
递归有着很多的应用：
盘点下业务场景中都有哪些涉及到了递归：
- 数组扁平化：
function flatten(arr) {
return arr.reduce(function(prev, next){
return prev.concat(Array.isArray(next) ? flatten(next) : next)
}, [])
}
- 深浅拷贝
var deepCopy = function(obj) {
if (typeof obj !== 'object') return;
var newObj = obj instanceof Array ? [] : {};
for (var key in obj) {
if (obj.hasOwnProperty(key)) {
newObj[key] = typeof obj[key] === 'object' ? deepCopy(obj[key]) : obj[key];
}
}
return newObj;
}
- 从0实现jQuery的extend
// 非完整版本
function extend() {
...
// 循环遍历要复制的对象们
for (; i < length; i++) {
// 获取当前对象
options = arguments[i];
// 要求不能为空 避免extend(a,,b)这种情况
if (options != null) {
for (name in options) {
// 目标属性值
src = target[name];
// 要复制的对象的属性值
copy = options[name];
if (deep && copy && typeof copy == 'object') {
// 递归调用
target[name] = extend(deep, src, copy);
}
else if (copy !== undefined){
target[name] = copy;
}
}
}
}
}
- 如何判断2个对象相等
// 非完整版本
// 属于间接调用
function eq(a, b, aStack, bStack) {
...
// 更复杂的对象使用 deepEq 函数进行深度比较
return deepEq(a, b, aStack, bStack);
};
function deepEq(a, b, aStack, bStack) {
...
// 数组判断
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;
}
}
}
- 函数柯里化
// 非完整版本
function curry(fn, args) {
length = fn.length;
args = args || [];
return function() {
var _args = args.slice(0),
arg, i;
for (i = 0; i < arguments.length; i++) {
arg = arguments[i];
_args.push(arg);
}
if (_args.length < length) {
return curry.call(this, fn, _args);
}
else {
return fn.apply(this, _args);
}
}
}
写在最后
递归的内容远不止这些，比如还有汉诺塔、二叉树遍历等递归场景，本篇就不过多展开，真希望未来能写个算法系列。
网友评论