JavaScriptの再帰関数で10進数から2進数への変換を実装する方法

概要

数値を唯一の引数として受け取り、その数値を2進数表記に変換した文字列を返すJavaScript関数を作成します。本記事では、ループ処理ではなく再帰（recursion）を使った実装方法をわかりやすく解説します。

期待する動作は以下のとおりです。

f(4) = '100'
f(1000) = '1111101000'
f(8) = '1000'

サンプルコード

const decimalToBinary = (num) => {
  if(num >= 1) {
    // 奇数の場合：(num - 1) / 2 に対して再帰呼び出しを行い、
    // 余りの1を末尾に連結する
    if (num % 2) {
      return decimalToBinary((num - 1) / 2) + 1;
    } else {
      // 偶数の場合：num / 2 に対して再帰呼び出しを行い、
      // 末尾に「0」を連結する
      return decimalToBinary(num / 2) + 0;
    }
  } else {
    // 終了条件（ベースケース）
    return '';
  };
};
console.log(decimalToBinary(4));
console.log(decimalToBinary(1000));
console.log(decimalToBinary(8));

コードの仕組み

この関数は、10進数を2で割り続けることで各桁のビットを求め、再帰の戻り値に文字列として連結していきます。処理の流れは次のとおりです。

• 終了条件： 引数 num が1未満になった時点で空文字列を返し、再帰を停止します。
• 奇数の場合： num % 2 が真であれば、(num - 1) / 2 を引数に再帰呼び出しを行い、その結果に「1」を連結します。
• 偶数の場合： num / 2 を引数に再帰呼び出しを行い、その結果に「0」を連結します。
• 再帰が深くなるにつれて上位の桁から順に確定し、文字列の連結により最終的な2進表記が完成します。

なお、標準APIを使いたい場合は (4).toString(2) のように Number.prototype.toString() でも同様の結果が得られますが、再帰による自前実装はアルゴリズムの学習に最適です。

実行結果

コンソールには以下が出力されます。

100
1111101000
1000