当我们在编写计算阶乘的函数,一般我们都会会选择使用迭代或递归的方法来实现。下面就让我们看看,同一个函数的两种实现方法。首先,是使用迭代方式实现的函数,我们使用循环的方式来计算阶乘:
// 阶乘函数,计算给定正整数 n 的阶乘
const factorial = (n) => {// 初始化结果为 1let result = 1;// 使用循环逐步计算阶乘while (n > 1) {// 乘以当前的 n 值result *= n;// 减小 n,准备下一次迭代n--;}// 返回最终的阶乘结果return result;
}
jcode
接着我们再使用递归的方式来实现同样的函数
// 阶乘函数,递归方式计算给定正整数 n 的阶乘
const factorial = (n) => {// 当 n 为 0 时,阶乘为 1if (n === 0) {return 1;}// 递归情况:计算 n 与 (n-1) 的阶乘乘积return n * factorial(n - 1);
}
jcode
虽然上面这个递归函数和迭代函数的结果是相同的,但浏览器的运行过程中,迭代函数的性能要比递归函数好的多。并且如果我们在递归函数当去计算非常大的数的阶乘时,可能会遇到"RangeError: Maximum call stack size exceeded"
错误。这是因为递归函数中的递归调用会在调用栈中积累,当递归深度过深时,调用栈会耗尽系统的内存资源,从而导致错误。
这样说你可能会很懵,那我们就画图来好好理解一下递归是如何工作的。
调用栈
调用栈是一个存储函数调用信息的数据结构。当调用函数时,它会被添加到执行栈中,以及它所调用的所有函数。当一个函数返回时,它会从执行栈中移除。每个添加到栈中的函数称为一个栈帧。
下面我们画出迭代函数和递归函数计算6的阶乘的过程,来更好的理解
迭代函数的替代模型
递归函数的模型
通过两张图的对比,我们可以发现。
- 在迭代函数中,我们可以看到每一步的变量状态。并且,在我们的循环的每次迭代中,都会执行一次计算,然后更新存储在内存中的变量。
- 而在递归函数中,我们不能在执行过程的前半部分看到所有变量的状态。并且,每次执行函数时,都使用更多的内存来存储每次执行的结果值。
你可能会问这会有什么影响呢?
在使用迭代函数计算6的阶乘的过程中,JavaScript将我们的while条件添加到堆栈中,执行计算,然后更新result变量,然后从堆栈中删除while的执行代码块。他会一直这样重复的操作下去,直到我们的while条件为false,也就是n的值小于或等于1。
而在递归函数中,函数每次调用的阶乘函数都会被添加到堆栈中,直到我们的if条件为false时,也就是n的值小于或等于1。这说明我们的阶乘函数将在执行之前被添加到堆栈中6次。这也就是为什么当我们尝试计算一个非常大的数(比如100,000)的阶乘时,会遇到"RangeError: Maximum call stack size exceeded"
的错误的原因,因为调用栈中没有足够的空间来存储所有对阶乘函数的调用。
但是如果使用尾调用优化就能解决上面的问题。
尾调用优化
每当一个函数的最后一件事是调用另一个函数时,那么这个最后一个函数不需要返回给它的调用者。因此,不需要在调用栈上存储任何信息,函数的调用更像是一个跳转。这种类型的调用被称为尾调用;不增加栈的操作被称为尾调用优化(TCO)。
那我们要怎么把它变成尾递归呢?
当然是借助另一个函数啦
// 计算正整数 n 的阶乘
const factorial = (n) => {// 使用 factorialHelper 函数来执行实际计算,初始累积值为 1return factorialHelper(n, 1);
}// 辅助函数,递归计算阶乘
const factorialHelper = (x, accumulator) => {// 如果 x 小于或等于 1,返回累积值作为阶乘结果if (x <= 1) {return accumulator;}// 否则,递归调用自身,将 x 递减并累积的结果递归传递下去return factorialHelper(x - 1, x * accumulator);
}
上面,我们已经把函数修改成尾递归的形式了,它的最后一步是调用一个函数(而不是计算一个表达式,就像迭代一样)。接下来,让我们看看如何使用新的阶乘函数进行替代模型计算6的阶乘:
虽然我们现在的性能已经优于我们的递归函数,但是它还是会比迭代函数略微逊色。然而,如果我们计算较大的阶乘,依然会遇到"RangeError: Maximum call stack size exceeded"
的错误。
但是为什么还会发生这种情况呢?
这是因为尽管我们的函数是尾递归的,但如果我们使用的是的Node.js和浏览器(除了Safari)来执行代码,他们都是不会进行尾调用优化
那么,我们应该要如何来解决这个问题呢?
答案是:可以借助另一个函数来实现!我们将依赖Trampoline(跳板)方法
Trampoline
// trampoline 函数用于实现尾递归优化
const trampoline = (fn) => {// 只要 fn 是函数,就不断执行它while (typeof fn === 'function') {fn = fn();}// 返回最终的非函数结果return fn;
}
我们的 Trampoline 函数由一个循环组成,该循环调用一个包装另一个函数的函数(我们称之为thunk),他会一直循环执行,直到符合条件才会退出。
// trampoline 函数用于实现尾递归,接受一个函数 fn 作为输入
const trampoline = (fn) => {// 只要 fn 是函数,就不断执行它,直到 fn 不再是函数为止while (typeof fn === 'function') {fn = fn();}// 返回最终的结果return fn;
}// factorialHelper 函数用于递归计算阶乘,接受两个参数 x 和 accumulator
const factorialHelper = (x, accumulator) => {// 如果 x 小于等于 1,返回累积值(基本情况)if (x <= 1) {return accumulator;}// 返回一个函数,该函数会在下一次迭代中计算下一个递归步骤return () => factorialHelper(x - 1, x * accumulator);
}// factorial 函数用于启动阶乘计算,接受一个参数 n
const factorial = (n) => {// 调用 trampoline 函数,将输入参数 n 和初始累积值 1 传递给 factorialHelperreturn trampoline(() => factorialHelper(n, 1));
}
现在,我们可以来计算一个比较大的阶乘了,并且再也不会担心出现RangeError: Maximum call stack size exceeded
错误了。
但是如果我们要计算的阶乘是无穷大的,因为它是一个非常大的数字(大于 Number.MAX_SAFE_INTEGER: 253 - 1的数字)。在这种情况下,我们可以使用BigInt。
// trampoline 函数用于实现尾递归优化,接受一个函数 fn 作为输入
const trampoline = (fn) => {// 只要 fn 是函数,就不断执行它,直到 fn 不再是函数为止while (typeof fn === 'function') {fn = fn()}// 返回最终的结果return fn
}// factorialHelper 函数用于递归计算阶乘,接受两个参数 x 和 accumulator
const factorialHelper = (x, accumulator) => {// 如果 x 小于等于 1,返回累积值(基本情况)if (x <= 1) {return accumulator}// 否则,返回一个函数,该函数将计算下一个递归步骤return () => factorialHelper(x - 1n, x * accumulator)
}// factorial 函数用于启动阶乘计算,接受一个参数 n
const factorial = (n) => {// 将输入值 n 和初始累积值 1 转换为 BigInt 数据类型,然后调用 trampoline 函数进行尾递归计算return trampoline(factorialHelper(BigInt(n), 1n))
}
最后我们可以给函数添加类型定义,也就是ts的写法
// 定义 Thunk 类型,它可以是 bigint 或返回 Thunk 的函数
type Thunk = bigint | (() => Thunk)// trampoline 函数用于实现尾递归,接受一个 Thunk 作为输入
const trampoline = (fn: Thunk) => {// 只要 fn 是函数,就循环执行它,直到 fn 不再是函数为止while (typeof fn === 'function') {fn = fn()}// 返回最终的结果,可能是 bigintreturn fn
}// factorialHelper 函数用于递归计算阶乘,接受两个参数 x 和 accumulator,并返回一个 Thunk
const factorialHelper = (x: bigint, accumulator: bigint): Thunk => {// 如果 x 小于等于 1,返回累积值(base case)if (x <= 1n) {return accumulator}// 否则,返回一个函数,该函数将计算下一个递归步骤return () => factorialHelper(x - 1n, x * accumulator)
}// factorial 函数用于启动阶乘计算,接受一个 number 类型的参数 n
const factorial = (n: number) => {// 使用 trampoline 函数调用 factorialHelper,传入 bigint 参数,初始累积值为 1nreturn trampoline(factorialHelper(BigInt(n), 1n))
}