JavaScript 递归与尾递归

递归

程序调用自身的编程技巧称为递归(recursion)。

1
2
3
4
5
6
function factorial(n) {
if (n == 1) return n;
return n * factorial(n - 1);
}

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

条件

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

尾调用

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

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

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

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

模拟执行上下文栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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();

尾调用函数执行时,调用了一个函数,在原来的的函数执行完毕,执行上下文会被弹出,执行上下文栈中相当于只多压入了一个执行上下文。然而非尾调用函数,就会创建多个执行上下文压入执行上下文栈。

尾递归:函数调用自身,称为递归。如果尾调用自身,就称为尾递归。

0%