JavaScript | 再帰的なアルゴリズムの実例集

JavaScript JavaScript
スポンサーリンク

再帰アルゴリズムの実例集（後半）

後半では、より「実務で使う再帰」に踏み込みながら、初心者でも理解しやすいように構造化して解説していきます。 前半で学んだ ベースケース と 問題を小さくするステップ を軸に、実際の開発現場で頻出する再帰の使い方を丁寧に紐解いていきます。

フォルダ階層やツリー構造をたどる再帰

フォルダ階層やツリー構造は「入れ子」になっているため、再帰と非常に相性が良い構造です。 JavaScriptでよく扱う例として、JSON形式のツリーを再帰で処理するケースがあります。

JSONツリーを再帰で走査する

次のようなツリー構造を例にします。

const tree = {
  name: "root",
  children: [
    { name: "child1" },
    {
      name: "child2",
      children: [
        { name: "grandchild1" },
        { name: "grandchild2" }
      ]
    }
  ]
};
JavaScript

このツリーを「すべてのノード名を表示する」関数を再帰で書くとこうなります。

function traverse(node) {
  console.log(node.name);

  if (!node.children) {
    return;
  }

  for (const child of node.children) {
    traverse(child);
  }
}

traverse(tree);
JavaScript

深掘り：なぜ再帰が最適なのか

ツリー構造は「どれだけ深く入れ子になっているか」が事前に分かりません。 ループだけで書こうとすると、深さに応じて複雑な処理が必要になります。 再帰なら「子があるなら子を処理する」という自然な形で書けるため、コードが圧倒的に読みやすくなります。

DOMツリーを再帰で処理する

ブラウザのDOMもツリー構造です。 例えば「ページ内のすべての要素のタグ名を表示する」処理は再帰で簡潔に書けます。

function printTags(element) {
  console.log(element.tagName);

  for (const child of element.children) {
    printTags(child);
  }
}

printTags(document.body);
JavaScript

深掘り：DOM操作と再帰の注意点

DOMは巨大な場合があり、再帰が深くなりすぎるとコールスタックが増えすぎる可能性があります。 そのため、実務では 深さの制限 や 非同期処理 を組み合わせて安全性を高めることがあります。

再帰とセキュリティ：危険な再帰と安全な再帰

再帰は便利ですが、セキュリティの観点では注意すべき点があります。

危険な再帰

ユーザー入力をそのまま再帰処理に使うと、意図的に「深すぎるデータ」を渡されて コールスタックを溢れさせる攻撃（DoS攻撃）が成立します。

function unsafe(data) {
  if (!data.next) return;
  unsafe(data.next); // ユーザーが深さを操作できる
}
JavaScript

安全な再帰

安全にするには「深さの上限」を設けます。

function safeTraverse(node, depth = 0, maxDepth = 1000) {
  if (depth > maxDepth) {
    throw new Error("Depth limit exceeded");
  }

  if (!node.children) return;

  for (const child of node.children) {
    safeTraverse(child, depth + 1, maxDepth);
  }
}
JavaScript

深掘り：セキュリティスペシャリストの視点

再帰は「入力の深さに比例して負荷が増える」ため、攻撃者にとって扱いやすい弱点になります。 そのため、実務では次のような対策が一般的です。

  • 深さの上限を設ける
  • 入力データを検証する
  • 再帰ではなくループに置き換える
  • 非同期処理で負荷を分散する

再帰とイテレーション（ループ）の選び方

再帰は強力ですが、万能ではありません。 実務では「再帰で書くべきか、ループで書くべきか」を判断する必要があります。

再帰が向いている場面

  • ツリー構造
  • ネストが深いデータ
  • 数学的な再帰定義
  • 問題を自然に分割できる場合

ループが向いている場面

  • 単純な繰り返し
  • 深さが大きくなる可能性がある処理
  • パフォーマンスが重要な場面

深掘り：プロとしての判断基準

プロのエンジニアは「読みやすさ」と「安全性」の両方を考えます。 再帰は読みやすいが、深さが増えると危険。 ループは安全だが、ツリー構造では複雑になりやすい。 このトレードオフを理解することが、実務での再帰の使いこなしにつながります。

実務でよく使う再帰：ファイル探索の例

Node.jsでは、フォルダ内のファイルを再帰的に探索する処理が頻出します。

const fs = require("fs");
const path = require("path");

function walk(dir) {
  const entries = fs.readdirSync(dir);

  for (const entry of entries) {
    const fullPath = path.join(dir, entry);
    const stat = fs.statSync(fullPath);

    if (stat.isDirectory()) {
      walk(fullPath);
    } else {
      console.log(fullPath);
    }
  }
}

walk("./");
JavaScript

深掘り：実務での応用

この再帰は次のような場面で使われます。

  • 静的サイトジェネレーター
  • ビルドツール
  • セキュリティスキャン
  • ログ解析
  • 自動テストのファイル探索

再帰は「構造をたどる」処理に非常に強いことが分かります。

再帰の高度な応用：メモ化と動的計画法

前半で扱ったフィボナッチ数列は、再帰の美しい例ですが非効率でした。 ここでは「メモ化」を使って効率化します。

function fibonacciMemo() {
  const memo = {};

  function fib(n) {
    if (memo[n] !== undefined) return memo[n];
    if (n === 0) return 0;
    if (n === 1) return 1;

    const result = fib(n - 1) + fib(n - 2);
    memo[n] = result;
    return result;
  }

  return fib;
}

const fib = fibonacciMemo();
console.log(fib(40)); // 高速
JavaScript

深掘り：再帰と効率化の関係

再帰は「表現が美しい」反面、計算量が増えやすい構造です。 メモ化や動的計画法を組み合わせることで、 再帰の読みやすさと効率の両方を手に入れることができます。

再帰を使いこなすための最終ポイント

再帰は初心者にとって難しく感じることがありますが、 次の3つを意識すると一気に理解が進みます。

ベースケース

どこで終わるかを必ず明確にする。

問題を小さくする

毎回「少しだけ簡単な問題」にして自分自身を呼び出す。

コールスタックのイメージ

深く潜って、戻りながら計算する流れを頭の中で描く。

この3つを押さえれば、再帰は強力な武器になります。

次に学ぶべきステップ

再帰を理解したら、次は次のようなテーマに進むとスムーズです。

  • 関数型プログラミング
  • 非同期処理とイベントループ
  • アルゴリズムとデータ構造
  • ツリー構造の実践的な操作

どれも再帰と深く関係しており、理解が加速します。

必要であれば、読者向けに「再帰の練習問題集」や「実務で使う再帰パターン集」も作成できます。

前へ
12
スポンサーリンク
タイトルとURLをコピーしました