では今回は、再帰の「本領発揮」分野である ツリー探索（Tree Traversal） を、プログラミング初心者でも「実感して理解できる」ように、段階的にやさしく解説します。
1. まず「ツリー構造」ってなに？
ツリー構造とは、「親 → 子 → 孫…」のように階層があるデータのことです。
たとえばパソコンのフォルダ構成：
root
├─ photos
│ ├─ trip
│ └─ family
└─ docs
├─ work
└─ personal
JavaScriptで表すと👇のようになります：
const tree = {
name: "root",
children: [
{
name: "photos",
children: [
{ name: "trip", children: [] },
{ name: "family", children: [] }
]
},
{
name: "docs",
children: [
{ name: "work", children: [] },
{ name: "personal", children: [] }
]
}
]
};
2. 「ツリー探索」とは？
ツリーの中を「全部たどる」ことです。
たとえば「すべてのフォルダ名を表示したい」など。
ツリー探索には2つの代表的な方法があります：
| 方法 | 呼び出し順 | よく使う場面 |
|---|---|---|
| 深さ優先探索（DFS） | 子ノードをどんどん掘り下げてから戻る | 構造を全部調べたい時 |
| 幅優先探索（BFS） | 同じ階層を順に処理 | 「距離の近い順」で探す時 |
ここでは 再帰を使った「深さ優先探索」 に集中します。
3. 再帰でツリーをたどる（基本版）
function traverse(node) {
console.log(node.name); // まず自分を処理
for (const child of node.children) {
traverse(child); // 子を再帰的に探索
}
}
traverse(tree);
出力：
root
photos
trip
family
docs
work
personal
🟢 これが最も基本的な「深さ優先探索（DFS）」の流れです。
4. 特定のノードを検索する再帰関数
「名前が work のノードを探す」関数を作ってみましょう。
function findNode(node, targetName) {
if (node.name === targetName) {
return node; // 見つけた！
}
for (const child of node.children) {
const result = findNode(child, targetName);
if (result) return result; // 子の中で見つかったら即返す
}
return null; // 見つからなかった
}
const result = findNode(tree, "work");
console.log(result);
出力：
{ name: "work", children: [] }
ポイント解説
if (node.name === targetName)が「終了条件（ベースケース）」- 見つからなければ子ノードを再帰的に探す
return resultで「見つかったらすぐ戻る」
5. 全ノードを「リスト」として集める
フォルダ名をまとめて配列にして返す関数：
function collectNames(node) {
let names = [node.name]; // 自分の名前をまず追加
for (const child of node.children) {
names = names.concat(collectNames(child)); // 子の名前を結合
}
return names;
}
console.log(collectNames(tree));
// ["root", "photos", "trip", "family", "docs", "work", "personal"]
🟡 こうすれば「再帰呼び出しの結果（子の配列）」をまとめて扱えます。
6. 応用：階層をインデントして表示する
「どのフォルダがどの階層にあるか」をわかりやすく出力する例です。
function printTree(node, depth = 0) {
console.log(" ".repeat(depth * 2) + node.name); // 深さに応じてインデント
for (const child of node.children) {
printTree(child, depth + 1); // 深さを1つ増やして呼ぶ
}
}
printTree(tree);
出力：
root
photos
trip
family
docs
work
personal
📘 コツ：
- 再帰では「深さ（depth）」のような補助的な引数を使うと、階層情報を簡単に扱える。
depth + 1で階層を一段深くしていくのが再帰らしいポイントです。
7. 実務に近い使い方（再帰＋条件）
「ファイルの中から .txt だけをリストアップしたい」など、条件を加えた探索。
const fileTree = {
name: "root",
children: [
{ name: "note.txt", children: [] },
{ name: "photo.jpg", children: [] },
{ name: "sub", children: [
{ name: "report.txt", children: [] },
{ name: "data.json", children: [] }
]
}
]
};
function findTxtFiles(node) {
let result = [];
if (node.name.endsWith(".txt")) {
result.push(node.name);
}
for (const child of node.children) {
result = result.concat(findTxtFiles(child));
}
return result;
}
console.log(findTxtFiles(fileTree));
// ["note.txt", "report.txt"]
🔹 再帰の中で条件をチェックし、該当したものだけ配列に追加。
🔹 実務では「ファイル検索」「メニュー階層の生成」「コメントツリー」などでよく使われます。
8. まとめ
| ポイント | 内容 |
|---|---|
| 🌿 再帰は「ツリー」を扱うのが得意 | 子を同じ形で処理する構造にピッタリ |
| 🧱 ベースケース（終了条件） | 子がいない、見つけた、などで終了 |
| 🔁 引数で状態を渡す | depth や path を渡すことで柔軟に |
| 📦 配列やオブジェクトを結合 | 結果をまとめて返す構成にする |
追加チャレンジ（自作課題）
- ファイルパス付きで出力する
→root/photos/tripのように親フォルダも含めた文字列を出力する。 - ノードの数を数える
→ 再帰を使ってツリー全体にいくつのノードがあるかを数える。 - 深さの最大値を求める
→ 「最も深い階層はいくつか？」を調べる。