Slik konverterer Recursive til Iterativ

Rekursive algoritmer er de algoritmer som kan kalle seg som en del av løsningen. Disse funksjonene ofte arbeide med problemer som inneholder en serie av identiske under problemer, som tre traversering eller fakultet beregning. Gjentatte ganger å kalle samme funksjon igjen og igjen kan gjøre arbeidet sakte, selv om det kan gjøre koding enklere. For å øke gjennomføring hastighet, kan du gjenskape rekursive algoritmer, som fakultetet algoritmen, inn i en litt mer komplisert iterativ algoritme bruker løkker som utføres mye raskere.

Bruksanvisning

1 Analyser rekursiv algoritme. I dette eksemplet vil du bruke den rekursive løsningen for fakultetet problem:

int fakultet (int faktisk) {

if (faktisk == 0) {
returnere en;
}ellers{
returnere faktum * fakultet (faktisk - 1);
}
}

2 Bestem om eventuelle funksjonsargumenter kan holdes i variabler. I faktoriell eksempel kan resultatene av faktoriell bli lagret i en variabel "total_factorial" for varigheten av enhver iterasjon. Dette eksemplet viser rekursiv fakultetet algoritme og variabelen som skal brukes for rekursive argument:

int total_factorial = 0:

3 Bestem en løkke struktur. I C ++, for eksempel, arbeider ", mens" loop godt med iterasjoner som har en indeterminant lengde. "For" løkker, på den annen side fungere godt når en løkke vil gå til en streng varighet, representert ved et helt tall av noe slag. For fakultetet eksempel en "for" loop vil fungere godt:

int faktoriell = 5;
int total_factorial = 0;

4 Bestem stanse forhold. Vanligvis, som i den faktorielle eksempel vil rekursjon opphøre når en betingelse er oppfylt. I en interative loop, slik som for loop, hjelper det å vite før hånd. Siden du vet at å finne fakultet til et tall "n" at du vil reagere n-1 ganger (unntatt null), kan du begynne på en og kjøre til fakultet nummer:

for (int i = 1; i <= fakultetet; i ++) {
if (i == 1) {
total_factorial = 1;
} Else {
total faktoriell * = i;
}
}