Menukar Rekursi kepada Lelaran Menggunakan Tindanan: Panduan Praktikal

Rekursi ialah teknik yang berkuasa dalam sains komputer, selalunya digunakan untuk tugas seperti rentas pokok, carian pertama mendalam dan algoritma penjejakan ke belakang. Walau bagaimanapun, rekursi boleh menjadi kurang cekap dari segi masa dan ruang disebabkan oleh overhed panggilan fungsi dan mengekalkan timbunan panggilan. Dalam sesetengah kes, adalah berfaedah untuk menukar rekursi kepada pendekatan berulang menggunakan tindanan eksplisit untuk mensimulasikan panggilan rekursif. Artikel ini menyediakan panduan langkah demi langkah untuk menukar algoritma rekursif kepada yang berulang menggunakan timbunan dalam JavaScript.

---

Mengapa Menukar Rekursi kepada Lelaran?

Terdapat beberapa sebab mengapa anda mungkin mahu menukar rekursi kepada lelaran:

1. Limpahan Tindanan: Panggilan rekursif dalam boleh meletihkan tindanan panggilan, yang membawa kepada limpahan tindanan. Menggunakan tindanan eksplisit boleh mengelakkan masalah ini.
2. Kecekapan: Penyelesaian berulang secara amnya lebih cekap ingatan, kerana ia tidak memerlukan overhed untuk mengekalkan timbunan panggilan.
3. Kawalan Lebih Baik: Menggunakan tindanan eksplisit boleh memberi anda lebih kawalan ke atas pelaksanaan algoritma, terutamanya apabila penjejakan ke belakang terlibat.

---

Templat untuk Menukar Rekursi kepada Lelaran Menggunakan Tindanan

Apabila menukar fungsi rekursif kepada satu lelaran menggunakan tindanan, pendekatan umum kekal serupa merentas pelbagai jenis algoritma (seperti lintasan pokok, masalah menjejak ke belakang atau lintasan graf). Di bawah ialah templat fleksibel yang boleh disesuaikan dengan pelbagai senario.

---

Templat Umum

1. Fungsi Rekursif (Contoh)

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

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

2. Fungsi Berulang Menggunakan Tindanan

Untuk menukar fungsi rekursif di atas menjadi satu lelaran, kami ikuti langkah berikut:

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);
        }
    }
}

---

Pecahan Templat

1. Mulakan Tindanan:
   
   Tindanan hendaklah dimulakan dengan keadaan permulaan, yang boleh menjadi argumen awal atau nod pertama dalam traversal.

2. Gelung Melalui Tindanan:
   
   Gelung berterusan selagi tindanan mempunyai item, mewakili panggilan rekursif yang akan dibuat dalam fungsi asal.

3. Pengendalian Keadaan Asas:
   
   Dalam rekursi, keadaan asas menyemak sama ada rekursi selanjutnya diperlukan. Dalam pendekatan berulang, anda boleh melakukan pemeriksaan yang sama di dalam gelung. Anda boleh menggunakan terus melangkau pemprosesan selanjutnya apabila syarat asas dipenuhi.

4. Proses Keadaan Semasa:
   
   Proseskan keadaan lelaran semasa (bersamaan dengan pemprosesan yang akan berlaku pada panggilan rekursif semasa).

5. Tekan Negeri Seterusnya:
   
   Sama seperti fungsi rekursif memanggil fungsi rekursif baharu, di sini anda menolak keadaan seterusnya (iaitu, argumen fungsi atau nod untuk diproses) ke dalam tindanan.

---

Contoh Penukaran: Traversal Pokok Tertib

Versi Rekursif:

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

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

Versi Berulang Menggunakan Tindanan:

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);
        }
    }
}

---

Contoh Menukar Rekursi kepada Lelaran

Contoh 1: Depth-First Search (DFS) pada Graf

Depth-First Search (DFS) biasanya dilaksanakan menggunakan rekursi. Berikut ialah algoritma DFS rekursif:

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

Versi Berulang Menggunakan Tindanan:

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;
    }
}

Dalam contoh ini, tindanan secara eksplisit memegang nod yang akan dilawati dan kami menggunakan gelung untuk mensimulasikan panggilan rekursif.

---

Contoh 2: Traversal Pokok Tertib (Berulang)

Perjalanan tertib pokok binari biasanya dilakukan secara rekursif. Berikut ialah versi rekursif:

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);
    }
}

Versi Berulang Menggunakan Tindanan:

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);
            }
        }
    }
}

Dalam kes ini, timbunan membantu menjejaki nod untuk dilawati dan gelung dalam merentasi ke bawah sebelah kiri pokok sehingga mencapai nod paling kiri.

---

Contoh 3: Menjana Subset (Penjejakan Belakang)

Pendekatan menjejak ke belakang untuk menjana subset set boleh dilaksanakan secara rekursif seperti ini:

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

Versi Berulang Menggunakan Tindanan:

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;
    }
}

Versi berulang menggunakan tindanan untuk mensimulasikan panggilan fungsi rekursif. Subset semasa diubah suai di tempatnya dan timbunan mengendalikan penjejakan ke belakang dengan menolak keadaan baharu ke atasnya.

---

Contoh 4: Menjana Pilihatur

Untuk menjana semua pilih atur set, ulangan biasanya digunakan:

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;
}

Versi Berulang Menggunakan Tindanan:

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;
}

Versi lelaran ini menggunakan tindanan untuk menyimpan keadaan semasa pilih atur. Penjejakan ke belakang dikendalikan dengan menolak dan mengeluarkan keadaan daripada tindanan.

---

Contoh 5: Masalah N-Queens (Penjejakan Belakang)

Masalah N-Queens selalunya diselesaikan menggunakan penjejakan belakang rekursif:

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;
}

Versi Berulang Menggunakan Tindanan:

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

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

---

Kesimpulan

Menukar rekursi kepada lelaran menggunakan tindanan ialah teknik yang berharga untuk banyak algoritma, terutamanya yang melibatkan pengesanan belakang atau lintasan pokok/graf. Dengan menggunakan tindanan eksplisit, kami boleh mengelakkan rekursi mendalam, mengurus keadaan fungsi secara manual dan memastikan kami mempunyai kawalan yang lebih baik ke atas pelaksanaan algoritma. Contoh ini harus menjadi panduan untuk membantu anda menangani masalah yang sama dalam kod anda sendiri.

Atas ialah kandungan terperinci Menukar Rekursi kepada Lelaran Menggunakan Tindanan: Panduan Praktikal. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!