尾递归

2024年03月12日

柏拉文

越努力，越幸运

一、认识

---

尾递归Tail Recursion 函数调用自身，称为递归。如果尾调用自身，就称为尾递归。

递归非常耗费内存，因为需要同时保存成千上百个调用记录，很容易发生栈溢出错误（stack overflow）。但对于尾递归来说，由于只存在一个调用记录，所以永远不会发生栈溢出错误。

二、语法

---

三、场景

---

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));

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);