在 JavaScript 中封装尾调用优化的实用程序？

Question

我一直在阅读 JavaScript 中有关递归函数和尾调用优化 (TCO) 的内容。我的目标是克服递归函数中的堆栈溢出：

function factorial(n) {
    function recur(n, acc) {
        if (n === 0) {
            return acc;
        } else {
            return recur(n - 1, n * acc);
        }
    }
    return recur(n, 1);
}

factorial(5); // 120
console.log(factorial(4585759)); // Maximum call stack size exceeded

我找到了如何使用 thunk 和 trampoline 来克服递归函数中的堆栈溢出：

let thunk = function (fn) {
    return function() {
        let args = Array.prototype.slice.apply(arguments);
        return function() { return fn.apply(this, args); };
    };
};

function trampoline(f) {
    while (f && f instanceof Function) {
        f = f();
    }
    return f;
}

function factorial(n) {
    let recur = function(x, n) {
        if (n === 0) {
            return x;
        } else {
            return thunk(recur)(n * x, n - 1);
        }
    };
    return trampoline(thunk(recur)(1, n));
}

console.log(factorial(5)); // 120
console.log(factorial(4585759)); // Infinity

但是，我不喜欢我被迫编写递归函数的方式。我找到了一些名为 TCO:

的函数的实现

function tco(fn) {
  var active, nextArgs;
  return function() {
    var result;
    nextArgs = arguments;
    if (!active) {
      active = true;
      while (nextArgs) {
        result = fn.apply(this, [nextArgs, nextArgs = null][0]);
      }
      active = false;
    }
    return result;
  };
}

该函数应允许以下内容：

let factorialToc = tco(function(n) {
    function recur(n, acc) {
        if (n === 0) {
            return acc;
        } else {
            return recur(n - 1, n * acc);
        }
    };
    return recur(n, 1);
});

但它不起作用：

factorialToc(5); // 120
console.log(factorialToc(4585759)); // Maximum call stack size exceeded

有封装TCO的实用函数吗？

Answer 1

您将 tco 函数应用于非递归 factorialToc 函数，而不是 recur 导致堆栈溢出。应该是

function factorialToc(n) {
    const recur = tco(function(n, acc) {
        if (n === 0) {
            return acc;
        } else {
            return recur(n - 1, n * acc);
        }
    });
    return recur(n, 1);
}

在 JavaScript 中封装尾调用优化的实用程序？

Utility to encapsulate tail-call optimisation in JavaScript?

javascript

recursion

functional-programming

tail-recursion