js递归 - 舍宠博客

程序调用自身的编程技巧称为递归。递归思想也是软件开发中非常重要的基本思想之一。当然这种思想是要有，但是确实递归会影响效率。

我们称自己调用自己就叫做递归。

从小学就接触的阶乘就可以用递归实现。
示例：

function factorial(n) {
    if (n == 1) return n;
    return n * factorial(n - 1)
}
console.log(factorial(4)) // 4 * 3 * 2 * 1 = 24

曾经去面试时，就有这样一道题目，说是写出一个函数实现如下数列：1, 1, 2, 3, 5, 8, 13, 21, 34 … 。当时自以为很机智地一直在找规律，回来后跟别人说起，结果被深深的鄙视.

递归实现斐波那契数列：

function fibonacci(n){
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(8)) // 1 1 2 3 5 8 13 21

从这两个例子中，我们可以看出：

构成递归需具备边界条件、递归前进段和递归返回段，当边界条件不满足时，递归前进，当边界条件满足时，递归返回。阶乘中的 n == 1 和斐波那契数列中的 n < 2 都是边界条件。递归不能无限制地调用本身，边界条件就是递归的出口。

我们知道当执行一个函数的时候，就会创建一个执行上下文，并且压入执行上下文栈，当函数执行完毕的时候，就会将函数的执行上下文从栈中弹出。我们看上面阶乘的列子会发现JavaScript会不停的创建执行上下文压入执行上下文栈，对于内存而言，维护这么多的执行上下文是一笔不小的开销。

接下来我们试试用尾调用来优化它。

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

// 尾调用
function a(x){
    return b(x);
}

然而

// 非尾调用
function a(x){
    return b(x) + 1;
}

因为 b(x) 的返回值还需要跟 1 进行计算后，a(x)才会返回值。

也就说尾调用函数执行时，虽然也调用了一个函数，但是因为原来的函数执行完毕，执行上下文会被弹出，执行上下文栈中相当于只多压入了一个执行上下文。然而非尾调用函数，就会创建多个执行上下文压入执行上下文栈。

接下来我们用尾调用来优化递归：

function factorial(n, res) {
    if (n == 1) return res;
    return factorial(n - 1, n * res)
}
console.log(factorial(4, 1)) // 24