Nøkkelforskjell – rekursjon vs iterasjon
Rekursjon og iterasjon kan brukes til å løse programmeringsproblemer. Tilnærmingen til å løse problemet ved hjelp av rekursjon eller iterasjon avhenger av måten å løse problemet på. Nøkkelforskjellen mellom rekursjon og iterasjon er at rekursjon er en mekanisme for å kalle en funksjon innenfor samme funksjon mens iterasjon er å utføre et sett med instruksjoner gjentatte ganger til den gitte betingelsen er sann. Rekursjon og iterasjon er viktige teknikker for å utvikle algoritmer og bygge programvareapplikasjoner.
Hva er rekursjon?
Når en funksjon kaller seg selv innenfor funksjonen, er den kjent som rekursjon. Det er to typer rekursjon. De er endelig rekursjon og uendelig rekursjon. Finitt rekursjon har en avsluttende tilstand. Uendelig rekursjon har ikke en avsluttende betingelse.
Rekursjon kan forklares ved hjelp av programmet for å beregne faktorialer.
n!=n(n-1)!, hvis n>0
n!=1, hvis n=0;
Se koden nedenfor for å beregne faktoren 3(3!=321).
intmain () {
int verdi=faktoriell (3);
printf(“Faktorial er %d\n”, verdi);
retur 0;
}
intfatorial (intn) {
if(n==0) {
retur 1;
}
else {
return n factorial(n-1);
}
}
Når du kaller faktoriell (3), vil den funksjonen kalle faktoriell (2). Når du kaller faktoriell (2), vil denne funksjonen kalle faktoriell (1). Da vil factorial (1) kalle factorial (0). faktoriell (0) vil returnere 1. I programmet ovenfor er n==0-betingelsen i "hvis-blokken" grunnbetingelsen. I følge Likewise kalles den faktorielle funksjonen opp igjen og igjen.
Rekursive funksjoner er relatert til stabelen. I C kan hovedprogrammet ha mange funksjoner. Så, main () er den kallende funksjonen, og funksjonen som kalles av hovedprogrammet er den k alte funksjonen. Når funksjonen kalles, gis kontrollen til den k alte funksjonen. Etter at funksjonsutførelsen er fullført, går kontrollen tilbake til hoved. Så fortsetter hovedprogrammet. Så den oppretter en aktiveringspost eller en stabelramme for å fortsette utføringen.
Figur 01: Rekursjon
I programmet ovenfor, når du ringer faktoriell (3) fra hoved, oppretter det en aktiveringspost i anropsstakken. Deretter opprettes en faktoriell (2) stabelramme på toppen av stabelen og så videre. Aktiveringsposten holder informasjon om lokale variabler osv. Hver gang funksjonen kalles opp, opprettes et nytt sett med lokale variabler på toppen av stabelen. Disse stabelrammene kan redusere hastigheten. På samme måte i rekursjon kaller en funksjon seg selv. Tidskompleksitet for en rekursiv funksjon er funnet ved antall ganger funksjonen kalles. Tidskompleksiteten for ett funksjonskall er O(1). For n antall rekursive anrop er tidskompleksiteten O(n).
Hva er iterasjon?
Iterasjon er en blokk med instruksjoner som gjentas igjen og igjen til den gitte betingelsen er sann. Iterasjon kan oppnås ved å bruke "for loop", "do-while loop" eller "while loop". "for loop"-syntaksen er som følger.
for (initialisering; betingelse; endre) {
//-utsagn;
}
Figur 02: "for sløyfeflytdiagram"
Initialiseringstrinnet utføres først. Dette trinnet er å deklarere og initialisere sløyfekontrollvariabler. Hvis betingelsen er sann, utføres utsagnene i de krøllete klammeparentesene. Disse utsagnene utføres til betingelsen er sann. Hvis betingelsen er usann, går kontrollen til neste setning etter "for loop". Etter å ha utført setningene inne i loopen, går kontrollen til modifisereseksjonen. Det er for å oppdatere sløyfekontrollvariabelen. Deretter sjekkes tilstanden på nytt. Hvis betingelsen er sann, vil utsagnene i de krøllete klammeparentesene utføres. På denne måten gjentar "for loop".
I «while loop» kjøres setningene inne i loopen til betingelsen er sann.
while (tilstand){
//statements
}
I «do-while»-løkke kontrolleres tilstanden på slutten av løkken. Så loopen kjøres minst én gang.
do{
//statements
} mens(tilstand)
Programmer for å finne faktoren til 3 (3!) ved å bruke iterasjon ("for loop") er som følger.
int main(){
intn=3, factorial=1;
inti;
for(i=1; i<=n; i++){
faktoriell=faktorielli;
}
printf(“Faktorial er %d\n”, faktoriell);
retur 0;
}
Hva er likhetene mellom rekursjon og iterasjon?
- Begge er teknikker for å løse et problem.
- Oppgaven kan løses enten i rekursjon eller iterasjon.
Hva er forskjellen mellom rekursjon og iterasjon?
Rekursjon vs iterasjon |
|
| Rekursjon er en metode for å kalle en funksjon innenfor samme funksjon. | Iterasjon er en blokk med instruksjoner som gjentas til den gitte betingelsen er sann. |
| Space Complexity | |
| Romkompleksiteten til rekursive programmer er høyere enn iterasjoner. | Romkompleksiteten er lavere i iterasjoner. |
| Speed | |
| Rekursjonsutførelsen er treg. | Norm alt er iterasjon raskere enn rekursjon. |
| Condition | |
| Hvis det ikke er noen oppsigelsesbetingelse, kan det være en uendelig rekursjon. | Hvis betingelsen aldri blir falsk, vil det være en uendelig iterasjon. |
| Stack | |
| I rekursjon brukes stabelen til å lagre lokale variabler når funksjonen kalles. | I en iterasjon blir ikke stabelen brukt. |
| Kodelesbarhet | |
| Et rekursivt program er mer lesbart. | Det iterative programmet er vanskeligere å lese enn et rekursivt program. |
Sammendrag – rekursjon vs iterasjon
Denne artikkelen diskuterte forskjellen mellom rekursjon og iterasjon. Begge kan brukes til å løse programmeringsproblemer. Forskjellen mellom rekursjon og iterasjon er at rekursjon er en mekanisme for å kalle en funksjon innenfor samme funksjon og iterasjon for å utføre et sett med instruksjoner gjentatte ganger til den gitte betingelsen er sann. Hvis et problem kan løses i rekursiv form, kan det også løses ved hjelp av iterasjoner.
Last ned PDF-versjonen av Recursion vs Iteration
Du kan laste ned PDF-versjonen av denne artikkelen og bruke den til offline-formål i henhold til sitat. Last ned PDF-versjon her Forskjellen mellom rekursjon og iterasjon
