Как вернуть правильный массив для f (0), оптимизированного для хвостового вызова Фибоначчи?

Поиграв с этим некоторое время, я нашел ответ, который возвращает все ожидаемые результаты:

function fibRecursiveTCO(n) {
  return fibonacciRecursiveTCO(n, 0, 1);
}

function fibonacciRecursiveTCO(n, a, b, result = [0, 1].slice(0, n + 1)) {
  if (n <= 1) {
    return result;
  }

  const next = a + b;
  result.push(next);
  return fibonacciRecursiveTCO(n - 1, b, next, result);
}

console.info(fibRecursiveTCO(0)); // [0]
console.info(fibRecursiveTCO(1)); // [0, 1]
console.info(fibRecursiveTCO(19)); // Array(20) [0, 1, ..., 4181]

Прежде всего, если вы используете рекурсию, воспользуйтесь ее преимуществами. В нашем случае у вас есть сложная задача, т. е. получить первые 19 чисел Фибоначчи, и вам всегда следует разложить свою проблему на похожие, но более простые подзадачи. Итак, каким должен быть результат для F(19)? Результатом должно быть F(17) + F(18) и так далее в обратном порядке.

Итак, давайте автоматизируем это разложение проблемы, пока не дойдем до тривиального случая F(1), который равен 1 и для которого вам нужен результат [0, 1]. Таким образом, вызывающая функция fibonacciRecursiveTCO(n - 1) получит числа Фибоначчи до F(n - 1), поэтому, когда функция вернется, в вашем распоряжении будут как F(n - 2), так и F(n - 1) (при условии, что n >= 2, потому что в противном случае у вас тривиальный случай), и вы можете сложить их и соединить результат с предыдущим результатом.

Теперь, когда мы правильно справились с более сложными случаями, разложив проблему на подзадачи и выстроив результат от тривиального к более сложному, давайте обратим внимание на тривиальные случаи.

Для простоты приведенная мной реализация предполагает, что n будет натуральным числом, и полностью игнорирует возможность отрицательных, недискретных или нечисловых входных данных. В профессиональной среде вам тоже придется задуматься, что делать в таких случаях, но здесь мы имеем дело только с натуральными числами.

У нас есть два тривиальных случая для натуральных чисел. Либо у вас n равно 0, либо 1. В обоих случаях мы возвращаем результат, то есть значение по умолчанию. Тем не менее, мы сталкиваемся с проблемой необходимости двух отдельных значений по умолчанию: [0] является значением по умолчанию, когда n равно 0, и [0, 1] является значением по умолчанию, когда n равно 1. Итак, какое из двух должно быть значением по умолчанию? Что ж, поскольку все входные данные будут сводиться к тому, что n равно 1 по умолчанию, за исключением исключительного случая, когда n равно 0, значение по умолчанию выбирается равным [0, 1].

Однако тогда что-то должно будет знать, что для n, равного 0, значением по умолчанию должно быть [0]. Я обработал это в fibRecursiveTCO, где будет указано, каков будет результат по умолчанию, если n было 0, но вы можете убедиться, что fibonacciRecursiveTCO недостижимо, кроме fibRecursiveTCO, поэтому значения по умолчанию будут гарантированно обработаны правильно. Для этой цели вы можете создать class и убедиться, что fibRecursiveTCO — это public, а fibonacciRecursiveTCO — это private. Подробнее здесь: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Classes/Private_properties

// Fibonacci recursive, tail call optimised, returns an array
function fibRecursiveTCO(n) {
  return n ? fibonacciRecursiveTCO(n) : fibonacciRecursiveTCO(n, [0]);
}

function fibonacciRecursiveTCO(n, result = [0, 1]) {
  if (n <= 1) {
      return result;
  }
  let previous = fibonacciRecursiveTCO(n - 1, result);
  return previous.concat(previous[previous.length - 2] + previous[previous.length - 1]);
}

console.info(fibRecursiveTCO(0)); // expected [0], returns [0, 1] instead
console.info(fibRecursiveTCO(1)); // [0, 1]
console.info(fibRecursiveTCO(19)); // Array(20) [0, 1, ..., 4181]

Этот интерфейс Loop и Recur, первоначально представленный в этих вопросах и ответах, способен выражать множество функций хвостовой рекурсии без необходимости писать вспомогательные помощники или опираться на другие императивные конструкции.

В этом первом примере мы вычисляем член 100 000^th примерно за 100 миллисекунд. Во втором примере мы покажем, как изменить функцию для вычисления списка терминов:

const fib = x =>
  Loop(                             // <- loop
    (n, a, b) =>                    // <- vars {n}, {a}, and {b}
      n <= 0n                       // <- exit condition
        ? String(a)                 // <- base case
        : Recur(n - 1n, b, a + b),  // <- recursive case
    BigInt(x),                      // <- init {n}
    0n,                             // <- init {a}
    1n,                             // <- init {b}
  )
  
function Loop(f, ...init) {
  let r = f(...init)          // <- apply f for initial result
  while (r instanceof Recur)  // <- if result is Recur
    r = f(...r)               // <- apply f again
  return r                    // <- return non-Recur result
}

function Recur(...v) {
  return Object.create(                              // <- simple object
    Recur.prototype,                                 // <- prototype
    {
      constructor: { value: Recur },                 // <- constructor
      [Symbol.iterator]: { value: _ => v.values() }, // <- values
    }
  )
}

console.time("fib(100000)")
document.body.textContent = fib(100000)
console.timeEnd("fib(100000)")

body { overflow-wrap: anywhere; }
.as-console-row:after { min-width: 150px; }

Теперь мы модифицируем, чтобы возвращать список вместо одного числа:

const fibs = x =>
  Loop(
    (n, a, b, r) =>           // <- additional var, {r}
      n <= 0n
        ? r                   // <- return result
        : Recur(
            n - 1n,
            b,
            a + b,
            (r.push(a), r),   // <- append {a} to result
          ),
    BigInt(x),
    0n,
    1n,
    [0n],                     // <- init result, {r}
  )
  
function Loop(f, ...init) {
  let r = f(...init)
  while (r instanceof Recur)
    r = f(...r)
  return r
}

function Recur(...v) {
  return Object.create(
    Recur.prototype,
    {
      constructor: { value: Recur },
      [Symbol.iterator]: { value: _ => v.values() },
    }
  )
}

console.time("fibs(1000)")
const result = fibs(1000)             // <- result is array
console.timeEnd("fibs(1000)")
document.body.textContent = result.join(", ")

body { overflow-wrap: anywhere; }
.as-console-row:after { min-width: 150px; }

Благодаря тому, как работает Loop, мы также можем инициализировать параметры цикла, используя значения по умолчанию. Я считаю, что это улучшает читаемость, когда количество параметров выше -

const fibs = x =>
  Loop(
    ( n = BigInt(x),         // <- init {n}
      a = 0n,                // <- init {a}
      b = 1n,                // <- init {b}
      r = [0n]               // <- init {r}
    ) =>
      n <= 0n
        ? r
        : Recur(
            n - 1n,          // <- next {n}
            b,               // <- next {a}
            a + b,           // <- next {b}
            (r.push(a), r),  // <- next {r}
          )
  )

Итак, базовый случай должен быть [0,1], потому что вам всегда нужно сложить два числа, но для fib(0) вы хотите вернуть только первое. Поскольку результат fib(n) всегда имеет n+1 чисел, вы всегда можете просто сделать if (n <= 1) return result.slice(0, n+1) в своем базовом случае.

Я бы обработал случай [0], не вызывая рекурсию, и использовал бы [0, 1] в качестве базового результата. Кроме того, движение вперед позволяет мне использовать числа из массива result для вычисления следующих значений.

function fibs(nth) {
  if (nth === 0) return [0];

  const fibonacciRecursiveTCO = (n, result) => { 
    if (n > nth) return result;

    return fibonacciRecursiveTCO(
      n + 1, 
      [...result, result.at(-2) + result.at(-1)]
    );
  }
  
  return fibonacciRecursiveTCO(2, [0, 1]);
}



console.info(fibs(0)); // [0]
console.info(fibs(1)); // [0, 1]
console.info(fibs(19));
console.time("fibs(1000)")
fibs(1000)
console.timeEnd("fibs(1000)")

Чтобы оптимизировать время, мы можем избежать повторного создания массива results с использованием расширения массива и вместо этого использовать Array.push():

function fibs(nth) {
  if (nth === 0) return [0];

  const fibonacciRecursiveTCO = (n, result) => { 
    if (n > nth) return result;

    return fibonacciRecursiveTCO(
      n + 1, 
      (result.push(result.at(-2) + result.at(-1)), result)
    );
  }
  
  return fibonacciRecursiveTCO(2, [0, 1]);
}


console.time("fibs(1000)");
const results = fibs(1000);
console.timeEnd("fibs(1000)");
document.body.textContent = results.join(", ")