尾递归

2024年03月12日

柏拉文

越努力，越幸运

一、认识

---

尾递归Tail Recursion 是一种特殊的递归形式, 其中递归调用是函数中的最后一个操作。在尾调用的位置，当前函数不需要保留自己的执行上下文（例如局部变量、后续操作等），因此理论上可以复用当前的栈帧。如果 JavaScript 引擎实现了尾递归优化（Tail Recursion），那么尾递归就可以避免调用栈不断增长的问题。普通递归 非常耗费内存，因为需要同时保存成千上百个调用记录，很容易发生 栈溢出 错误（stack overflow）。但对于 尾递归 来说，由于只存在一个调用记录，所以永远不会发生栈溢出错误。

ES6 规范要求：ECMAScript 2015（ES6） 规范中要求实现尾调用优化，以便在尾调用位置复用调用栈。但这要求是在严格模式下进行的。尽管理论上 ES6 规范支持尾调用优化，但目前主流的 JavaScript 引擎（如 V8、SpiderMonkey 等）并未普遍实现这一特性。因此，在实际开发中，尽管我们可以采用尾递归的写法，但不能完全依赖底层引擎来保证优化效果。

二、语法

---

三、场景

---

3.1 阶乘

常规递归: 计算n的阶乘，最多需要保存n个调用记录，复杂度 O(n) 。

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

console.log(factorial(5));

尾递归优化: 尾递归，只保留一个调用记录，复杂度 O(1)

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

console.log(factorial(5));

在这个例子中，factorial 的递归调用是函数中的最后一步，理论上可以通过尾调用优化来复用栈帧，从而使得函数在处理大量递归时不会导致栈溢出。

3.2 斐波那契第 N 位

常规递归: 显然这个函数不符合尾调用优化的条件，因为返回语句中有一个相加的操作。结果，getFibByN(n) 的栈帧数的内存复杂度是 O(2^n)。计算 getFibByN(1000) 的时候其实是计算不出来的。

function getFibByN(n) {
  if (n < 2) {
    return n;
  }
  return getFibByN(n - 1) + getFibByN(n - 2);
}

const fibN = getFibByN(10);
console.log(fibN);

尾递归优化: 尾递归，只保留一个调用记录，复杂度 O(1) 。即使计算 getFibByN(1000) 的时候也很快。

function getFibByN(n,a=0,b=1){
    if(n === 0){
        return a;
    }
    return getFibByN(n-1,b,a+b);
}

const fibN = getFibByN(10);
console.log(fibN);