Ik heb tijdens mijn jarenlange programmeerwerk vrij veel recursie gebruikt om eenvoudige problemen op te lossen, maar ik ben me er volledig van bewust dat je soms iteratie nodig hebt vanwege geheugen-/snelheidsproblemen.
Dus ergens in het verre verleden ging ik proberen te ontdekken of er een “patroon” of een tekstboek-manier bestond om een algemene recursiebenadering van iteratie te transformeren en ik vond niets. Of in ieder geval niets dat ik me kan herinneren dat het zou helpen.
- Zijn er algemene regels?
- Is er een “patroon”?
Antwoord 1, autoriteit 100%
Meestal vervang ik een recursief algoritme door een iteratief algoritme door de parameters die normaal gesproken aan de recursieve functie worden doorgegeven op een stapel te plaatsen. In feite vervangt u de programma-stack door een van uzelf.
var stack = [];
stack.push(firstObject);
// while not empty
while (stack.length) {
// Pop off end of stack.
obj = stack.pop();
// Do stuff.
// Push other objects on the stack as needed.
...
}
Opmerking: als je meer dan één recursieve aanroep hebt en je wilt de volgorde van de aanroepen behouden, dan moet je ze in omgekeerde volgorde aan de stapel toevoegen:
foo(first);
foo(second);
moet worden vervangen door
stack.push(second);
stack.push(first);
Bewerken: het artikel eliminatie van stapels en recursie (of Artikel Back-up link) gaat dieper in op dit onderwerp.
Antwoord 2, autoriteit 22%
Eigenlijk is de meest gebruikelijke manier om dit te doen, uw eigen stapel te behouden. Hier is een recursieve quicksort-functie in C:
void quicksort(int* array, int left, int right)
{
if(left >= right)
return;
int index = partition(array, left, right);
quicksort(array, left, index - 1);
quicksort(array, index + 1, right);
}
Hier is hoe we het iteratief kunnen maken door onze eigen stapel te behouden:
void quicksort(int *array, int left, int right)
{
int stack[1024];
int i=0;
stack[i++] = left;
stack[i++] = right;
while (i > 0)
{
right = stack[--i];
left = stack[--i];
if (left >= right)
continue;
int index = partition(array, left, right);
stack[i++] = left;
stack[i++] = index - 1;
stack[i++] = index + 1;
stack[i++] = right;
}
}
Het is duidelijk dat dit voorbeeld de stapelgrenzen niet controleert… en in werkelijkheid zou je de stapel kunnen rangschikken op basis van het slechtste geval gegeven linker- en rechterwaarden. Maar je snapt het idee.
Antwoord 3, autoriteit 16%
Het lijkt erop dat niemand heeft aangegeven waar de recursieve functie zichzelf meer dan eens in het lichaam aanroept en afhandelt om terug te keren naar een specifiek punt in de recursie (d.w.z. niet primitief-recursief). Er wordt gezegd dat elke recursie kan worden omgezet in iteratie, dus het lijkt erop dat dit mogelijk moet zijn.
Ik heb zojuist een C#-voorbeeld bedacht om dit te doen. Stel dat je de volgende recursieve functie hebt, die werkt als een postorder-traversal, en dat AbcTreeNode een drietallige boom is met wijzers a, b, c.
public static void AbcRecursiveTraversal(this AbcTreeNode x, List<int> list) {
if (x != null) {
AbcRecursiveTraversal(x.a, list);
AbcRecursiveTraversal(x.b, list);
AbcRecursiveTraversal(x.c, list);
list.Add(x.key);//finally visit root
}
}
De iteratieve oplossing:
int? address = null;
AbcTreeNode x = null;
x = root;
address = A;
stack.Push(x);
stack.Push(null)
while (stack.Count > 0) {
bool @return = x == null;
if (@return == false) {
switch (address) {
case A://
stack.Push(x);
stack.Push(B);
x = x.a;
address = A;
break;
case B:
stack.Push(x);
stack.Push(C);
x = x.b;
address = A;
break;
case C:
stack.Push(x);
stack.Push(null);
x = x.c;
address = A;
break;
case null:
list_iterative.Add(x.key);
@return = true;
break;
}
}
if (@return == true) {
address = (int?)stack.Pop();
x = (AbcTreeNode)stack.Pop();
}
}
Antwoord 4, autoriteit 9%
Streef ernaar om uw recursieve aanroep Staartrecursiete doen (recursie waarbij de laatste uitspraak de recursieve aanroep is ). Als je dat eenmaal hebt, is het over het algemeen vrij eenvoudig om het te converteren naar iteratie.
Antwoord 5, autoriteit 6%
Nou, in het algemeen kan recursie worden nagebootst als iteratie door simpelweg een opslagvariabele te gebruiken. Merk op dat recursie en iteratie over het algemeen equivalent zijn; de ene kan bijna altijd worden omgezet in de andere. Een staart-recursieve functie kan heel gemakkelijk worden omgezet in een iteratieve functie. Maak de accumulatorvariabele gewoon een lokale variabele en herhaal in plaats van herhaling. Hier is een voorbeeld in C++ (C ware het niet voor het gebruik van een standaardargument):
// tail-recursive
int factorial (int n, int acc = 1)
{
if (n == 1)
return acc;
else
return factorial(n - 1, acc * n);
}
// iterative
int factorial (int n)
{
int acc = 1;
for (; n > 1; --n)
acc *= n;
return acc;
}
Mij kennende, ik heb waarschijnlijk een fout gemaakt in de code, maar het idee is er.
Antwoord 6, autoriteit 4%
Zelfs het gebruik van stack zal een recursief algoritme niet omzetten in iteratief. Normale recursie is functiegebaseerde recursie en als we stapel gebruiken, wordt het stapelgebaseerde recursie. Maar het is nog steeds recursie.
Voor recursieve algoritmen is ruimtecomplexiteit O(N) en tijdcomplexiteit O(N).
Voor iteratieve algoritmen is ruimtecomplexiteit O(1) en tijdcomplexiteit O(N).
Maar als we stack gebruiken, blijft de complexiteit hetzelfde. Ik denk dat alleen staartrecursie kan worden omgezet in iteratie.
Antwoord 7, autoriteit 4%
De eliminatie van stapels en recursieartikel beschrijft het idee om het stapelframe op heap te externaliseren, maar biedt geen eenvoudige en herhaalbaremanier om te converteren. Hieronder staat er een.
Tijdens het converteren naar iteratieve code moet men zich ervan bewust zijn dat de recursieve aanroep kan plaatsvinden vanuit een willekeurig diep codeblok. Het zijn niet alleen de parameters, maar ook het punt om terug te keren naar de logica die nog moet worden uitgevoerd en de status van variabelen die deelnemen aan volgende voorwaarden, die er toe doen. Hieronder vindt u een zeer eenvoudige manier om met de minste wijzigingen naar iteratieve code te converteren.
Beschouw deze recursieve code:
struct tnode
{
tnode(int n) : data(n), left(0), right(0) {}
tnode *left, *right;
int data;
};
void insertnode_recur(tnode *node, int num)
{
if(node->data <= num)
{
if(node->right == NULL)
node->right = new tnode(num);
else
insertnode(node->right, num);
}
else
{
if(node->left == NULL)
node->left = new tnode(num);
else
insertnode(node->left, num);
}
}
Iteratieve code:
// Identify the stack variables that need to be preserved across stack
// invocations, that is, across iterations and wrap them in an object
struct stackitem
{
stackitem(tnode *t, int n) : node(t), num(n), ra(0) {}
tnode *node; int num;
int ra; //to point of return
};
void insertnode_iter(tnode *node, int num)
{
vector<stackitem> v;
//pushing a stackitem is equivalent to making a recursive call.
v.push_back(stackitem(node, num));
while(v.size())
{
// taking a modifiable reference to the stack item makes prepending
// 'si.' to auto variables in recursive logic suffice
// e.g., instead of num, replace with si.num.
stackitem &si = v.back();
switch(si.ra)
{
// this jump simulates resuming execution after return from recursive
// call
case 1: goto ra1;
case 2: goto ra2;
default: break;
}
if(si.node->data <= si.num)
{
if(si.node->right == NULL)
si.node->right = new tnode(si.num);
else
{
// replace a recursive call with below statements
// (a) save return point,
// (b) push stack item with new stackitem,
// (c) continue statement to make loop pick up and start
// processing new stack item,
// (d) a return point label
// (e) optional semi-colon, if resume point is an end
// of a block.
si.ra=1;
v.push_back(stackitem(si.node->right, si.num));
continue;
ra1: ;
}
}
else
{
if(si.node->left == NULL)
si.node->left = new tnode(si.num);
else
{
si.ra=2;
v.push_back(stackitem(si.node->left, si.num));
continue;
ra2: ;
}
}
v.pop_back();
}
}
Merk op hoe de structuur van de code nog steeds trouw blijft aan de recursieve logica en dat de aanpassingen minimaal zijn, wat resulteert in minder bugs. Ter vergelijking heb ik de wijzigingen gemarkeerd met ++ en –. De meeste van de nieuw ingevoegde blokken, behalve v.push_back, zijn gemeenschappelijk voor elke geconverteerde iteratieve logica
void insertnode_iter(tnode *node, int num)
{
+++++++++++++++++++++++++
vector<stackitem> v;
v.push_back(stackitem(node, num));
while(v.size())
{
stackitem &si = v.back();
switch(si.ra)
{
case 1: goto ra1;
case 2: goto ra2;
default: break;
}
------------------------
if(si.node->data <= si.num)
{
if(si.node->right == NULL)
si.node->right = new tnode(si.num);
else
{
+++++++++++++++++++++++++
si.ra=1;
v.push_back(stackitem(si.node->right, si.num));
continue;
ra1: ;
-------------------------
}
}
else
{
if(si.node->left == NULL)
si.node->left = new tnode(si.num);
else
{
+++++++++++++++++++++++++
si.ra=2;
v.push_back(stackitem(si.node->left, si.num));
continue;
ra2: ;
-------------------------
}
}
+++++++++++++++++++++++++
v.pop_back();
}
-------------------------
}
Antwoord 8, autoriteit 2%
Zoek op Google naar ‘Continuation passing style’. Er is een algemene procedure voor het converteren naar een recursieve staartstijl; er is ook een algemene procedure om recursieve staartfuncties om te zetten in lussen.
Antwoord 9, autoriteit 2%
Gewoon de tijd doden… Een recursieve functie
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
kan worden geconverteerd naar
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
stack.push(node->right);
stack.push(node->left);
while(!stack.empty()) {
node1 = stack.pop();
if(node1 == NULL)
continue;
// Do something with node1...
stack.push(node1->right);
stack.push(node1->left);
}
}
Antwoord 10, autoriteit 2%
Dingen bedenken die eigenlijk een stapel nodig hebben:
Als we het patroon van recursie beschouwen als:
if(task can be done directly) {
return result of doing task directly
} else {
split task into two or more parts
solve for each part (possibly by recursing)
return result constructed by combining these solutions
}
Bijvoorbeeld de klassieke toren van Hanoi
if(the number of discs to move is 1) {
just move it
} else {
move n-1 discs to the spare peg
move the remaining disc to the target peg
move n-1 discs from the spare peg to the target peg, using the current peg as a spare
}
Dit kan worden vertaald in een lus die werkt op een expliciete stapel, door deze opnieuw te formuleren als:
place seed task on stack
while stack is not empty
take a task off the stack
if(task can be done directly) {
Do it
} else {
Split task into two or more parts
Place task to consolidate results on stack
Place each task on stack
}
}
Voor Tower of Hanoi wordt dit:
stack.push(new Task(size, from, to, spare));
while(! stack.isEmpty()) {
task = stack.pop();
if(task.size() = 1) {
just move it
} else {
stack.push(new Task(task.size() -1, task.spare(), task,to(), task,from()));
stack.push(new Task(1, task.from(), task.to(), task.spare()));
stack.push(new Task(task.size() -1, task.from(), task.spare(), task.to()));
}
}
Er is hier een aanzienlijke flexibiliteit met betrekking tot hoe u uw stapel definieert. Je kunt van je stapel een lijst maken met Command-objecten die geavanceerde dingen doen. Of je kunt de andere kant op gaan en er een lijst van eenvoudigere typen van maken (bijvoorbeeld een “taak” kan 4 elementen zijn op een stapel int, in plaats van één element op een stapel van Task).
Dit betekent alleen dat het geheugen voor de stapel zich in de heap bevindt in plaats van in de Java-uitvoeringsstapel, maar dit kan handig zijn omdat u er meer controle over hebt.
Antwoord 11
Over het algemeen wordt de techniek om stapeloverloop te voorkomen voor recursieve functies de trampolinetechniek genoemd, die algemeen wordt toegepast door Java-ontwikkelaars.
Voor C# is er echter een kleine hulpmethode hierdie uw recursieve functie in iteratief verandert zonder de logica te veranderen of de code onbegrijpelijk te maken. C# is zo’n mooie taal dat er geweldige dingen mee mogelijk zijn.
Het werkt door delen van de methode in te pakken met een hulpmethode. Bijvoorbeeld de volgende recursieve functie:
int Sum(int index, int[] array)
{
//This is the termination condition
if (int >= array.Length)
//This is the returning value when termination condition is true
return 0;
//This is the recursive call
var sumofrest = Sum(index+1, array);
//This is the work to do with the current item and the
//result of recursive call
return array[index]+sumofrest;
}
Verandert in:
int Sum(int[] ar)
{
return RecursionHelper<int>.CreateSingular(i => i >= ar.Length, i => 0)
.RecursiveCall((i, rv) => i + 1)
.Do((i, rv) => ar[i] + rv)
.Execute(0);
}
Antwoord 12
Een patroon om naar te zoeken is een recursie-aanroep aan het einde van de functie (zogenaamde staart-recursie). Dit kan gemakkelijk worden vervangen door een tijdje. Bijvoorbeeld de functie foo:
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
eindigt met een oproep aan foo. Dit kan worden vervangen door:
void foo(Node* node)
{
while(node != NULL)
{
// Do something with node...
foo(node->left);
node = node->right;
}
}
wat de tweede recursieve oproep elimineert.
Antwoord 13
Een vraagdie was gesloten als een duplicaat van deze had een zeer specifieke gegevensstructuur:
Het knooppunt had de volgende structuur:
typedef struct {
int32_t type;
int32_t valueint;
double valuedouble;
struct cNODE *next;
struct cNODE *prev;
struct cNODE *child;
} cNODE;
De recursieve verwijderingsfunctie zag er als volgt uit:
void cNODE_Delete(cNODE *c) {
cNODE*next;
while (c) {
next=c->next;
if (c->child) {
cNODE_Delete(c->child)
}
free(c);
c=next;
}
}
Over het algemeen is het niet altijd mogelijk om een stapel te vermijden voor recursieve functies die zichzelf meer dan één keer (of zelfs één keer) aanroepen. Voor deze specifieke structuur is het echter mogelijk. Het idee is om alle knooppunten af te vlakken in een enkele lijst. Dit wordt bereikt door het childvan het huidige knooppunt aan het einde van de lijst van de bovenste rij te plaatsen.
void cNODE_Delete (cNODE *c) {
cNODE *tmp, *last = c;
while (c) {
while (last->next) {
last = last->next; /* find last */
}
if ((tmp = c->child)) {
c->child = NULL; /* append child to last */
last->next = tmp;
tmp->prev = last;
}
tmp = c->next; /* remove current */
free(c);
c = tmp;
}
}
Deze techniek kan worden toegepast op elke data-gekoppelde structuur die kan worden teruggebracht tot een DAG met een deterministische topologische ordening. De huidige knooppunten-kinderen worden herschikt zodat het laatste kind alle andere kinderen overneemt. Vervolgens kan het huidige knooppunt worden verwijderd en kan de traversal vervolgens worden herhaald naar het resterende kind.
Antwoord 14
Recursie is niets anders dan het aanroepen van de ene functie vanuit de andere, alleen dit proces wordt gedaan door een functie zelf aan te roepen. Zoals we weten, wanneer de ene functie de andere functie aanroept, slaat de eerste functie zijn status (zijn variabelen) op en geeft vervolgens de besturing door aan de aangeroepen functie. De aangeroepen functie kan worden aangeroepen door dezelfde naam van variabelen te gebruiken ex fun1(a) kan fun2(a) aanroepen.
Wanneer we recursieve aanroep doen, gebeurt er niets nieuws. Eén functie roept zichzelf aan door hetzelfde type en soortgelijke naamvariabelen door te geven (maar uiteraard zijn de waarden die in variabelen zijn opgeslagen anders, alleen de naam blijft hetzelfde.) Maar vóór elke aanroep slaat de functie zijn status op en dit proces van opslaan gaat door. Het OPSLAAN WORDT GEDAAN OP EEN STAPEL.
NU KOMT DE STAP IN HET SPEL.
Dus als je een iteratief programma schrijft en de status elke keer op een stapel opslaat en vervolgens de waarden uit de stapel haalt wanneer dat nodig is, heb je een recursief programma met succes omgezet in een iteratief programma!
Het bewijs is eenvoudig en analytisch.
In recursie onderhoudt de computer een stapel en in de iteratieve versie moet u de stapel handmatig onderhouden.
Denk erover na, converteer gewoon een recursief programma voor diepteonderzoek (op grafieken) naar een iteratief dfs-programma.
Het allerbeste!
Antwoord 15
TLDR
U kunt de onderstaande broncode vergelijken, voordat en na om intuïtief de aanpak te begrijpen zonder dit hele antwoord te lezen.
Ik liep problemen met een aantal multi-key QuickSort-code die ik gebruikte om zeer grote tekstblokken te verwerken om achtervoegselarrays te produceren. De code zou afbreken vanwege de extreme die diepte van recursie vereist is. Met deze aanpak werden de beëindigingsproblemen opgelost. Na de conversie kan het maximale aantal frames dat nodig is voor sommige banen worden vastgelegd, die tussen 10k en 100k was, van 1M tot 6M geheugen. Geen optimale oplossing, er zijn effectievere manieren om Suffix-arrays te produceren. Maar hoe dan ook, hier is de gebruikte aanpak.
de aanpak
Een algemene manier om een recursieve functie om te zetten naar een iteratieve oplossing die op elk geval van toepassing is, is het proces van natureel gecompileerde code gebruikt tijdens een functie-oproep en de terugkeer van de oproep.
Een voorbeeld nemen dat een enigszins betrokken benadering vereist, hebben we het multi-key QuickSort-algoritme. Deze functie heeft drie opeenvolgende recursieve oproepen, en na elke oproep begint de uitvoering bij de volgende regel.
De status van de functie wordt vastgelegd in het stapelframe, dat op de execution-stapel wordt geduwd. Wanneer sort()wordt opgeroepen vanuit zichzelf en retourneert, wordt het stapelframe dat aanwezig is op het moment van de oproep hersteld. Op die manier hebben alle variabelen dezelfde waarden als vóór de oproep – tenzij ze door de oproep zijn gewijzigd.
recursieve functie
def sort(a: list_view, d: int):
if len(a) <= 1:
return
p = pivot(a, d)
i, j = partition(a, d, p)
sort(a[0:i], d)
sort(a[i:j], d + 1)
sort(a[j:len(a)], d)
Dit model nemen en het naemmeren, wordt een lijst ingesteld om op te treden als de stapel. In dit voorbeeld worden de tuples gebruikt om frames na te bootsen. Als dit in C is gecodeerd, kunnen eringen worden gebruikt. De gegevens kunnen worden opgenomen in een gegevensstructuur in plaats van gewoon één waarde tegelijk te duwen.
Reïplementeerd als “iteratief”
# Assume `a` is view-like object where slices reference
# the same internal list of strings.
def sort(a: list_view):
stack = []
stack.append((LEFT, a, 0)) # Initial frame.
while len(stack) > 0:
frame = stack.pop()
if len(frame[1]) <= 1: # Guard.
continue
stage = frame[0] # Where to jump to.
if stage == LEFT:
_, a, d = frame # a - array/list, d - depth.
p = pivot(a, d)
i, j = partition(a, d, p)
stack.append((MID, a, i, j, d)) # Where to go after "return".
stack.append((LEFT, a[0:i], d)) # Simulate function call.
elif stage == MID: # Picking up here after "call"
_, a, i, j, d = frame # State before "call" restored.
stack.append((RIGHT, a, i, j, d)) # Set up for next "return".
stack.append((LEFT, a[i:j], d + 1)) # Split list and "recurse".
elif stage == RIGHT:
_, a, _, j, d = frame
stack.append((LEFT, a[j:len(a)], d)
else:
pass
Wanneer een functie-oproep wordt gedaan, wordt informatie over de uitvoering van de uitvoering opgenomen nadat de functie Returns is opgenomen in het stapelframe. In dit voorbeeld, if/elif/elseBLOCKS vertegenwoordigen de punten waar de uitvoering na terugkomst van een oproep begint. In C kan dit worden geïmplementeerd als een switchverklaring.
In het voorbeeld worden de blokken aangegeven labels; Ze zijn willekeurig gelabeld door hoe de lijst wordt gepartitioneerd in elk blok. Het eerste blok, “links” splitst de lijst aan de linkerkant. De sectie “MID” vertegenwoordigt het blok dat de lijst in het midden, enz. Splanteert.
Bij deze aanpak zijn er twee stappen nodig om een oproep na te bootsen. Eerst wordt een frame op de stapel geduwd waardoor de uitvoering wordt hervat in het blok dat volgt op het huidige blok nadat de “call” “returns” is. Een waarde in het frame geeft aan in welke sectie if/elif/elseje moet vallen in de lus die volgt op de “call”.
Vervolgens wordt het “call”-frame op de stapel geschoven. Dit stuurt de uitvoering naar het eerste, “LEFT”, blok in de meeste gevallen voor dit specifieke voorbeeld. Dit is waar de eigenlijke sortering wordt gedaan, ongeacht welk gedeelte van de lijst is opgesplitst om daar te komen.
Voordat de lus begint, vertegenwoordigt het primaire frame dat bovenaan de functie wordt gedrukt, de eerste aanroep. Vervolgens wordt bij elke iteratie een frame geopend. De “LEFT/MID/RIGHT” waarde/label van het frame wordt gebruikt om in het juiste blok van de if/elif/else-instructie te vallen. Het frame wordt gebruikt om de status van de variabelen die nodig zijn voor de huidige bewerking te herstellen, en bij de volgende iteratie wordt het retourframe geopend, waardoor de uitvoering naar de volgende sectie wordt verzonden.
Retourwaarden
Als de recursieve functie een waarde retourneert die op zichzelf wordt gebruikt, kan deze op dezelfde manier worden behandeld als andere variabelen. Maak er gewoon een veld voor in het stapelframe. Als een “callee” een waarde retourneert, controleert hij de stapel om te zien of deze iets bevat; en als dat het geval is, wordt de geretourneerde waarde in het frame bovenaan de stapel bijgewerkt. Voor een voorbeeld van deze kunt u dit andere voorbeeldvan dezelfde benadering van recursieve naar iteratieve conversie bekijken.
Conclusie
Methoden zoals deze die recursieve functies omzetten in iteratieve functies, zijn in wezen ook “recursief”. In plaats van dat de processtack wordt gebruikt voor daadwerkelijke functieaanroepen, komt er een andere programmatisch geïmplementeerde stack voor in de plaats.
Wat wordt er gewonnen? Misschien enkele marginale verbeteringen in snelheid. Of het kan dienen als een manier om stackbeperkingen te omzeilen die worden opgelegd door sommige compilers en/of uitvoeringsomgevingen (stackaanwijzer raakt de bewakingspagina). In sommige gevallen kan de hoeveelheid gegevens die op de stapel wordt geduwd, worden verminderd. Compenseren de voordelen de complexiteit die in de code is geïntroduceerd door iets na te bootsen dat we automatisch krijgen met de recursieve implementatie?
In het geval van het sorteeralgoritme kan het een uitdaging zijn om een manier te vinden om dit specifieke zonder stapel te implementeren, en er zijn zoveel iteratieve sorteeralgoritmen beschikbaar die veel sneller zijn. Er wordt gezegd dat elk recursief algoritme iteratief kan worden geïmplementeerd. Natuurlijk… maar sommige algoritmen converteren niet goed zonder zodanig te worden aangepast dat ze niet langer hetzelfde algoritme zijn.
Het is misschien niet zo’n goed idee om recursieve algoritmen te converteren alleen om ze te converteren. Hoe dan ook, voor wat het waard is, de bovenstaande benadering is een generieke manier van converteren die voor zo ongeveer alles zou moeten gelden.
Als je merkt dat je echt een iteratieve versie van een recursieve functie nodig hebt die geen eigen geheugen-vretende stapel gebruikt, kan de beste aanpak zijn om de code te schrappen en je eigen code te schrijven met behulp van de beschrijving van een wetenschappelijk artikel, of werk het op papier uit en codeer het dan helemaal opnieuw, of een andere grondige aanpak.
Antwoord 16
Er is een algemene manier om recursieve traversal om te zetten in iterator door een luie iterator te gebruiken die meerdere iteratorleveranciers samenvoegt (lambda-expressie die een iterator retourneert). Zie mijn Recursieve traversal converteren naar iterator.
Antwoord 17
Nog een eenvoudig en compleet voorbeeld van het omzetten van de recursieve functie in een iteratieve functie met behulp van de stapel.
#include <iostream>
#include <stack>
using namespace std;
int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }
struct Par
{
int a, b;
Par() : Par(0, 0) {}
Par(int _a, int _b) : a(_a), b(_b) {}
};
int GCDIter(int a, int b)
{
stack<Par> rcstack;
if (b == 0)
return a;
rcstack.push(Par(b, a % b));
Par p;
while (!rcstack.empty())
{
p = rcstack.top();
rcstack.pop();
if (p.b == 0)
continue;
rcstack.push(Par(p.b, p.a % p.b));
}
return p.a;
}
int main()
{
//cout << GCD(24, 36) << endl;
cout << GCDIter(81, 36) << endl;
cin.get();
return 0;
}
Antwoord 18
Mijn voorbeelden zijn in Clojure, maar zouden vrij eenvoudig te vertalen zijn naar elke taal.
Gezien deze functie die StackOverflows voor grote waarden van n:
(defn factorial [n]
(if (< n 2)
1
(*' n (factorial (dec n)))))
we kunnen op de volgende manier een versie definiëren die zijn eigen stapel gebruikt:
(defn factorial [n]
(loop [n n
stack []]
(if (< n 2)
(return 1 stack)
;; else loop with new values
(recur (dec n)
;; push function onto stack
(cons (fn [n-1!]
(*' n n-1!))
stack)))))
waar returnis gedefinieerd als:
(defn return
[v stack]
(reduce (fn [acc f]
(f acc))
v
stack))
Dit werkt ook voor complexere functies, bijvoorbeeld de ackermann-functie:
(defn ackermann [m n]
(cond
(zero? m)
(inc n)
(zero? n)
(recur (dec m) 1)
:else
(recur (dec m)
(ackermann m (dec n)))))
kan worden omgezet in:
(defn ackermann [m n]
(loop [m m
n n
stack []]
(cond
(zero? m)
(return (inc n) stack)
(zero? n)
(recur (dec m) 1 stack)
:else
(recur m
(dec n)
(cons #(ackermann (dec m) %)
stack)))))
Antwoord 19
Een ruwe beschrijving van hoe een systeem een recursieve functie neemt en deze uitvoert met behulp van een stapel:
Dit was bedoeld om het idee zonder details te laten zien. Overweeg deze functie die knooppunten van een grafiek zou afdrukken:
function show(node)
0. if isleaf(node):
1. print node.name
2. else:
3. show(node.left)
4. show(node)
5. show(node.right)
Bijvoorbeeld grafiek:
A->B
A->C
show(A) zou B, A, C afdrukken
Functie-aanroepen houden in: sla de lokale staat en het vervolgpunt op zodat u terug kunt komen en spring dan naar de functie die u wilt aanroepen.
Stel bijvoorbeeld dat show(A) begint te lopen. De functieaanroep op regel 3. show(B) betekent:
– Voeg item toe aan de stapel, wat betekent “je moet doorgaan op regel 2 met lokale variabele status node=A”
– Ga naar regel 0 met node=B.
Om code uit te voeren, doorloopt het systeem de instructies. Wanneer een functieaanroep wordt aangetroffen, pusht het systeem informatie die het nodig heeft om terug te komen naar waar het was, voert het de functiecode uit en wanneer de functie is voltooid, verschijnt de informatie over waar het naartoe moet om verder te gaan.
Antwoord 20
Deze linkgeeft enige uitleg en stelt het idee voor om “locatie” te behouden om de exacte plaats tussen verschillende recursieve oproepen te kunnen bereiken:
Al deze voorbeelden beschrijven echter scenario’s waarin een recursieve aanroep een vastaantal keren wordt gedaan. Dingen worden lastiger als je iets hebt als:
function rec(...) {
for/while loop {
var x = rec(...)
// make a side effect involving return value x
}
}
Antwoord 21
Dit is een oude vraag, maar ik wil een ander aspect toevoegen als een oplossing. Ik ben momenteel bezig met een project waarin ik het algoritme van de overstroming vult met C #. Normaal gesproken heb ik dit algoritme met recursie in eerste instantie geïmplementeerd, maar duidelijk, veroorzaakte het een stapel overloop. Daarna veranderde ik de methode van recursie tot iteratie. Ja, het werkte en ik kreeg de stapeloverloopfout niet meer. Maar deze keer, aangezien ik de overstromingsvulling methode toegepast op zeer grote structuren, ging het programma in een oneindige lus. Om deze reden kwam het bij mij op dat de functie misschien opnieuw de plaatsen heeft ingevoerd die het al had bezocht. Als een definitieve oplossing hiervoor besloot ik een woordenboek te gebruiken voor bezochte punten. Als dat knooppunt (X, Y) voor de eerste keer al aan de stapelstructuur is toegevoegd, wordt dat knooppunt (X, Y) in het woordenboek opgeslagen als de sleutel. Zelfs als hetzelfde knooppunt later opnieuw wordt toegevoegd, wordt het niet toegevoegd aan de stapelstructuur omdat het knooppunt al in het woordenboek staat. Laten we eens kijken op pseudo-code:
startNode = pos(x,y)
Stack stack = new Stack();
Dictionary visited<pos, bool> = new Dictionary();
stack.Push(startNode);
while(stack.count != 0){
currentNode = stack.Pop();
if "check currentNode if not available"
continue;
if "check if already handled"
continue;
else if "run if it must be wanted thing should be handled"
// make something with pos currentNode.X and currentNode.X
// then add its neighbor nodes to the stack to iterate
// but at first check if it has already been visited.
if(!visited.Contains(pos(x-1,y)))
visited[pos(x-1,y)] = true;
stack.Push(pos(x-1,y));
if(!visited.Contains(pos(x+1,y)))
...
if(!visited.Contains(pos(x,y+1)))
...
if(!visited.Contains(pos(x,y-1)))
...
}