Nøgleforskel – rekursion vs iteration
Rekursion og iteration kan bruges til at løse programmeringsproblemer. Tilgangen til at løse problemet ved hjælp af rekursion eller iteration afhænger af måden at løse problemet på. Den vigtigste forskel 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 betingelse er sand. Rekursion og iteration er vigtige teknikker til at udvikle algoritmer og bygge softwareapplikationer.
Hvad er rekursion?
Når en funktion kalder sig selv i funktionen, er den kendt som rekursion. Der er to typer af rekursion. De er endelig rekursion og uendelig rekursion. Finit rekursion har en afsluttende betingelse. Uendelig rekursion har ikke en afsluttende betingelse.
Rekursion kan forklares ved hjælp af programmet til at beregne factorials.
n!=n(n-1)!, hvis n>0
n!=1, hvis n=0;
Se nedenstående kode for at beregne factorial af 3(3!=321).
intmain () {
int værdi=faktoriel (3);
printf(“Faktorial er %d\n”, værdi);
retur 0;
}
intfatorial (intn) {
if(n==0) {
retur 1;
}
else {
return n factorial(n-1);
}
}
Når du kalder faktorial (3), kalder denne funktion faktorial (2). Når du kalder factorial (2), vil denne funktion kalde factorial (1). Så vil factorial (1) kalde factorial (0). factorial (0) vil returnere 1. I ovenstående program er n==0 betingelse i "hvis blokken" grundbetingelsen. Ifølge Ligeledes kaldes den faktorielle funktion 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 kaldede funktion. Når funktionen kaldes, gives styringen til den kaldte funktion. Efter at funktionsudførelsen er afsluttet, returneres styringen til main. Så fortsætter hovedprogrammet. Så den opretter en aktiveringspost eller en stakramme for at fortsætte eksekveringen.
Figur 01: Rekursion
I ovennævnte program, når du kalder faktorial (3) fra main, opretter det en aktiveringspost i opkaldsstakken. Derefter oprettes en faktoriel (2) stakramme oven på stakken og så videre. Aktiveringsposten gemmer information om lokale variabler osv. Hver gang funktionen kaldes, oprettes et nyt sæt lokale variabler øverst i stakken. Disse stak-rammer kan sænke hastigheden. Ligeledes i rekursion kalder en funktion sig selv. Tidskompleksitet for en rekursiv funktion findes ved det antal gange, funktionen kaldes. Tidskompleksiteten for et funktionskald er O(1). For n antal rekursive opkald er tidskompleksiteten O(n).
Hvad er iteration?
Iteration er en blok af instruktioner, som gentages igen og igen, indtil den givne betingelse er sand. Iteration kan opnås ved at bruge "for loop", "do-while loop" eller "while loop". "for loop"-syntaksen er som følger.
for (initialisering; betingelse; modificere) {
//-udsagn;
}
Figur 02: "for loop-flowdiagram"
Initialiseringstrin udføres først. Dette trin er at erklære og initialisere sløjfekontrolvariabler. Hvis betingelsen er sand, udføres udsagn inde i de krøllede parenteser. 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 sætningerne inde i løkken, går kontrollen til ændringssektionen. Det er for at opdatere sløjfekontrolvariablen. Derefter kontrolleres tilstanden igen. Hvis betingelsen er sand, vil udsagn inde i de krøllede bøjler udføres. På denne måde gentager "for-løkken".
I "while loop" udføres sætningerne inde i loopet, indtil betingelsen er sand.
while (tilstand){
//udsagn
}
I "do-while"-løkke kontrolleres tilstanden i slutningen af løkken. Så løkken udføres mindst én gang.
do{
//udsagn
} mens(tilstand)
Programmer for at finde faktoren på 3 (3!) ved hjælp af iteration ("for loop") er som følger.
int main(){
intn=3, factorial=1;
inti;
for(i=1; i<=n; i++){
factorial=faktorieli;
}
printf(“Faktorial er %d\n”, faktoriel);
retur 0;
}
Hvad er lighederne mellem rekursion og iteration?
- Begge er teknikker til at løse et problem.
- Opgaven kan løses enten i rekursion eller iteration.
Hvad er forskellen mellem rekursion og iteration?
Rekursion vs Iteration |
|
| Rekursion er en metode til at kalde en funktion inden for den samme funktion. | Iteration er en blok af instruktioner, der gentages, indtil den givne betingelse er sand. |
| Rumkompleksitet | |
| Rumkompleksiteten af rekursive programmer er højere end iterationer. | Rumkompleksiteten er lavere i iterationer. |
| Speed | |
| Rekursionsudførelse er langsom. | Norm alt er iteration hurtigere end rekursion. |
| Condition | |
| Hvis der ikke er nogen opsigelsesbetingelse, kan der være en uendelig rekursion. | Hvis betingelsen 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. |
Opsummering – 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 den for at udføre et sæt instruktioner gentagne gange, indtil den givne betingelse 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-versionen af denne artikel og bruge den til offline-formål i henhold til citatnotat. Download venligst PDF-version her Forskel mellem rekursion og iteration
