Rekursion ist eine leistungsstarke Technik in der Informatik, die häufig für Aufgaben wie Baumdurchquerung, Tiefensuche und Backtracking-Algorithmen verwendet wird. Aufgrund des Mehraufwands für Funktionsaufrufe und der Verwaltung des Aufrufstapels kann die Rekursion jedoch sowohl zeitlich als auch räumlich weniger effizient sein. In einigen Fällen ist es von Vorteil, die Rekursion in einen iterativen Ansatz umzuwandeln und einen expliziten Stapel zur Simulation der rekursiven Aufrufe zu verwenden. Dieser Artikel bietet eine Schritt-für-Schritt-Anleitung zum Konvertieren rekursiver Algorithmen in iterative mithilfe eines Stacks in JavaScript.
Es gibt mehrere Gründe, warum Sie Rekursion in Iteration umwandeln möchten:
Beim Konvertieren einer rekursiven Funktion in eine iterative Funktion mithilfe eines Stapels bleibt der allgemeine Ansatz für verschiedene Arten von Algorithmen (wie Baumdurchläufe, Backtracking-Probleme oder Graphdurchläufe) ähnlich. Nachfolgend finden Sie eine flexible Vorlage, die an verschiedene Szenarien angepasst werden kann.
function recursiveFunction(args) {
// Base case
if (baseCondition) {
// Handle the base case
return;
}
// Recursive calls
for (let i = 0; i < someLimit; i++) {
recursiveFunction(newArgs);
}
}
Um die obige rekursive Funktion in eine iterative umzuwandeln, führen wir die folgenden Schritte aus:
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);
}
}
}
Stack initialisieren:
Der Stapel sollte mit dem Startzustand initialisiert werden, bei dem es sich um die Anfangsargumente oder den ersten Knoten in einer Durchquerung handeln kann.
Schleife durch den Stapel:
Die Schleife wird so lange fortgesetzt, wie der Stapel Elemente enthält, die die rekursiven Aufrufe darstellen, die in der ursprünglichen Funktion durchgeführt worden wären.
Grundzustandsbehandlung:
Bei der Rekursion prüft die Basisbedingung, ob eine weitere Rekursion erforderlich ist. Beim iterativen Ansatz können Sie die gleiche Prüfung innerhalb der Schleife durchführen. Mit „Weiter“ können Sie die weitere Verarbeitung überspringen, wenn die Grundbedingung erfüllt ist.
Verarbeiten Sie den aktuellen Status:
Verarbeiten Sie den Status der aktuellen Iteration (entspricht der Verarbeitung, die beim aktuellen rekursiven Aufruf erfolgen würde).
Push Next States:
Genau wie die rekursive Funktion neue rekursive Funktionen aufruft, schieben Sie hier die nächsten Zustände (d. h. zu verarbeitende Funktionsargumente oder Knoten) auf den Stapel.
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);
}
}
}
Depth-First Search (DFS) wird üblicherweise mithilfe von Rekursion implementiert. Hier ist der rekursive DFS-Algorithmus:
function inorderTraversal(root) {
if (root === null) return;
inorderTraversal(root.left);
console.log(root.value);
inorderTraversal(root.right);
}
Iterative Version mit einem Stapel:
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;
}
}
In diesem Beispiel enthält der Stapel explizit die Knoten, die besucht werden sollen, und wir verwenden die Schleife, um die rekursiven Aufrufe zu simulieren.
Das Durchlaufen eines Binärbaums in der richtigen Reihenfolge erfolgt normalerweise rekursiv. Hier ist die rekursive Version:
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);
}
}
Iterative Version mit einem Stapel:
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);
}
}
}
}
In diesem Fall hilft der Stapel dabei, zu besuchende Knoten zu verfolgen, und die innere Schleife durchläuft die linke Seite des Baums nach unten, bis sie den Knoten ganz links erreicht.
Der Backtracking-Ansatz zum Generieren von Teilmengen einer Menge kann wie folgt rekursiv implementiert werden:
function inorderTraversal(root) {
if (root === null) return;
inorderTraversal(root.left);
console.log(root.value);
inorderTraversal(root.right);
}
Iterative Version mit einem Stapel:
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;
}
}
Die iterative Version verwendet einen Stapel, um die rekursiven Funktionsaufrufe zu simulieren. Das currentSubset wird direkt geändert und der Stack übernimmt das Backtracking, indem er neue Zustände darauf schiebt.
Um alle Permutationen einer Menge zu generieren, wird normalerweise Rekursion verwendet:
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;
}
Iterative Version mit einem Stapel:
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;
}
Diese iterative Version verwendet den Stapel, um den aktuellen Status der Permutation zu speichern. Das Backtracking wird durch das Verschieben und Entfernen der Zustände vom Stapel erledigt.
Das N-Queens-Problem wird oft durch rekursives Backtracking gelöst:
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;
}
Iterative Version mit einem Stapel:
function recursiveFunction(args) {
// Base case
if (baseCondition) {
// Handle the base case
return;
}
// Recursive calls
for (let i = 0; i < someLimit; i++) {
recursiveFunction(newArgs);
}
}
Die Umwandlung von Rekursion in Iteration mithilfe eines Stapels ist eine wertvolle Technik für viele Algorithmen, insbesondere für solche, die Backtracking oder Baum-/Graph-Traversal beinhalten. Durch die Verwendung eines expliziten Stapels können wir tiefe Rekursionen vermeiden, Funktionszustände manuell verwalten und sicherstellen, dass wir eine bessere Kontrolle über die Ausführung des Algorithmus haben. Diese Beispiele sollen als Leitfaden dienen, um Ihnen bei der Bewältigung ähnlicher Probleme in Ihrem eigenen Code zu helfen.
Das obige ist der detaillierte Inhalt vonKonvertieren von Rekursion in Iteration mithilfe eines Stapels: Ein praktischer Leitfaden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
So zeigen Sie gespeicherte Prozeduren in MySQL an
Was bedeutet Liquidation?
Mehrere Möglichkeiten zur Datenerfassung
So öffnen Sie eine Bak-Datei
Einführung in Artikel-Tag-Attribute
Top Ten der Rangliste der digitalen Geldwechsel
So lösen Sie das Problem, dass der DNS-Server nicht reagiert
So zentrieren Sie ein Div in CSS
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
