javascript - 尾部调用优化 javascript

Question

注:这只是为了学习和提升自己。我知道数组可用的排序方法。我只是想了解 TCO 的基础知识。

目前正在尝试使用递归来研究排序算法。然而，当我尝试处理大型数据集(+4000 个对象)时，我仍然收到堆栈溢出错误。我正在尝试实现 TCO。我对这个概念还很陌生，但我想我已经掌握了它的要点。但是，我仍然收到堆栈溢出错误。

const sort = (arr, counter) => {
  if (!counter) {
    counter = arr.length - 1;
  }
  for (let n = 1; n <= counter; n++) {
    if(arr[n - 1] < arr[n]) {
      let placeHolder = arr[n];
      arr[n] = arr[n - 1];
      arr[n - 1] = placeHolder;
    }
  }
  counter -= 1;
  return counter === 0 ? arr : sort(arr, counter);
};

function sortRecursive(arr) {
  return sort(arr);
}

更新:

我设法让它工作，但我不太明白为什么。我成功地处理了 100,000 次递归，没有出现任何问题。我必须移动检查计数器是否已定义的 bool 值。但是，我不太明白为什么它会起作用。

const sort = (arr, counter) => {
  if (!counter) {
    counter = arr.length - 1;
  }
  for (let n = 1; n <= counter; n++) {
    if(arr[n - 1] < arr[n]) {
      let placeHolder = arr[n];
      arr[n] = arr[n - 1];
      arr[n - 1] = placeHolder;
    }
  }
  counter -= 1;
  if (counter === 0) {
    return arr;
  } else {
    return sort(arr, counter);
  }
};

function sortRecursive(arr) {
  return sort(arr, arr.length - 1);
}

输出:

let firstArr = [];
let secondArr = [];

for (let x = 0; x < 100000; x++) {
  firstArr.push(Math.ceil(Math.random() * 100000));
  secondArr.push(Math.ceil(Math.random() * 100000));
}

sortRecursive(firstArr);
//Array[100000]

Answer 1

如您所知，尾调用优化是一种编译器技术，它可以允许程序通过不为每个递归调用分配更多内存来无限递归。

Javascript 目前未优化尾部调用，但语言规范的 ES2015 标准包括 TCO。每次函数在 Javascript 中调用自身时，都会创建一个新的堆栈帧，分配新的内存，因此它最终会耗尽并崩溃。

有一些技术可以避免这种情况，包括 trampolines并且不使用递归循环。但目前你不能在 Javascript 中无限递归。