Forskellen mellem rekursion og itteration

Nøgleforskel - rekursion vs Iteration
 

Rekursion og Iteration kan bruges til at løse programmeringsproblemer. Fremgangsmåden til løsning af problemet ved hjælp af rekursion eller iteration afhænger af, hvordan man løser problemet. Det vigtigste forskel mellem rekursion og iteration er det 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 Iteration er vigtige teknikker til udvikling af algoritmer og bygning af softwareapplikationer.

INDHOLD

1. Oversigt og nøgleforskel
2. Hvad er rekursion
3. Hvad er itteration
4. Ligheder mellem rekursion og itteration
5. Sammenligning side ved side - Rekursion vs gentagelse i tabelform
6. Resume

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 afslutningsbetingelse. Uendelig rekursion har ikke en afslutningsbetingelse.

Rekursion kan forklares ved hjælp af programmet til beregning af faktabøger.

n! = n * (n-1) !, hvis n> 0

n! = 1, hvis n = 0;

Henvis til bællekoden for at beregne faktorial på 3 (3! = 3 * 2 * 1).

intmain ()

int-værdi = factorial (3);

printf ("Factorial er% d \ n", værdi);

retur 0;

intfactorial (intn)

hvis (n == 0)

retur 1;

ellers

retur n * factorial (n-1);

Når der kaldes factorial (3), kaldes denne funktion factorial (2). Når der kaldes factorial (2), kaldes denne funktion factorial (1). Så kalder factorial (1) factorial (0). factorial (0) vender tilbage 1. I ovenstående program er n == 0 betingelse i “if block” som basisbetingelse. I henhold til Ligeledes kaldes den faktiske funktion igen og igen.

Rekursive funktioner hænger sammen med 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 styringen til den kaldte funktion. Når funktionsudførelsen er afsluttet, returneres kontrollen til main. Derefter fortsætter hovedprogrammet. Så det opretter en aktiveringsrekord eller en stakramme for at fortsætte udførelsen.

Figur 01: Rekursion

I ovenstående program opretter det en aktiveringsrekord i opkaldsstakken, når man ringer til factorial (3) fra main. Derefter oprettes factorial (2) stabelramme oven på stakken og så videre. Aktiveringsregistret opbevarer oplysninger om lokale variabler osv. Hver gang funktionen kaldes oprettes et nyt sæt lokale variabler øverst i stakken. Disse stakrammer kan bremse hastigheden op. Ligeledes i rekursion kalder en funktion sig selv. Tidskompleksitet for en rekursiv funktion findes ved det antal gange, der kaldes funktionen. Tidskompleksitet for et funktionsopkald er O (1). For et antal rekursive opkald er tidskompleksiteten O (n).

Hvad er Iteration?

Iteration er en blok instruktioner, der gentages igen og igen, indtil den givne betingelse 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: “til sløjfestrømsdiagram”

Initialiseringstrin udføres først. Dette trin er at erklære og initialisere loopkontrolvariabler. Hvis betingelsen er sand, udføres udsagnene inde i de krøllede seler. Disse udsagn udføres, indtil betingelsen er sand. Hvis betingelsen er falsk, går kontrollen til den næste erklæring efter “for loop”. Efter udførelse af udsagn i løkken, går kontrollen til at ændre sektionen. Det er at opdatere loopkontrolvariablen. Derefter kontrolleres tilstanden igen. Hvis betingelsen er sand, udføres udsagnene inde i de krøllede seler. På denne måde itereres “for loop”.

I “while loop”, udsagnene inde i løkken udføres, indtil betingelsen er sand.

mens (betingelse)

// udsagn

I “do-while” -sløjfe, tilstanden kontrolleres i slutningen af ​​løkken. Så løkken udføres mindst én gang.

gøre

// udsagn

mens (betingelse)

Program til at finde fabrikken af ​​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 = factorial * i;

printf ("Factorial er% d \ n", factorial);

retur 0;

Hvad er ligheden mellem rekursion og itteration?

• Begge er teknikker til at løse et problem.
• Opgaven kan løses enten i rekursion eller iteration.

Hvad er forskellen mellem rekursion og itteration?

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 i rekursive programmer er højere end iterationer.	Rumkompleksiteten er lavere i iterationer.
Hastighed
Rekursionsudførelse er langsom.	Normalt er iteration hurtigere end rekursion.
Tilstand
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.
Kode læsbarhed
Et rekursivt program er mere læsbart.	Det iterative program er sværere at læse end et rekursivt program.

Resume - 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 til 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 ​​Rekursion vs Iteration

Du kan downloade PDF-version af denne artikel og bruge den til offline-formål som pr. Citatnotat. Download PDF-version her Forskel mellem rekursion og itteration

Reference:

1.Point, selvstudier. “Datakonstruktioner og algoritmer Recursion Basics.”, Tutorials Point, 15. august 2017. Findes her 
2.nareshtechnologies. “Rekursion i C-funktioner | C Language Tutorial ”YouTube, YouTube, 12. september 2016. Findes her  
3.yusuf shakeel. “Rekursionsalgoritme | Factorial - trin for trin guide ”YouTube, YouTube, 14. oktober 2013. Findes her  

Billede høflighed:

1.'CPT-Recursion-Factorial-Code 'By Pluke - Eget arbejde, (Public Domain) via Commons Wikimedia 
2.'For-loop-diagram'By Ingen maskine læsbar forfatter leveret - Eget arbejde antaget. (CC BY-SA 2.5) via Commons Wikimedia