递归

下面主要讲解 JS 中的递归、递归爆栈问题、尾递归(递归优化)

function main(n) {
	if (n === 0) {
		return 'finish';
	} else {
		return main(n - 1);
	}
}

console.log(main(200000));

如果是 console.log(main(2)); 那么调用栈里面的大小就是 4 如果是 200000 那么其 200002 个,而我们通过

function computeMaxCallStackSize() {
	try {
		return 1 + computeMaxCallStackSize();
	} catch (e) {
		// Call stack overflow
		return 1;
	}
}
computeMaxCallStackSize(); //12577

那我们执行 console.log(main(12575));的时候刚好 执行 console.log(main(12576));就会出现 Uncaught RangeError: Maximum call stack size exceeded这就是我们著名的递归爆栈问题

尾递归优化

其实在 ES5 中仍然没有对尾递归优化进行处理

function fibonacci(n) {
	return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

当我们执行 fibonacci(5)其执行栈

[fibonacci(5)]
[fibonacci(4) + fibonacci(3)]
[(fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))]
[((fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))) + ((fibonacci(1) + fibonacci(0)) + fibonacci(1))]
[fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(0) + fibonacci(1)]

很容易最后一行就栈溢出了

那么我们怎么解决这个问题

function fibonacci(n) {
	return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}