Nøgleforskel - Rekursion vs Iteration
Rekursion og gentagelse kan bruges til at løse programmeringsproblemer. Fremgangsmåden til løsning af problemet ved hjælp af rekursion eller iteration afhænger af måden at løse problemet på. Hovedforskellen mellem rekursion og iteration er, at rekursion er en mekanisme til at kalde en funktion inden for den samme funktion, mens iteration er at udføre et sæt instruktioner gentagne gange, indtil den givne tilstand er sand. Rekursion og gentagelse er vigtige teknikker til udvikling af algoritmer og opbygning af softwareapplikationer.
INDHOLD
1. Oversigt og nøgleforskel
2. Hvad er rekursion
3. Hvad er gentagelse
4. Ligheder mellem rekursion og gentagelse
5. Sammenligning ved siden af hinanden - Rekursion mod ikteration i tabelform
6. Resumé
Hvad er rekursion?
Når en funktion kalder sig inden for funktionen, kaldes den rekursion. Der er to typer rekursion. De er endelig rekursion og uendelig rekursion. Endelig rekursion har en afsluttende tilstand. Uendelig rekursion har ikke en afsluttende tilstand.
Rekursion kan forklares ved hjælp af programmet til beregning af fakta.
n! = n * (n-1) !, hvis n> 0
n! = 1, hvis n = 0;
Henvis til nedenstående kode for at beregne faktoren på 3 (3! = 3 * 2 * 1).
intmain () {
int værdi = faktor (3);
printf ("Faktor er% d / n", værdi);
returnere 0;
}
intaktorisk (intn) {
hvis (n == 0) {
returnere 1;
}
andet {
returnere n * faktor (n-1);
}
}
Når man kalder factorial (3), vil denne funktion kalde factorial (2). Når der kaldes factorial (2), vil denne funktion kalde factorial (1). Derefter kalder factorial (1) factorial (0). factorial (0) returnerer 1. I ovenstående program er n == 0 betingelse i "hvis blokken" basistilstanden. Ifølge det samme kaldes faktorfunktionen igen og igen.
Rekursive funktioner er relateret til stakken. I C kan hovedprogrammet have mange funktioner. Så main () er den kaldende funktion, og den funktion, der kaldes af hovedprogrammet, er den kaldte funktion. Når funktionen kaldes, gives kontrol til den kaldte funktion. Når funktionens udførelse er afsluttet, returneres kontrollen til hoved. Derefter fortsætter hovedprogrammet. Så det opretter en aktiveringspost eller en stakramme for at fortsætte udførelsen.
Figur 01: Rekursion
I det ovennævnte program opretter det en aktiveringspost i opkaldsstakken, når der kaldes factorial (3) fra main. Derefter oprettes faktor (2) stabelramme oven på stakken og så videre. Aktiveringsjournalen gemmer information om lokale variabler osv. Hver gang funktionen kaldes, oprettes der et nyt sæt lokale variabler øverst på stakken. Disse stakrammer kan sænke hastigheden op. Ligeledes i rekursion kalder en funktion sig selv. Tidskompleksitet for en rekursiv funktion findes ved antallet af gange, funktionen kaldes. Tidskompleksitet for et funktionsopkald er O (1). For n antal rekursive opkald er tidskompleksiteten O (n).
Hvad er gentagelse?
Iteration er en blok af instruktioner, der gentages igen og igen, indtil den givne tilstand er sand. Iteration kan opnås ved hjælp af "for loop", "do-while loop" eller "while loop". "For loop" syntaks er som følger.
til (initialisering; betingelse; ændre) {
// udsagn;
}
Figur 02: "for loop-flowdiagram"
Initialiseringstrinnet udføres først. Dette trin er at deklarere og initialisere loopkontrolvariabler. Hvis betingelsen er sand, udføres udsagnene i de krøllede seler. Disse udsagn udføres, indtil betingelsen er sand. Hvis betingelsen er falsk, går kontrollen til den næste sætning efter "for loop". Efter at have udført udsagnene inde i sløjfen, går kontrollen til at ændre sektionen. Det er at opdatere loop-kontrolvariablen. Derefter kontrolleres tilstanden igen. Hvis betingelsen er sand, vil udsagnene i de krøllede seler udføres. På denne måde gentages "for loop".
I "while loop" udføres udsagnene inde i loop, indtil betingelsen er sand.
mens (betingelse) {
// udsagn
}
I "do-while" -sløjfe kontrolleres tilstanden i slutningen af sløjfen. Så sløjfen udføres mindst én gang.
gøre {
// udsagn
} mens (tilstand)
Programmet til at finde en faktor 3 (3!) Ved hjælp af iteration (“for loop”) er som følger.
int main () {
intn = 3, faktor = 1;
inti;
for (i = 1; i <= n; i ++) {
factorial = factorial * i;
}
printf ("Faktor er% d / n", faktor)
returnere 0;
}
Hvad er ligheden mellem rekursion og gentagelse?
- Begge er teknikker til at løse et problem.
- Opgaven kan løses enten i rekursion eller iteration.
Hvad er forskellen mellem rekursion og gentagelse?
Diff artikel midt foran bordet
Rekursion vs Iteration |
|
| Rekursion er en metode til at kalde en funktion inden for den samme funktion. | Iteration er en blok instruktioner, der gentages, indtil den givne betingelse er sand. |
| Rumkompleksitet | |
| Rumkompleksiteten af rekursive programmer er højere end iterationer. | Rumkompleksitet er lavere i iterationer. |
| Hastighed | |
| Rekursionsudførelse er langsom. | Normalt er iteration hurtigere end rekursion. |
| Tilstand | |
| Hvis der ikke er nogen opsigelsesbetingelser, kan der være en uendelig rekursion. | Hvis tilstanden aldrig bliver falsk, vil det være en uendelig iteration. |
| Stak | |
| I rekursion bruges stakken til at gemme lokale variabler, når funktionen kaldes. | I en iteration bruges stakken ikke. |
| Kodelæsbarhed | |
| Et rekursivt program er mere læsbart. | Det iterative program er sværere at læse end et rekursivt program. |
Resumé - Rekursion vs Iteration
Denne artikel diskuterede forskellen mellem rekursion og iteration. Begge kan bruges til at løse programmeringsproblemer. Forskellen mellem rekursion og iteration er, at rekursion er en mekanisme til at kalde en funktion inden for den samme funktion, og iteration til at udføre et sæt instruktioner gentagne gange, indtil den givne tilstand er sand. Hvis et problem kan løses i rekursiv form, kan det også løses ved hjælp af iterationer.
Download PDF-versionen af Recursion vs Iteration
Du kan downloade PDF-version af denne artikel og bruge den til offlineformål som pr. Citatnote. Download venligst PDF-version her Forskellen mellem rekursion og gentagelse
