Forskjellen mellom rekursjon og gjentagelse

Nøkkelforskjell - Rekursjon vs Iteration
 

Rekursjon og gjentagelse kan brukes til å løse programmeringsproblemer. Tilnærmingen til å løse problemet ved å bruke rekursjon eller iterasjon avhenger av måten å løse problemet på. De nøkkelforskjell mellom rekursjon og iterasjon er det rekursjon er en mekanisme for å ringe en funksjon i samme funksjon mens iterasjon er å utføre et sett med instruksjoner gjentatte ganger til den gitte tilstanden er sant. Rekursjon og læring er viktige teknikker for å utvikle algoritmer og bygge programvareapplikasjoner.

INNHOLD

1. Oversikt og nøkkelforskjell
2. Hva er rekursjon
3. Hva er Iteration
4. Likheter mellom rekursjon og gjentagelse
5. Side ved side-sammenligning - Recursion vs Iteration i tabellform
6. Sammendrag

Hva er rekursjon?

Når en funksjon kaller seg innenfor funksjonen, kalles den Recursion. Det er to typer rekursjon. De er endelige rekursjon og uendelig rekursjon. Finite rekursjon har en avsluttende tilstand. Uendelig rekursjon har ikke en avslutende tilstand.

Rekursjon kan forklares ved hjelp av programmet for å beregne factorials.

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

n! = 1, hvis n = 0;

Se bellow-koden for å beregne faktorial av 3 (3! = 3 * 2 * 1).

intmain ()

int verdi = faktorial (3);

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

returner 0;

intfaktoriell (intn)

hvis (n == 0)

returnere 1;

ellers

returnere n * faktorial (n-1);

Når du ringer faktorial (3), vil den funksjonen kalle fakultet (2). Når man ringer faktorial (2), vil den funksjonen kalle fakultet (1). Da vil faktorial (1) kalle fakultet (0). Faktorisk (0) vil returnere 1. I det ovennevnte programmet er n == 0 betingelsen i "if block" grunnverdien. I likhet med det kalles den faktorielle funksjonen igjen og igjen.

Rekursive funksjoner er relatert til stakken. I C kan hovedprogrammet ha mange funksjoner. Så, main () er kallfunksjonen, og funksjonen som kalles av hovedprogrammet, er den kalt funksjonen. Når funksjonen kalles, blir kontrollen gitt til den kalt funksjonen. Etter at funksjonen er fullført, blir kontrollen returnert til hovedmenyen. Deretter fortsetter hovedprogrammet. Så, det oppretter en aktiveringsoppføring eller en stabelramme for å fortsette å utføre.

Figur 01: Rekursjon

I det ovennevnte programmet, når det kalles faktorial (3) fra hoved, oppretter det en aktiveringspost i anropsstakken. Deretter blir faktorial (2) stabelramme opprettet på toppen av stabelen og så videre. Aktiveringsposten inneholder informasjon om lokale variabler etc. Hver gang funksjonen kalles, opprettes et nytt sett med lokale variabler øverst på stakken. Disse stabelrammene kan redusere hastigheten oppover. På samme måte i rekursjon, kaller en funksjon seg selv. Tidskompleksiteten for en rekursiv funksjon er funnet av antall ganger, funksjonen kalles. Tids kompleksitet for ett funksjonsanrop er O (1). For n antall rekursive samtaler er tidskompleksiteten O (n).

Hva er Iteration?

Iterasjon er en blokk med instruksjoner som gjentas igjen og igjen til den gitte tilstanden er sant. Iterasjon kan oppnås ved bruk av "for loop", "do-while loop" eller "while loop". Syntaxen "for loop" er som følger.

for (initialisering, tilstand, modifisering)

// uttalelser;

Figur 02: "for kretsløpsdiagram"

Initialiseringstrinn utføres først. Dette trinnet er å erklære og initialisere loop-kontrollvariabler. Hvis tilstanden er sant, utfører uttalelsene i de krøllete båndene. Disse utsagnene utføres til tilstanden er sant. Hvis tilstanden er feil, går kontrollen til neste setning etter "for loop". Etter å ha utført uttalelsene inne i løkken, går kontrollen for å endre seksjonen. Det er å oppdatere loopkontrollvariabelen. Deretter kontrolleres tilstanden igjen. Hvis tilstanden er sant, vil utsagnene inne i de krøllete båndene utføres. På denne måten blir "for loop" iterates.

I "while loop", utsagnene i løkken utføres til tilstanden er sant.

mens (tilstand)

// uttalelser

I "do-while" -løkke, tilstanden kontrolleres på slutten av løkken. Så løper løkken minst en gang.

gjøre

// uttalelser

mens (tilstand)

Program for å finne faktorial av 3 (3!) Ved hjelp av iterasjon ("for loop") er som følger.

int main ()

intn = 3, faktorial = 1;

inti;

for (i = 1; i<=n ; i++)

factorial = factorial * jeg;

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

returner 0;

Hva er likhetene mellom rekursjon og gjentagelse?

• Begge er teknikker for å løse et problem.
• Oppgaven kan løses enten i rekursjon eller iterasjon.

Hva er forskjellen mellom rekursjon og gjentagelse?

Recursion vs Iteration
Rekursjon er en metode for å kalle en funksjon innenfor samme funksjon.	Iterasjon er en blokk med instruksjoner som gjentar til den oppgitte tilstanden er sant.
Plass kompleksitet
Rymlekompleksiteten til rekursive programmer er høyere enn iterasjoner.	Mellomkompleksiteten er lavere i iterasjoner.
Hastighet
Rekursjonen er langsom.	Normalt er iterasjon raskere enn rekursjon.
Tilstand
Hvis det ikke er noen oppsigelsestilstand, kan det være en uendelig rekursjon.	Hvis tilstanden aldri blir falsk, blir det en uendelig iterasjon.
Stable
I rekursjon brukes stakken til å lagre lokale variabler når funksjonen kalles.	I en iterasjon blir stakken ikke brukt.
Kode Lesbarhet
Et rekursivt program er mer lesbart.	Det iterative programmet er vanskeligere å lese enn et rekursivt program.

Sammendrag - Rekursjon vs Iteration

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 i samme funksjon og iterasjon det å utføre et sett med instruksjoner gjentatte ganger til den gitte tilstanden 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 off-line formål som per sitatnotat. Vennligst last ned PDF-versjon her Difference Between Recursion and Iteration

Henvisning:

1.Point, opplæringsprogrammer. "Datastrukturer og algoritmer Recursion Basics.", Tutorials Point, 15. august 2017. Tilgjengelig her 
2.nareshtechnologies. "Rekursjon i C-funksjoner | C Language Tutorial "YouTube, YouTube, 12. september 2016.  Tilgjengelig her  
3.yusuf shakeel. "Rekursjonsalgoritme | Faktorisk - trinnvis veiledning "YouTube, YouTube, 14. oktober 2013.  Tilgjengelig her  

Bilde Courtesy:

1.'CPT-Recursion-Factorial-Code'By Pluke - Eget arbeid, (Public Domain) via Commons Wikimedia 
2.'For-loop-diagram'Er ingen maskinlesbar forfatter oppgitt - eget arbeid antatt. (CC BY-SA 2.5) via Commons Wikimedia