JavaScriptでトリボナッチ数列を生成する方法

トリボナッチ数列とは？

トリボナッチ数列は、フィボナッチ数列を一般化した数列です。フィボナッチ数列では各項が「直前の2項の和」になるのに対し、トリボナッチ数列では各項が「直前の3項の和」になります。

トリボナッチ数列の最初のいくつかの項は以下のとおりです。

0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149

たとえば7番目の項「13」は、直前の3項である「2」「4」「7」を足した値（2 + 4 + 7 = 13）に一致します。

作成する関数の仕様

ここでは、数値 num を唯一の引数として受け取り、トリボナッチ数列の最初の num 個の項を要素にもつ配列を返すJavaScript関数を実装します。

たとえば f(6) を呼び出した場合、戻り値は最初の6項を並べた [0, 1, 1, 2, 4, 7] となります。

コード例

以下がその実装コードです。

const tribonacci = (num = 1) => {
  if (num === 1) {
    return 0;
  }
  if (num === 2 || num === 3) {
    return 1;
  } else {
    return tribonacci(num - 1) +
           tribonacci(num - 2) +
           tribonacci(num - 3);
  }
};

const trib = num => {
  const res = [];
  for (let i = 1; i <= num; i++) {
    res.push(tribonacci(i));
  }
  return res;
};

console.log(trib(11));

実行結果

コンソールには次のように出力されます。

[ 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149 ]

補足：メモ化による高速化

上記の素朴な再帰実装では、同じ値を何度も計算し直すため、num が大きくなると計算量が指数関数的に増加します。計算結果をキャッシュする「メモ化」を導入すると、計算量を O(n) まで抑えることができます。

const memo = {};

const tribonacci = (num = 1) => {
  if (memo[num] !== undefined) return memo[num];
  let result;
  if (num === 1) {
    result = 0;
  } else if (num === 2 || num === 3) {
    result = 1;
  } else {
    result = tribonacci(num - 1) +
             tribonacci(num - 2) +
             tribonacci(num - 3);
  }
  memo[num] = result;
  return result;
};

このように、トリボナッチ数列はフィボナッチ数列とほぼ同じ要領で実装でき、「ベースケース（初期条件）の数だけ異なる」という点が実装時のポイントになります。