JavaScript 尾递归调用优化实质解释

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了JavaScript 尾递归调用优化实质解释，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8182字，纯文字阅读大概需要12分钟。

内容图文

JavaScript 尾递归调用优化实质解释

我是在写一段代码的时候，打算用 ...rest 参数承接多参数情况，为了熟悉就去翻一下 ES6 的教程(《ES6入门》)，顺带着把那一章节所讲的复习一下，然后看到了尾递归优化，说其实质是把递归转为了循环，我突然想到我接下的代码会用到递归，会不会有栈满的情况（我碰到过），所以想着就干脆把它吃下来看看。

注意：

深究这段代码前请进行取舍，JS 尾调用并不是一定会用到，而且有时候递归就能解决很多问题，我是为了了解一下它设计的思想，看以后如果我不能用递归的时候该怎么进行设计。此处摘出一位网友的说法：

尾归调用的想法是好的，但是落地的时候出现了分歧，node在后续的版本中支持过尾归调用，但后续给去掉了。浏览器上只有safari支持，而其他浏览器上并不支持。所以，这是一个“未真正实现的提议”，大家仅仅了解下，目前还无法普遍用到生产环境中。”

吐槽一下

代码很精简，精简的难以看懂，gou ri de，花了我好久…………

正文分隔符

文前语：部分文字和代码来自于 阮一峰的《ES6入门》，以及一个“关于尾递归优化的问题”论坛的网友们。

设计精髓

在讲递归优化之前，先说出我理解到的其中设计精髓所在，先读一遍，然后再去研究具体实现的代码，那样会更容易。

1. 利用 this 的 arguments 把下一轮递归参数给带出。
2. 递归时只有第一次调用了，递归在真正运转，后面每一次递归内返回的函数结果都是 undefined ,也就是没有递归了。

递归函数

下面是一个正常的递归函数。

function sum(x, y) {
	if (y > 0)  return sum(x + 1, y - 1);
	else		return x;
}

sum(1, 100000)
// Uncaught RangeError: Maximum call stack size exceeded(…)

上面代码中，sum是一个递归函数，参数x是需要累加的值，参数y控制递归次数。一旦指定sum递归 100000 次，就会报错，提示超出调用栈的最大次数。

尾递归调用优化——递归转循环

这是尾递归调用优化的实现：（温馨提示：在阅读下面的解析过程之前，请把这段代码进行截屏放在你的屏幕上，方便你随时进行对照和查看。）

function tco(f) {
	var value;
	var active = false;
	var accumulated = [];

	return function accumulator() {
		accumulated.push(arguments);
		if (!active) {
			active = true;
			while (accumulated.length) {
				value = f.apply(this, accumulated.shift());
			}
			active = false;
			return value;
		}
	};
}

var sum = tco(function(x, y) {
	if (y > 0) {
		return sum(x + 1, y - 1)
	} else {
		return x
	}
});

sum(1, 100000)

这是 ES6教程 原文：

“上面代码中，tco函数是尾递归优化的实现，它的奥妙就在于状态变量active。默认情况下，这个变量是不激活的。一旦进入尾递归优化的过程，这个变量就激活了。然后，每一轮递归sum返回的都是undefined，所以就避免了递归执行；而accumulated数组存放每一轮sum执行的参数，总是有值的，这就保证了accumulator函数内部的while循环总是会执行。这样就很巧妙地将“递归”改成了“循环”，而后一轮的参数会取代前一轮的参数，保证了调用栈只有一层。”

上面这一段话看着是不是有些懵，没事，往下看，我也没打算让你直接就读懂，反正我是没读懂，不过他说的都没错，等你了解了之后再来看这段话就能读懂了。

了解过程

这段过程的替换代码来自于“论坛”中一位网友的提供，这样可以更直观的感受到函数运行的流程，使我在理解上向前走了一步。

我们来看递归函数本身:

var sum = tco(function(x, y) {
	if (y > 0) {
		return sum(x + 1, y - 1)
	} else {
		return x
	}
});

• tco 返回的是一个函数，我们也将之进行等价替换。且这个函数内部有三个私有变量：value , active , accumulated 。（记住，这三个变量是属于私有变量。为了便于理解，我们将第一次调用的这个 toc 称之为 first-toc）

var sum = function() {
	accumulated.push(arguments);
	if (!active) {
		active = true;
		while (accumulated.length) {
			value = function(x, y) {
				if (y > 0) {
					return sum(x + 1, y - 1)
				} else {
					return x
				}
			}.apply(this, accumulated.shift());
		}
		active = false;
		return value;
	}
};

接下来我们分析一下 sum(1, 100000) 实质发生了什么？

• 首先，把输入的两个参数从 arguments 提取出来给了 accumulated 进行存储。

accumulated = [ {0:1, 1:100000} ];
// 等价于
// first-toc.accumulated = [ {0:1, 1:100000} ]

• 然后进入 if 语句，

active = true;
// 等价于
// first-toc.active = true

• 然后进入 while 语句，

value = function(x, y) {
	if (y > 0) return sum(x + 1, y - 1)
	else 	   return x;
}.apply(this, accumulated.shift());

注意：这里的这个 this 很重要!

apply可以改变函数的运行环境，即运行时函数内部this变量的值。这时，我们调用this，就把first-toc传送给了function内部，成了this调用的背景，如下：

value = function(x, y) {
	if (y > 0) return sum(x + 1, y - 1)
	else 	   return x;
	// this.accumulated 等价于 first-toc.accumulated ;
}.apply(this, accumulated.shift());

那么这个转移有什么用呢？我们继续往下看。

（如果你不理解 apply 的具体作用，参考这篇文章。）

• 进入 while 语句后可以等价替换成

value = (function(x, y) { if (y > 0) { return sum(x + 1, y - 1); } else { return x } }(1, 100000));
// 这是一个立即执行函数

• 又可以等价替换成

value = sum(1+1, 100000 - 1)
// return sum(x + 1, y - 1)

• 此时（我们还在第一次执行中噢），当前的（first-toc）私有变量值的情况：

accumulated = [] ;
value = undefined ;
active = true ;

还能记得这三个值怎么来的吗？

accumulated：在apply(this, accumulated.shift())时被清空了，shift函数的作用是 删除数组的第一个元素并返回 。

value：value不是等于sum(1+1, 100000 - 1)吗？怎么变成 undefined了？我们继续往下看。

active：它是在进入while循环之前就被修改了。active = true; while (accumulated.length) ……

• 我们继续走

刚才我们已经得到了：

value = sum(1+1, 100000 - 1);

还记得我们最开始的替换吗？ sum 等于什么？

• tco 返回的是一个函数，我们也将之进行等价替换。且这个函数内部有三个私有变量：value , active , accumulated 。（记住，这三个变量是属于私有变量。）

var sum = function() {
	accumulated.push(arguments);
	if (!active) { // 你觉得此时的 active 是 ture 还是 false ?
		active = true;
		while (accumulated.length) {
			value = function(x, y) {
				if (y > 0) {
					return sum(x + 1, y - 1)
				} else {
					return x
				}
			}.apply(this, accumulated.shift());
		}
		active = false;
		return value;
	}
};

这是第二次递归入口，我称这个变量为 second-toc ，请你尝试回答一下我在代码中的提问，你肯定会想翻一下 toc 函数的定义，我给你贴在了下面：

function tco(f) {
	var value;
	var active = false;
	var accumulated = [];

	return function accumulator() {
		accumulated.push(arguments);
		if (!active) {
			active = true;
			while (accumulated.length) {
				value = f.apply(this, accumulated.shift());
			}
			active = false;
			return value;
		}
	};
}

你觉得是 false ？你有没有感觉我忘了讲什么？要不要往上翻翻？

还记得我让你的注意的那个this吗？

那么这个转移有什么用呢？

现在你能猜出second-toc.action的值了吗？

答案是 true ，理由嘛自己想去。不过，this可不只这么点作用。

我们运行第 2 次那个递归：

value = sum(1+1, 100000 - 1);

var sum = function() {
	accumulated.push(arguments);
	if (!active) { // active == true ;
		active = true;
		while (accumulated.length) {
			value = function(x, y) {
				if (y > 0) {
					return sum(x + 1, y - 1)
				} else {
					return x
				}
			}.apply(this, accumulated.shift());
		}
		active = false;
		return value;
	}
	// else return undefined; // 原函数没有 else ，程序执行完成默认返回 undefined 。
};

因为active == true，所以第二次递归没有进入到while循环里，而是直接执行完成，所以返回了undefined。所以：

value = sum(1+1, 100000 - 1);

执行结果为 value = undefined ;。

• 那么接下来呢？

我们再返回第一次递归执行：

var sum = function() {
	accumulated.push(arguments);
	if (!active) {
		active = true;
		while (accumulated.length) {
			value = function(x, y) {
				if (y > 0) {
					return sum(x + 1, y - 1)
				} else {
					return x
				}
			}.apply(this, accumulated.shift());
			// 我们刚才执行到这儿
			// 上一步得到结果 value = undefined
		}
		active = false;
		return value;
	}
};

value都等于undefined了，accumulated也因为shift()被清空了，那程序岂不是结束了？只执行了一遍？

肯定不对呀!

怎么能只执行一遍呢，递归那么深呢，都把栈压满了！其实你忽略了一些东西，给你提示一下： this的作用是替换函数背景域！！

决定性的一句

回去看看第二次递归的代码（其实看toc的函数定义就行），是不是有这么一句：

accumulated.push(arguments);// 这个变量是不是看着有些眼熟？

现在你能猜出来了吗？再给你点提示：

while (accumulated.length) {
	value = function(x, y) {
		if (y > 0) {
			return sum(x + 1, y - 1)
		} else {
			return x
		}
	}.apply(this, accumulated.shift());
	// 等价于
	// value = (function(x, y) { if (y > 0) { return sum(x + 1, y - 1); } else { return x } }(1, 100000));
}

答案揭晓：(1, 100000) 作为参数被写到函数内部的 arguments 里了，然后因为apply和this的关系：

first-toc.accumulated == second-toc.accumulated

所以第一次递归里：

while (accumulated.length) == while (first-toc.accumulated.length) == while (second-toc.accumulated.length)

判断结果就为true啦！如此往复循环，却不会爆栈。

你想到了吗？

意义及局限

我把这一部分放在了最后，也是我后来才思考出来的：披着递归的外衣，干着循环的事情! （在写代码时用递归的逻辑去写，代码结构清晰易懂，但你把 toc 函数利用起来后，实际执行是通过循环执行，也就是说完全不用担心爆栈的问题啦！）。

局限性也很明显，首先必须是尾递归调用；其次，这个是 JavaScript 的代码，我尚未想出如何用其他代码实现，譬如 Java / C++ ，如果有实际用到再考虑研究吧。

内容总结

以上是互联网集市为您收集整理的JavaScript 尾递归调用优化实质解释全部内容，希望文章能够帮你解决JavaScript 尾递归调用优化实质解释所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端