アルゴリズム - 14. 反復的DFS(スタックを使った木の走査)
algorithmstreetraversalstackiteration
By sko•10/9/2025•23 min read
反復的DFSを使用するタイミング
反復的DFSは、再帰を使わずに木やグラフを走査する必要がある場合に使用します。深い木でのスタックオーバーフローを避けるために最も一般的に使用されますが、以下のような用途にも適応できます:
- 二分木の走査(中順、前順、後順) - 典型的なユースケース
- 再帰の深さが制限を超える可能性がある場合のグラフ探索
- 状態空間探索 - 問題のすべての可能な構成や状態を探索
- パズル解決(8パズル、ルービックキューブ、数独)
- ゲーム状態の探索(チェスの手、三目並べの結果)
- 制約付きパス探索(鍵/扉のある迷路)
- 構成問題(充足可能性、制約充足)
- 明示的なスタックにより、探索パスの完全な可視性が得られ、訪問済み状態の追跡、カスタム枝刈り戦略の実装、またはゴール状態が見つかったときの実際の解パスの抽出が可能になります
- スタックを細かく制御する必要があるバックトラッキング問題
- メモリ使用量を制御した木のシリアライズ/デシリアライズ
- 正確なパスを維持しながら木/グラフでパスを見つける
- コールスタックを一時停止、再開、または検査する必要がある任意の走査
例題
一時停止可能なファイルシステム検索: 数百万のファイルが深いフォルダツリーに整理されたクラウドストレージシステム用のファイル検索機能を構築しています。検索には以下が必要です:
- パターンに一致するすべてのファイルを検索(例: "*.pdf")
- 1000ファイルごとに一時停止してプログレスバーを更新し、ユーザーがキャンセルしたかどうかを確認
- ユーザーが続行を希望する場合、中断した場所から正確に再開
- 一致する各ファイルの完全なパスを返す
- 深くネストされたフォルダ(数千レベルの深さ)でスタックオーバーフローを回避
次のようなフォルダ構造があるとします:
Root/
├── Documents/
│ ├── reports/
│ │ ├── report1.pdf ✓ 一致
│ │ └── data.txt
│ └── archive/
│ └── old.pdf ✓ 一致
└── Downloads/
└── ebook.pdf ✓ 一致なぜ再帰が機能しないのか:
- 再帰の途中で一時停止できない - 再帰呼び出しは完了するまでブロックされます
- 現在のパスを検査できない - コールスタックが隠されています
- スタックオーバーフローのリスク - 深くネストされたフォルダがメモリを使い果たします
- 再開できない - 中断された場合は最初からやり直す必要があります
答え: 反復的DFSは、一時停止、検査(ファイルパスを構築するため)、再開が可能な明示的なスタックを提供します - これは再帰の隠されたコールスタックでは不可能なことです。
反復的DFSが実際に行うこと
反復的DFSは、データ構造(通常はスタック)を使用して再帰的コールスタックを明示的にシミュレートします。再帰のためにシステムのコールスタックに依存するのではなく、走査順序を制御するために独自のスタックを手動で管理します。
これをファイリングキャビネットの検索に例えると:
- 再帰的DFS: 後ろに消えていくパンくずリストに従う - 今いる場所しか見えず、どこにいたか、何が探索すべきものとして残っているかは見えません。停止する必要がある場合、すべての進行状況が失われます。
- 反復的DFS: 可視的なブックマークリストを持つ - どのフォルダがまだ検索されていないかを正確に確認でき、いつでも一時停止でき、進行状況を確認でき、後で正確に同じ場所から再開できます
スタック操作の仕組み
コアパターン - "コールスタックを手動で管理する"
スタックで走査する場合:
-
プッシュノードをスタックに押し込む(再帰呼び出しのように)
- 後で探索するためにノードを保存します
- 順序が重要: 最後にプッシュされたものが最初に処理されます(LIFO)
-
ポップノードをスタックから取り出す(再帰呼び出しから戻るように)
- 次に作業するノードを取得します
- サブツリーを探索した後に「戻る」ことをシミュレートします
-
処理適切なタイミングでノードを処理(走査順序による)
- 前順: 最初に遭遇したときにすぐに処理(子をプッシュする前)
- 中順: 左に行けなくなったときに処理(左と右の探索の間)
- 後順: 両方の子が完了した後にのみ処理(2回目の訪問時)
- ファイル検索: ポップされたときに処理(パターンに一致するかどうかを確認)
-
必要に応じて状態を追跡(複雑な走査の場合)
- 後順: これが最初の訪問か2回目の訪問かを知るために「訪問済み」フラグが必要
- ファイル検索: スタックに
[node, path]ペアを格納して完全なパスを追跡 - グラフ走査: サイクルを避けるために訪問済みノードを追跡
- 一時停止可能な検索: 進行状況カウント、バッチ制限、完了ステータスを追跡
3つの古典的な木の走査
中順走査 - "左、ルート、右"
処理パターン:
- できるだけ左に行く(ノードをスタックにプッシュ)
- 左に行けないとき、現在のノードを処理
- 次に右サブツリーを探索
- スタックが空になるまで繰り返す
前順走査 - "ルート、左、右"
処理パターン:
- 訪問時にすぐにノードを処理
- 右の子を後で処理するためにプッシュ(存在する場合)
- 左の子に移動
- 左の子がないとき、スタックからポップ
後順走査 - "左、右、ルート"
処理パターン:
- 子を訪問したかどうかを追跡
- 最初の訪問: 子をスタックにプッシュ
- 2回目の訪問: ノードを処理
- 3つのパターンの中で最も複雑
これらのパターンが適用される場合
これらのパターンは、多くの実世界のシナリオに直接マッピングされます:
// 前順: 子の前に親を処理(トップダウン)
// 例: 木のコピー、構造のシリアライズ
// 中順: ソート順に処理(BSTの場合)
// 例: ソートされた値の取得、範囲クエリ
// 後順: 親の前に子を処理(ボトムアップ)
// 例: サイズの計算、ノードの削除、式の評価反復的DFSの美しさは、走査を完全に制御できることです - 一時停止したり、スタックを検査したり、実行中に走査戦略を変更したりできます!
最も重要な洞察
再帰呼び出しを明示的なスタック操作に置き換え、プッシュが呼び出しをシミュレートし、ポップが戻ることをシミュレートします - そして、スタック操作に対してノードを処理するタイミングを慎重に制御することで、再帰なしで任意の走査順序を実現できます。
メンタルノート: アルゴリズムの天才性は、探索すべきノードのシンプルな「やることリスト」を維持することにあります。スタックはそのリストに過ぎません。各ステップで、リストから次のアイテムを取得し(ポップ)、それに対して作業を行い、発見した新しいアイテムをリストに追加します(プッシュ)。この直接的なメンタルモデル - 「やることリストを処理する」 - は再帰について考えるよりも単純で、自然に一時停止、進行状況の検査、または再帰では提供できないカスタム状態の追跡を制御できます。
意思決定フレームワーク
各イテレーションで、次に何をすべきかを決定するために簡単な質問をします。これがファイル検索の例のパターンです:
ファイル検索の意思決定フロー(最もシンプルなパターン):
スタックから次のアイテムをポップ
↓
それはファイルかフォルダか?
↓
┌───────────────┬───────────────┐
│ ファイル │ フォルダ │
└───────────────┴───────────────┘
↓ ↓
一致するか? 子をスタック
↓ に追加
一致すれば保存 ↓
↓ ループ継続
ループ継続各ステップでの質問:
- "一時停止すべきか?" → 十分なノードを処理したかを確認
- "これはファイルかフォルダか?" → 何をすべきかを決定
- "パターンに一致するか?" → ファイルの場合のみ
- "どの子を探索するか?" → スタックにプッシュ
古典的な木の走査の場合、パターンはノードを処理したいタイミングに基づいて変わります:
前順(ノードを処理 → 子を探索):
ノードを訪問
↓
今すぐ処理(値を収集)
↓
右の子をプッシュ(後で保存)
↓
左の子に移動(すぐに探索)ユースケース: 木の構造をコピー、データをシリアライズ
中順(左を探索 → ノードを処理 → 右を探索):
左に行けるか?
↓
┌─────はい─────┬────いいえ────┐
│ │ │
現在をプッシュ ポップして処理
左に移動 次に右に移動ユースケース: BSTからソートされた値を取得
後順(子を探索 → ノードを処理):
ノードへの最初の訪問?
↓
┌─────はい─────┬────いいえ────┐
│ │ │
ノードをプッシュ 今すぐ処理
(訪問済みをマーク)(子が完了)
子をプッシュユースケース: 木のサイズを計算、ノードを削除
コアとなる決定: すべての走査は「子を探索するのに対してこのノードをいつ処理するか?」に集約されます。明示的なスタックにより、このタイミングを正確に制御できます。
コード
3つすべての走査タイプを実用的な例で探索しましょう。主な違いは、各ノードをいつ処理するかが子の探索に対してどうなるかです。
前順走査: 処理 → 探索
パターン: 子を探索する前に現在のノードを処理 ユースケース: 検索、木のコピー、前置式評価
// デモンストレーション用のシンプルな二分木ノード
type TreeNode = {
val: number;
left: TreeNode | null;
right: TreeNode | null;
};
// === 前順: 子の前にノードを処理 ===
function preorderIterative(root: TreeNode | null): Array<number> {
if (root == null) return [];
const result: Array<number> = [];
const stack: Array<TreeNode> = [root];
while (stack.length > 0) {
const node = stack.pop();
if (node == null) continue;
// 意思決定フレームワーク: ノードを見たときにすぐに処理
result.push(node.val); // 親を最初に処理
// 次に将来の探索のために子を追加
// 左が最初に処理されるように右を最初にプッシュ(LIFO)
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
return result;
}
// 例の木: 1
// / \
// 2 3
// / \
// 4 5
// 前順: [1, 2, 4, 5, 3] (ルート → 左 → 右)実世界の例: ファイルシステム検索
// ファイルシステムノードの定義
class FileNode {
name: string;
isFile: boolean;
children: Array<FileNode>;
constructor(
name: string,
isFile: boolean = false,
children: Array<FileNode> = []
) {
this.name = name;
this.isFile = isFile;
this.children = children; // FileNodeの配列(isFileがtrueの場合は空)
}
}
// 検索結果と進行状況の型定義
type SearchStatus = "paused" | "complete" | "already_complete";
type PausedSearchResult = {
status: "paused";
processed: number;
matches: number;
stackDepth: number;
};
type CompleteSearchResult = {
status: "complete" | "already_complete";
processed: number;
matches: number;
results: Array<string>;
};
type SearchResult = PausedSearchResult | CompleteSearchResult;
type ProgressInfo = {
nodesProcessed: number;
matchesFound: number;
remainingInStack: number;
isComplete: boolean;
};
// スタックエントリタイプ: ノードとルートからの完全なパスを持つオブジェクト
type StackEntry = {
node: FileNode;
path: string; // ルートからの完全なパス(例: "Root/Documents/reports")
};
// === 一時停止可能なファイル検索 ===
// パターンに一致するファイルを検索し、一時停止と再開の機能を持つ
// 前順走査を使用: 子を探索する前に各ノードを処理
class PausableFileSearch {
private root: FileNode;
private pattern: string;
private searchStack: Array<StackEntry>;
private matchingFiles: Array<string>;
private totalNodesProcessed: number;
private isComplete: boolean;
constructor(root: FileNode, pattern: string) {
this.root = root;
this.pattern = pattern;
// 明示的なスタックは、ノードとルートからの完全なパスを持つオブジェクトを格納
// 最初は、ルートのパスはその名前だけ
this.searchStack = [{ node: root, path: root.name }];
// 検索結果と進行状況の追跡
this.matchingFiles = [];
this.totalNodesProcessed = 0;
this.isComplete = false;
}
// 木を走査し、ノードを処理して子に展開
// ノード制限に達するか走査を完了するまで続行
traverse(nodeLimit: number = 1000): SearchResult {
let nodesProcessedThisCall = 0;
while (true) {
// 意思決定フレームワーク: 走査は完了したか?
const isStackEmpty = this.searchStack.length === 0;
if (isStackEmpty) {
// 探索するノードがもうない - 検索完了
this.isComplete = true;
return {
status: "complete",
processed: this.totalNodesProcessed,
matches: this.matchingFiles.length,
results: this.matchingFiles,
};
}
// 意思決定フレームワーク: 一時停止すべきか?
const shouldPause = nodesProcessedThisCall >= nodeLimit;
if (shouldPause) {
// ここで一時停止 - スタックは正確な位置を保存
return {
status: "paused",
processed: this.totalNodesProcessed,
matches: this.matchingFiles.length,
stackDepth: this.searchStack.length,
};
}
// スタックから次のノードとその完全なパスをポップ
// 上記でスタックが空でないことを既に確認済み
const stackEntry = this.searchStack.pop();
// 上記の空チェックのため、これは決して起こらないはずですが、
// TypeScriptは制御フローを理解していません
if (stackEntry == null) {
throw new Error("Unexpected: stack was empty after non-empty check");
}
const currentNode = stackEntry.node;
const currentPath = stackEntry.path;
nodesProcessedThisCall++;
this.totalNodesProcessed++;
// 前順: 子を探索する前に現在のノードを処理
// 意思決定フレームワーク: これはファイルかフォルダか?
if (currentNode.isFile) {
// ファイルがパターンに一致するかを確認
const matchesPattern = currentNode.name.endsWith(this.pattern);
if (matchesPattern) {
this.matchingFiles.push(currentPath);
}
} else {
// フォルダの場合 - 将来の探索のためにスタックに子を追加
// これは現在のノードを処理した後に起こります(前順)
// 左から右に処理されるように逆順でプッシュ
const children = currentNode.children;
for (let i = children.length - 1; i >= 0; i--) {
const childNode = children[i];
const childPath = `${currentPath}/${childNode.name}`;
// 完全なパスと共に子をプッシュ
this.searchStack.push({ node: childNode, path: childPath });
}
}
}
}
// 一時停止した場所から走査を再開
resume(nodeLimit: number = 1000): SearchResult {
const canResume = !this.isComplete && this.searchStack.length > 0;
if (canResume) {
return this.traverse(nodeLimit);
}
return {
status: "already_complete",
processed: this.totalNodesProcessed,
matches: this.matchingFiles.length,
results: this.matchingFiles,
};
}
// 現在の進行状況を取得
getProgress(): ProgressInfo {
return {
nodesProcessed: this.totalNodesProcessed,
matchesFound: this.matchingFiles.length,
remainingInStack: this.searchStack.length,
isComplete: this.isComplete,
};
}
}
// === 使用例: ファイルシステム検索 ===
// 例からファイルシステムツリーを構築
const fileSystem = new FileNode("Root", false, [
new FileNode("Documents", false, [
new FileNode("reports", false, [
new FileNode("report1.pdf", true),
new FileNode("data.txt", true),
]),
new FileNode("archive", false, [new FileNode("old.pdf", true)]),
]),
new FileNode("Downloads", false, [new FileNode("ebook.pdf", true)]),
]);
// PDFファイルの検索を作成
const search = new PausableFileSearch(fileSystem, ".pdf");
// 最初の走査: 2ノードを処理してから一時停止
let result = search.traverse(2);
console.log(`ステータス: ${result.status}`);
console.log(`処理済み: ${result.processed} ノード`);
console.log(`一致数: ${result.matches}`);
// 一時停止結果の型ガード
if (result.status === "paused") {
console.log(`スタック深度: ${result.stackDepth} (ここから再開可能)`);
}
// 進行状況を確認
console.log(search.getProgress());
// 再開: さらに3ノードを走査してから一時停止
result = search.resume(3);
console.log(`ステータス: ${result.status}`);
console.log(`処理済み合計: ${result.processed} ノード`);
console.log(`一致数: ${result.matches}`);
// 完了するまで再開
result = search.resume(1000);
console.log(`ステータス: ${result.status}`);
console.log(`処理済みノード合計: ${result.processed}`);
console.log(`一致合計: ${result.matches}`);
// 完了結果の型ガード
if (result.status === "complete" || result.status === "already_complete") {
console.log("\n一致するファイル:");
result.results.forEach((path) => console.log(` ${path}`));
}中順走査: 左を探索 → 処理 → 右を探索
パターン: 左と右の子を探索する間にノードを処理 ユースケース: 二分探索木(ソートされた出力を提供)、式木
// === 中順: 子の間でノードを処理 ===
function inorderIterative(root: TreeNode | null): Array<number> {
if (root == null) return [];
const result: Array<number> = [];
const stack: Array<TreeNode> = [];
let current: TreeNode | null = root;
// 処理を明示的にするヘルパー関数
function processNode(value: number) {
result.push(value); // またはその他のロジック
}
while (current != null || stack.length > 0) {
// 意思決定フレームワーク: まずできるだけ左に行く
while (current != null) {
stack.push(current); // スタック操作: 後で保存
current = current.left;
}
// 左に行けないときにノードを処理
const node = stack.pop(); // スタック操作: 保存されたノードを取得
if (node != null) {
processNode(node.val); // 左と右の間で処理(スタック操作ではない)
current = node.right; // 次に右サブツリーを探索
}
}
return result;
}
// 例のBST: 4
// / \
// 2 6
// / \ / \
// 1 3 5 7
// 中順: [1, 2, 3, 4, 5, 6, 7] (ソート済み!)実世界の例: データベースインデックス走査
何をしているか: ユーザーレコードを含むデータベーステーブルがあり、すべてのユーザーを名前のアルファベット順で取得したいとします。テーブル全体をスキャンしてソートする代わりに、データベースは二分探索木(BST)インデックスを使用して名前を整理します。
問題: "name"列のBSTインデックスが与えられたとき、すべてのユーザーレコードをアルファベット順で取得します。
データベーステーブルの例(Users):
| Record ID | Name | Email | | --------- | ------- | --------------- | | 101 | Charlie | charlie@ex.com | | 102 | Alice | alice@ex.com | | 103 | David | david@ex.com | | 104 | Bob | bob@ex.com | | 105 | Alice | alice2@ex.com |
"Name"列に構築されたインデックスツリー:
"Charlie" → [101]
/ \
"Alice" → [102,105] "David" → [103]
\
"Bob" → [104]各ノードは以下を格納:
- key: 名前(インデックス値)
- recordIds: その名前を持つ行IDの配列(例: 2人のAlice: 行102と105)
目標: 中順走査を使用してすべての名前をアルファベット順に取得: Alice → Bob → Charlie → David
// データベースインデックス用の二分探索木
class IndexNode {
key: string; // インデックス値(例: ユーザー名"Alice")
recordIds: Array<number>; // このキー値を持つすべてのデータベース行のID
left: IndexNode | null = null;
right: IndexNode | null = null;
constructor(key: string, recordId: number) {
this.key = key;
this.recordIds = [recordId]; // 最初は1つのレコードIDを含む
}
}
// アルファベット順にすべてのレコードを検索
// root: 既に構築されたBSTインデックスのルート
// 戻り値: アルファベット順の名前からレコードIDへのマップ
function getAllRecordsInOrder(
root: IndexNode | null // BSTは既に構造によってソート順を維持
): Map<string, Array<number>> {
const orderedRecords = new Map<string, Array<number>>();
const stack: Array<IndexNode> = [];
let current = root;
while (current != null || stack.length > 0) {
// 最も左のノードに移動
while (current != null) {
stack.push(current);
current = current.left;
}
// ノードを処理(ソート順)
const node = stack.pop();
if (node != null) {
orderedRecords.set(node.key, node.recordIds);
current = node.right;
}
}
return orderedRecords;
}
// 名前の例のインデックスツリー:
// "Charlie"
// / \
// "Alice" "David"
// \
// "Bob"
//
// 中順走査により: Alice → Bob → Charlie → David (アルファベット順!)後順走査: 探索 → 処理
パターン: すべての子を探索した後にノードを処理 ユースケース: サイズの計算、木の削除、後置式評価
// === 後順: 子の後にノードを処理 ===
function postorderIterative(root: TreeNode | null): Array<number> {
if (root == null) return [];
const result: Array<number> = [];
const stack: Array<{ node: TreeNode; visited: boolean }> = [
{ node: root, visited: false },
];
while (stack.length > 0) {
const entry = stack[stack.length - 1]; // トップを覗く
// 意思決定フレームワーク: このノードの子を既に訪問したか?
if (!entry.visited) {
// このノードを最初に見た - 訪問済みとマークし、子を追加
entry.visited = true;
// 子を追加(左が最初に処理されるように右を最初に)
if (entry.node.right) {
stack.push({ node: entry.node.right, visited: false });
}
if (entry.node.left) {
stack.push({ node: entry.node.left, visited: false });
}
} else {
// このノードを2回目に見た - 子が完了、処理する
stack.pop();
result.push(entry.node.val); // 子の後に処理
}
}
return result;
}
// 例の木: 1
// / \
// 2 3
// / \
// 4 5
// 後順: [4, 5, 2, 3, 1] (左 → 右 → ルート)実世界の例: ディレクトリサイズの計算
// サイズを持つファイルシステムノード
class FileSystemNode {
name: string;
isFile: boolean;
size: number; // ファイルの場合: 実際のサイズ。ディレクトリの場合: 子から計算
children: Array<FileSystemNode>;
constructor(name: string, isFile: boolean, size: number = 0) {
this.name = name;
this.isFile = isFile;
this.size = size;
this.children = [];
}
}
// 各ディレクトリの合計サイズを計算(子を最初に処理する必要があります!)
function calculateDirectorySizes(root: FileSystemNode): Map<string, number> {
const directorySizes = new Map<string, number>();
const stack: Array<{
node: FileSystemNode;
path: string;
visited: boolean;
}> = [{ node: root, path: root.name, visited: false }];
while (stack.length > 0) {
const entry = stack[stack.length - 1];
if (!entry.visited) {
// 最初の訪問: 子をスタックに追加
entry.visited = true;
if (!entry.node.isFile) {
// すべての子を処理のために追加
for (const child of entry.node.children) {
stack.push({
node: child,
path: `${entry.path}/${child.name}`,
visited: false,
});
}
}
} else {
// 2回目の訪問: 子が処理済み、このノードのサイズを計算
stack.pop();
if (entry.node.isFile) {
// ファイル: そのサイズを使用
// 親ディレクトリがこれを合計します
} else {
// ディレクトリ: すべての子のサイズを合計
let totalSize = 0;
for (const child of entry.node.children) {
if (child.isFile) {
// ファイル: ファイルの直接サイズを使用
totalSize += child.size;
} else {
// サブディレクトリ: 既に計算された合計を取得
// 後順は、この子ディレクトリが完全に処理されたことを保証
// 以前に(親の前にスタックからポップ)、そのため完全な
// サイズは既にマップに格納されています。二重カウントではありません -
// 再計算する代わりに事前計算された合計を使用しています。
const childPath = `${entry.path}/${child.name}`;
const childDirectoryTotal = directorySizes.get(childPath) || 0;
totalSize += childDirectoryTotal;
}
}
// このディレクトリの合計サイズをマップに格納
// (この合計は、このディレクトリが子として現れるときに使用されます)
directorySizes.set(entry.path, totalSize);
entry.node.size = totalSize; // ノード自体を更新
}
}
}
return directorySizes;
}
// ファイルシステムの例:
// Root/
// ├── docs/ (30KB合計)
// │ ├── file1.txt (10KB)
// │ └── file2.txt (20KB)
// └── images/ (150KB合計)
// ├── pic1.jpg (100KB)
// └── pic2.jpg (50KB)
//
// 後順は、Root/のサイズ(180KB)を計算する前に
// docs/とimages/のサイズを計算することを保証まとめ: 各走査をいつ使用するか
| 走査 | いつ処理するか | ユースケース | | ---------- | -------------------- | -------------------------------------------- | | 前順 | 子の前 | 検索、コピー、シリアライズ | | 中順 | 左と右の間 | BSTからのソート済み取得 | | 後順 | すべての子の後 | サイズ計算、クリーンアップ、依存関係 |
反復的DFSの美しさは、スタックを明示的に管理することで、走査順序を完全に制御できることです - 子を探索するタイミングに対してノードを処理するタイミングを変更するだけです!
疑問解消
よくある疑問: "反復的DFSは本当に再帰的DFSができるすべてのことを処理できるのか? より広く言えば、反復はすべての再帰ロジックを置き換えることができるのか、DFSだけではないのか? それとも、再帰が根本的に必要なケースがあるのか?"
基本的な等価性: 反復はすべての再帰を置き換えることができるか?
はい、理論的には任意の再帰アルゴリズムを反復的なものに変換できます。 これはDFSに特有のものではありません - コンピュータサイエンスの基本原則です。
これが普遍的に真である理由: すべての再帰アルゴリズムはコールスタックを使用します。反復バージョンは、代わりに明示的なスタックデータ構造を使用するだけです。常に独自のスタックを作成できるため、常に再帰を反復に置き換えることができます。
これはすべての再帰アルゴリズムに適用されます:
- 木/グラフの走査(DFS、BFSのバリエーション)
- 分割統治(クイックソート、マージソート、二分探索)
- バックトラッキング(Nクイーン、数独ソルバー、順列)
- 動的計画法(トップダウン再帰またはボトムアップ反復)
- 数学的再帰(フィボナッチ、階乗、ハノイの塔)
DFSに特有の場合、等価性が機能する理由は次のとおりです:
再帰呼び出しを行うと、システムは自動的に2つのことを行います:
- ローカル変数を保存コールスタックに
- 戻る場所を記憶呼び出しが完了したときに
反復的DFSでは、これらの同じ2つのことを手動で行います:
- 状態を保存明示的なスタックに(スタックエントリに変数を格納)
- 実行フローを制御ループとスタック操作で
例による証明 - これが再帰関数とその反復的同等物です:
// 再帰: 木の高さを計算
function heightRecursive(node: TreeNode | null): number {
if (node == null) return 0;
// 再帰呼び出しはこれらの計算をコールスタックに保存
const leftHeight = heightRecursive(node.left);
const rightHeight = heightRecursive(node.right);
return Math.max(leftHeight, rightHeight) + 1;
}
// 反復: 同じ計算、明示的なスタック
function heightIterative(root: TreeNode | null): number {
if (root == null) return 0;
// 部分結果を格納する必要があります - これが複雑にする原因です
type StackEntry = {
node: TreeNode;
phase: "initial" | "left_done" | "right_done";
leftHeight?: number; // 左サブツリーからの結果を格納
rightHeight?: number; // 右サブツリーからの結果を格納
};
const stack: Array<StackEntry> = [{ node: root, phase: "initial" }];
let finalHeight = 0;
while (stack.length > 0) {
const entry = stack[stack.length - 1]; // 覗く
if (entry.phase === "initial") {
// 最初の訪問 - 左の子を探索
entry.phase = "left_done";
if (entry.node.left) {
stack.push({ node: entry.node.left, phase: "initial" });
} else {
entry.leftHeight = 0; // 左の子がない = 高さ0
}
} else if (entry.phase === "left_done") {
// 左が完了 - 結果をキャプチャして右を探索
if (entry.node.left) {
// 左の子の結果をスタックからポップ
const leftResult = stack.pop();
if (leftResult != null) {
entry.leftHeight = finalHeight; // 左の計算された高さを保存
}
}
entry.phase = "right_done";
if (entry.node.right) {
stack.push({ node: entry.node.right, phase: "initial" });
} else {
entry.rightHeight = 0;
}
} else {
// 両方の子が完了 - このノードの高さを計算
if (entry.node.right) {
stack.pop(); // 右の子をポップ
entry.rightHeight = finalHeight;
}
const leftH = entry.leftHeight ?? 0;
const rightH = entry.rightHeight ?? 0;
finalHeight = Math.max(leftH, rightH) + 1;
stack.pop(); // このノードをポップ
}
}
return finalHeight;
}要点: はい、任意の再帰的DFSを反復的に変換できます。しかし、複雑さの違いを見てください!
DFSを超えて: 反復に変換された他の再帰アルゴリズム
これがDFS特有のものではないことを証明するために、他の古典的な再帰アルゴリズムとその反復的同等物を示します:
例1: クイックソート(分割統治)
// 再帰: エレガントな15行
function quicksortRecursive(arr: Array<number>, low: number, high: number) {
if (low >= high) return;
const pivot = partition(arr, low, high);
quicksortRecursive(arr, low, pivot - 1); // 左をソート
quicksortRecursive(arr, pivot + 1, high); // 右をソート
}
// 反復: 範囲を追跡するために明示的なスタックが必要
function quicksortIterative(arr: Array<number>) {
const stack: Array<[number, number]> = [[0, arr.length - 1]];
while (stack.length > 0) {
const range = stack.pop();
if (range == null) continue;
const [low, high] = range;
if (low >= high) continue;
const pivot = partition(arr, low, high);
// 両方の範囲をスタックにプッシュ(再帰呼び出しを置き換える)
stack.push([low, pivot - 1]);
stack.push([pivot + 1, high]);
}
}例2: フィボナッチ(数学的再帰)
// 再帰: 自然な数学的定義
function fibRecursive(n: number): number {
if (n <= 1) return n;
return fibRecursive(n - 1) + fibRecursive(n - 2);
}
// 反復: ボトムアップアプローチ(実際により効率的!)
function fibIterative(n: number): number {
if (n <= 1) return n;
let prev = 0;
let curr = 1;
for (let i = 2; i <= n; i++) {
const next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}例3: バックトラッキング - すべての順列を生成
// 再帰: クリーンなバックトラッキングパターン
function permuteRecursive(nums: Array<number>): Array<Array<number>> {
const result: Array<Array<number>> = [];
function backtrack(current: Array<number>, remaining: Array<number>) {
if (remaining.length === 0) {
result.push([...current]);
return;
}
for (let i = 0; i < remaining.length; i++) {
backtrack(
[...current, remaining[i]],
[...remaining.slice(0, i), ...remaining.slice(i + 1)]
);
}
}
backtrack([], nums);
return result;
}
// 反復: 複雑な状態管理
function permuteIterative(nums: Array<number>): Array<Array<number>> {
const result: Array<Array<number>> = [];
const stack: Array<{
current: Array<number>;
remaining: Array<number>;
}> = [{ current: [], remaining: nums }];
while (stack.length > 0) {
const state = stack.pop();
if (state == null) continue;
if (state.remaining.length === 0) {
result.push(state.current);
continue;
}
// すべての可能な次の状態をプッシュ
for (let i = state.remaining.length - 1; i >= 0; i--) {
stack.push({
current: [...state.current, state.remaining[i]],
remaining: [
...state.remaining.slice(0, i),
...state.remaining.slice(i + 1),
],
});
}
}
return result;
}重要な観察: どの場合でも、再帰を反復に変換できますが、再帰バージョンは通常よりクリーンで直感的です。反復バージョンは、再帰が自動的に処理する状態を手動で管理する必要があります。
それぞれをいつ使用すべきか?
等価性は、反復が常に優れていることを意味するわけではありません。実用的な意思決定フレームワークは次のとおりです:
再帰的DFSを使用する場合:
- ✅ 自然なフィット - 問題が本質的に再帰的(木の操作、分割統治)
- ✅ シンプルさが重要 - よりクリーンで、理解しやすく、保守しやすい
- ✅ スタックオーバーフローのリスクなし - 木の深さが妥当(通常1000レベル未満が安全)
- ✅ 戻り値が必要 - サブツリーから結果を収集して組み合わせる必要がある
- ✅ 標準的な走査 - 再帰が最もクリアな基本的な前/中/後順
例: 再帰がここで完璧
// 木の最大値を見つける - 再帰が自然にクリーン
function findMax(node: TreeNode | null): number {
if (node == null) return -Infinity;
return Math.max(node.val, findMax(node.left), findMax(node.right));
}
// 反復バージョンは複雑な状態追跡が必要 - 価値がない!反復的DFSを使用する場合:
- ✅ スタックオーバーフローのリスク - 非常に深い木(数百万のノード、数千のレベル)
- ✅ 一時停止/再開が必要 - 一時停止して後で再開する必要がある長時間実行の検索
- ✅ スタック検査が必要 - 現在のパスまたは走査状態を確認する必要がある
- ✅ カスタム制御フロー - バックトラック、サブツリーのスキップ、または実行中の走査の変更が必要
- ✅ メモリ制約 - システムのコールスタックが制限されているが、ヒープメモリは利用可能
例: 反復がここで必要
// 一時停止可能な検索 - 再帰では不可能
class PausableSearch {
private stack: Array<StackEntry>;
search(limit: number) {
while (this.stack.length > 0 && processed < limit) {
// ノードを処理...
// ここで一時停止して後で再開できます!
}
}
}実世界の経験則
特定の理由がない限り、ほとんどのアルゴリズムで再帰をデフォルトとします:
- 95%の問題 → 再帰を使用(よりシンプル、クリーン、保守しやすい)
- 特別なニーズのある5% → 反復を使用(スタックオーバーフローのリスク、一時停止/再開、明示的な状態検査)
再帰は劣っていません - ほとんどの再帰問題に対する自然で好ましいソリューションです。反復アプローチは、再帰の制限が実際の問題になったときの強力なツールであり、常に使用すべき「より良い」アプローチではありません。
なぜ再帰が通常好まれるか:
- 問題構造に一致 - 木の走査、分割統治、バックトラッキングは本質的に再帰的な概念
- 自己文書化コード - 再帰コードは、数学的定義や問題の説明のように読める
- エラーが少ない - 手動のスタック管理がないということは、バグが少ないということ
- コンパイラの最適化 - 現代のコンパイラは、末尾再帰関数を自動的に最適化できる
反復が必要になる場合:
- スタック深度制限 - システムのコールスタックは通常数千フレームに制限されている
- 外部制約 - プログラムの再起動間で状態を保存/復元する必要がある
- パフォーマンスクリティカル - 関数呼び出しのオーバーヘッドを排除(ただし、コンパイラはしばしばこれを行う)
- 教育目的 - 再帰が内部で何をしているかを理解する
なぜ複雑さが違うのか?
再帰バージョンがよりシンプルなのは、言語ランタイムが状態管理を処理するからです:
- コールスタックは自動的にローカル変数を保存
- 戻り値は自動的に上に流れる
- 実行は自動的に正しい場所で再開される
反復バージョンはこれらすべてを手動で実装する必要があります:
- スタックエントリに変数を明示的に保存
- 処理のどの段階にいるかを手動で追跡
- 各段階の遷移を処理するコードを書く
しかし、反復がクリーンな場合はどうでしょうか?
素晴らしい質問: "再帰の主な利点が明確さであるなら、反復も同様にクリーンな場合、反復の方が良いのではないか?"
はい、絶対に! 反復ソリューションが同様にクリーンで直感的な場合、以下の理由から再帰よりも良いことがよくあります:
- ✅ スタックオーバーフローのリスクなし
- ✅ 実行の明示的な制御
- ✅ デバッグが簡単(スタックを直接検査できる)
- ✅ パフォーマンスが向上(関数呼び出しのオーバーヘッドなし)
反復が自然にクリーンな例: フィボナッチ
// 再帰: 数学的定義に一致するが指数時間複雑度
function fibRecursive(n: number): number {
if (n <= 1) return n;
return fibRecursive(n - 1) + fibRecursive(n - 2); // 同じ値を再計算!
}
// 反復: 実際により単純でより効率的
function fibIterative(n: number): number {
if (n <= 1) return n;
let prev = 0,
curr = 1;
for (let i = 2; i <= n; i++) {
[prev, curr] = [curr, prev + curr]; // クリーンな1行更新
}
return curr;
}この場合、反復が優れています - よりシンプルで読みやすく、より効率的です。
反復が自然にクリーンな他のケース:
-
末尾再帰関数 - これらは単にループの変装:
// 末尾再帰: 最後の操作が再帰呼び出し function sumRecursive(n: number, acc: number = 0): number { if (n === 0) return acc; return sumRecursive(n - 1, acc + n); // 末尾呼び出し } // 反復は同様に明確でスタックフレームを回避 function sumIterative(n: number): number { let sum = 0; for (let i = 1; i <= n; i++) { sum += i; } return sum; } -
ボトムアップ動的計画法 - 反復がより自然:
// 基本ケースからソリューションを構築することは自然に反復的 function climbStairs(n: number): number { if (n <= 2) return n; let prev = 1, curr = 2; for (let i = 3; i <= n; i++) { [prev, curr] = [curr, prev + curr]; } return curr; } -
シンプルな線形走査 - ループが再帰よりも明確:
// 配列の合計 - 反復がより自然 function sumArray(arr: Array<number>): number { let sum = 0; for (const num of arr) { sum += num; } return sum; }
重要な原則: 特定の問題に対してよりクリーンな方を使用します。
ほとんどの再帰問題(木、分割統治、バックトラッキング)は、以下を含むため再帰の方がクリーンです:
- 複数の再帰呼び出し
- サブツリーからの戻り値の組み合わせ
- 自然な階層構造
しかし、反復が同様またはより直感的な場合(末尾再帰、線形走査、ボトムアップDP)、上記の利点のために反復を優先します。
結論:
- 反復はすべての再帰を置き換えることができるか(DFSだけでなく)? はい、理論的には任意の再帰アルゴリズムを反復的に変換できます。
- 常に再帰の代わりに反復を使用すべきか? いいえ、絶対にそうではありません。
- 常に反復の代わりに再帰を使用すべきか? いいえ、絶対にそうではありません。
- 実際のルール: 特定の問題に対してよりクリーンで直感的なアプローチを使用します。 実際には、これは木/グラフ/バックトラッキングには再帰(よりクリーン)、末尾再帰パターン/線形走査/ボトムアップDPには反復(同様またはより明確)を意味します。