JavaScriptの再帰処理で「+5」か「×3」の繰り返しにより特定の数に到達できるかを判定する方法

問題の概要

数値 1 からスタートして、「5を足す」または「3を掛ける」という操作を繰り返し適用することで、無限に多くの新しい数値を生成することができます。

本記事では、与えられた数値に対して、その数値を生成する一連の加算・乗算の手順が存在するかどうかを判定する関数をJavaScriptで実装します。そのような手順が存在すれば true を、存在しなければ false を返します。

例

例えば、数値 13 は「まず3を掛け、その後2回5を足す」という操作で到達できます（1 × 3 = 3 → 3 + 5 = 8 → 8 + 5 = 13）。したがって、この関数は 13 に対して true を返します。

一方、数値 15 はどのような操作の組み合わせでも到達できないため、この関数は 15 に対して false を返します。

アプローチ：再帰による探索

この問題は再帰（recursion）を使うことで解けます。現在の値から「5を足す」「3を掛ける」という2つの分岐を再帰的に試していき、目的の数値に一致する経路が1つでも見つかれば true を返します。

また、現在の値が目標の数値を超えた時点でその経路を打ち切る（枝刈りを行う）ことで、無駄な探索を省き、効率よく答えを導き出せます。

実装コード

const sequenceExists = (num, curr = 1) => {
   if(curr > num){
      return false;
   };
   if(curr === num){
      return true;
   };
   return sequenceExists(num, curr+5) || sequenceExists(num, curr*3);
};
console.log(sequenceExists(18));
console.log(sequenceExists(15));
console.log(sequenceExists(32));
console.log(sequenceExists(167));
console.log(sequenceExists(17));
console.log(sequenceExists(1119));

コードの解説

• 引数：num は目標の数値、curr は現在の値（デフォルトは開始値の 1）です。
• 枝刈り：curr が num を超えた時点で、これ以上の操作では目標に届かないため false を返して探索を打ち切ります。
• ベースケース：curr が num と一致すれば到達可能であることが確定するので、true を返します。
• 再帰ステップ：「5を足す場合」と「3を掛ける場合」の2つの再帰呼び出しの結果を論理OR（||）で結合します。どちらか片方でも成功すれば、全体として true になります。

実行結果

コンソールへの出力は次の通りです。

true
false
true
true
false
true

18（1 + 5 = 6 → 6 × 3 = 18）や 32（1 × 3 = 3 → 3 × 3 = 9 → 9 × 3 = 27 → 27 + 5 = 32）、1119 などは操作の組み合わせで到達可能ですが、15 や 17 はどのような順序で操作しても生成できません。