定义

程序调用自身的编程技巧称为递归（Recursion）。

斐波那契数列

function fibonacci(n) {
	if(n<2) {
		return n
	} else {
		return fibonacci(n-1) + fibonacci(n-2)
	}
}

一张图表示递归（penjee.com)

递归条件

递归的特点：

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

执行上下文栈

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

试着对阶乘函数分析执行的过程，我们会发现，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) {
    if (n == 1) return n;
    return n * factorial(n - 1)
}

console.log(factorial(5)) // 5 * 4 * 3 * 2 * 1 = 120


// 尾递归优化

function factorial(n, res) {
    if (n == 1) return res;
    return factorial(n - 1, n * res)
}

console.log(factorial(4, 1)) // 24

Mark24

JavaScript编程之递归

定义

斐波那契数列

递归条件

执行上下文栈

尾调用