スタックを使用した再帰から反復への変換: 実践ガイド

再帰はコンピュータ サイエンスにおける強力な手法であり、ツリー トラバーサル、深さ優先検索、バックトラッキング アルゴリズムなどのタスクによく使用されます。ただし、再帰は関数呼び出しのオーバーヘッドと呼び出しスタックの維持により、時間とスペースの両方の点で効率が低下する可能性があります。場合によっては、明示的なスタックを使用して再帰呼び出しをシミュレートする反復アプローチに再帰を変換すると有益です。この記事では、JavaScript のスタックを使用して再帰的アルゴリズムを反復的アルゴリズムに変換するためのステップバイステップのガイドを提供します。

---

再帰を反復に変換する理由

再帰を反復に変換する理由はいくつかあります。

1. スタック オーバーフロー: 深い再帰呼び出しにより呼び出しスタックが枯渇し、スタック オーバーフローが発生する可能性があります。明示的なスタックを使用すると、この問題を回避できます。
2. 効率: 反復ソリューションは、呼び出しスタックを維持するオーバーヘッドを必要としないため、一般にメモリ効率が高くなります。
3. より良い制御: 明示的なスタックを使用すると、特にバックトラッキングが関係する場合に、アルゴリズムの実行をより詳細に制御できます。

---

スタックを使用して再帰を反復に変換するためのテンプレート

スタックを使用して再帰関数を反復関数に変換する場合、一般的なアプローチは、さまざまな種類のアルゴリズム (ツリー トラバーサル、バックトラッキング問題、グラフ トラバーサルなど) 間でも同様です。以下は、さまざまなシナリオに適応できる柔軟なテンプレートです。

---

一般的なテンプレート

1. 再帰関数(例)

function recursiveFunction(args) {
    // Base case
    if (baseCondition) {
        // Handle the base case
        return;
    }

    // Recursive calls
    for (let i = 0; i < someLimit; i++) {
        recursiveFunction(newArgs);
    }
}

2. スタックを使用した反復関数

上記の再帰関数を反復関数に変換するには、次の手順に従います。

function iterativeFunction(args) {
    // Initialize the stack
    let stack = [initialState];

    // Loop until the stack is empty
    while (stack.length > 0) {
        // Pop the current state from the stack
        let currentState = stack.pop();

        // Handle the base case (optional, since we can check on each iteration)
        if (baseCondition) {
            continue;  // Skip or handle the base case
        }

        // Process the current state
        processState(currentState);

        // Push next states onto the stack
        for (let i = 0; i < someLimit; i++) {
            let newState = generateNewState(currentState, i);
            stack.push(newState);
        }
    }
}

---

テンプレートの内訳

1. スタックを初期化します:
   
   スタックは開始状態で初期化される必要があります。これは、最初の引数またはトラバーサルの最初のノードである可能性があります。

2. スタックをループします:
   
   ループは、元の関数で行われた再帰呼び出しを表す項目がスタックにある限り継続します。

3. 基本条件の処理:
   
   再帰では、基本条件によってさらなる再帰が必要かどうかがチェックされます。反復アプローチでは、ループ内で同じチェックを実行できます。基本条件が満たされた場合は、 continue を使用して以降の処理をスキップできます。

4. 現在の状態を処理します:
   
   現在の反復の状態を処理します (現在の再帰呼び出しで発生する処理と同等)。

5. 次の状態をプッシュ:
   
   再帰関数が新しい再帰関数を呼び出すのと同じように、ここでは次の状態 (つまり、処理される関数の引数またはノード) をスタックにプッシュします。

---

変換例: 順序ツリー走査

再帰的バージョン:

function recursiveFunction(args) {
    // Base case
    if (baseCondition) {
        // Handle the base case
        return;
    }

    // Recursive calls
    for (let i = 0; i < someLimit; i++) {
        recursiveFunction(newArgs);
    }
}

スタックを使用した反復バージョン:

function iterativeFunction(args) {
    // Initialize the stack
    let stack = [initialState];

    // Loop until the stack is empty
    while (stack.length > 0) {
        // Pop the current state from the stack
        let currentState = stack.pop();

        // Handle the base case (optional, since we can check on each iteration)
        if (baseCondition) {
            continue;  // Skip or handle the base case
        }

        // Process the current state
        processState(currentState);

        // Push next states onto the stack
        for (let i = 0; i < someLimit; i++) {
            let newState = generateNewState(currentState, i);
            stack.push(newState);
        }
    }
}

---

再帰を反復に変換する例

例 1: グラフ上の深さ優先検索 (DFS)

深さ優先検索 (DFS) は通常、再帰を使用して実装されます。再帰的 DFS アルゴリズムは次のとおりです:

function inorderTraversal(root) {
    if (root === null) return;
    inorderTraversal(root.left);
    console.log(root.value);
    inorderTraversal(root.right);
}

スタックを使用した反復バージョン:

function inorderTraversalIterative(root) {
    let stack = [];
    let current = root;

    while (stack.length > 0 || current !== null) {
        // Reach the leftmost node
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }

        // Visit the node
        current = stack.pop();
        console.log(current.value);

        // Move to the right node
        current = current.right;
    }
}

この例では、スタックは訪問するノードを明示的に保持し、ループを使用して再帰呼び出しをシミュレートします。

---

例 2: 順序どおりのツリー走査 (反復)

バイナリ ツリーの順序どおりの走査は通常、再帰的に行われます。再帰バージョンは次のとおりです:

function dfs(graph, node, visited = new Set()) {
    if (visited.has(node)) return;
    console.log(node);
    visited.add(node);

    for (let neighbor of graph[node]) {
        dfs(graph, neighbor, visited);
    }
}

スタックを使用した反復バージョン:

function dfsIterative(graph, startNode) {
    let stack = [startNode];
    let visited = new Set();

    while (stack.length > 0) {
        let node = stack.pop();

        if (visited.has(node)) continue;

        console.log(node);
        visited.add(node);

        // Add neighbors to the stack in reverse order to maintain DFS order
        for (let neighbor of graph[node].reverse()) {
            if (!visited.has(neighbor)) {
                stack.push(neighbor);
            }
        }
    }
}

この場合、スタックは訪問するノードの追跡に役立ち、内部ループは左端のノードに到達するまでツリーの左側を下に移動します。

---

例 3: サブセットの生成 (バックトラッキング)

セットのサブセットを生成するためのバックトラッキング アプローチは、次のように再帰的に実装できます。

function inorderTraversal(root) {
    if (root === null) return;
    inorderTraversal(root.left);
    console.log(root.value);
    inorderTraversal(root.right);
}

スタックを使用した反復バージョン:

function inorderTraversalIterative(root) {
    let stack = [];
    let current = root;

    while (stack.length > 0 || current !== null) {
        // Reach the leftmost node
        while (current !== null) {
            stack.push(current);
            current = current.left;
        }

        // Visit the node
        current = stack.pop();
        console.log(current.value);

        // Move to the right node
        current = current.right;
    }
}

反復バージョンでは、スタックを使用して再帰的な関数呼び出しをシミュレートします。 currentSubset はインプレースで変更され、スタックは新しい状態をプッシュすることでバックトラックを処理します。

---

例 4: 順列の生成

セットのすべての順列を生成するには、通常、再帰が使用されます。

function subsets(nums) {
    let result = [];
    function backtrack(start, currentSubset) {
        result.push([...currentSubset]);
        for (let i = start; i < nums.length; i++) {
            currentSubset.push(nums[i]);
            backtrack(i + 1, currentSubset);
            currentSubset.pop();
        }
    }
    backtrack(0, []);
    return result;
}

スタックを使用した反復バージョン:

function subsetsIterative(nums) {
    let stack = [{start: 0, currentSubset: []}];
    let result = [];

    while (stack.length > 0) {
        let { start, currentSubset } = stack.pop();
        result.push([...currentSubset]);

        // Explore subsets by including elements from `start` onwards
        for (let i = start; i < nums.length; i++) {
            currentSubset.push(nums[i]);
            stack.push({ start: i + 1, currentSubset: [...currentSubset] });
            currentSubset.pop(); // backtrack
        }
    }

    return result;
}

この反復バージョンでは、スタックを使用して順列の現在の状態を保存します。バックトラッキングは、スタックから状態をプッシュおよびポップすることによって処理されます。

---

例 5: N-Queens 問題 (バックトラッキング)

N-Queens 問題は、多くの場合、再帰的バックトラッキングを使用して解決されます。

function permute(nums) {
    let result = [];
    function backtrack(start) {
        if (start === nums.length) {
            result.push([...nums]);
            return;
        }
        for (let i = start; i < nums.length; i++) {
            [nums[start], nums[i]] = [nums[i], nums[start]];  // swap
            backtrack(start + 1);
            [nums[start], nums[i]] = [nums[i], nums[start]];  // backtrack (swap back)
        }
    }
    backtrack(0);
    return result;
}

スタックを使用した反復バージョン:

function recursiveFunction(args) {
    // Base case
    if (baseCondition) {
        // Handle the base case
        return;
    }

    // Recursive calls
    for (let i = 0; i < someLimit; i++) {
        recursiveFunction(newArgs);
    }
}

---

結論

スタックを使用して再帰を反復に変換することは、多くのアルゴリズム、特にバックトラッキングやツリー/グラフの走査を伴うアルゴリズムにとって貴重な手法です。明示的なスタックを使用することで、深い再帰を回避し、関数の状態を手動で管理し、アルゴリズムの実行をより適切に制御できるようになります。これらの例は、独自のコードで同様の問題に取り組む際のガイドとして役立ちます。

以上がスタックを使用した再帰から反復への変換: 実践ガイドの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。