Verschil tussen recursie en iteratie

Sleutelverschil - Recursie vs Iteratie
 

Recursie en iteratie kunnen worden gebruikt om programmeerproblemen op te lossen. De aanpak voor het oplossen van het probleem met behulp van recursie of iteratie is afhankelijk van de manier om het probleem op te lossen. De belangrijk verschil tussen recursie en iteratie is dat recursie is een mechanisme om een ​​functie binnen dezelfde functie aan te roepen terwijl iteratie een reeks instructies herhaaldelijk moet uitvoeren totdat de gegeven voorwaarde waar is. Recursie en iteratie zijn belangrijke technieken voor het ontwikkelen van algoritmen en het bouwen van softwaretoepassingen.

INHOUD

1. Overzicht en belangrijkste verschil
2. Wat is recursie
3. Wat is Iteratie
4. Overeenkomsten tussen recursie en iteratie
5. Vergelijking zij aan zij - Recursie versus iteratie in tabelvorm
6. Samenvatting

Wat is recursie?

Wanneer een functie zichzelf binnen de functie noemt, staat deze bekend als Recursie. Er zijn twee soorten recursie. Ze zijn eindige recursie en oneindige recursie. Eindige recursie heeft een beëindigende voorwaarde. Oneindige recursie heeft geen afsluitende voorwaarde.

Recursie kan met behulp van het programma worden uitgelegd om faculteiten te berekenen.

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

n! = 1, als n = 0;

Raadpleeg de onderstaande code om factor 3 te berekenen (3! = 3 * 2 * 1).

intmain ()

int waarde = faculteit (3);

printf ("Factorial is% d \ n", waarde);

retourneer 0;

intfactorial (intn)

if (n == 0)

terug 1;

anders

return n * faculteit (n-1);

Bij het aanroepen van factorial (3), zal die functie faculteit (2) aanroepen. Bij het aanroepen van factorial (2), zal die functie faculteit noemen (1). Dan zal faculteit (1) faculteit (0) noemen. faculteit (0) zal terugkeren 1. In het bovenstaande programma is de voorwaarde n == 0 in het "if-blok" de basisvoorwaarde. Volgens de overeenkomst wordt de faculteitfunctie steeds opnieuw genoemd.

Recursieve functies zijn gerelateerd aan de stapel. In C kan het hoofdprogramma vele functies hebben. Hoofd () is dus de aanroepende functie en de functie die door het hoofdprogramma wordt aangeroepen, is de aangeroepen functie. Wanneer de functie wordt aangeroepen, wordt de besturing aan de opgeroepen functie gegeven. Nadat de functie-uitvoering is voltooid, wordt het besturingselement teruggezet naar de hoofdfunctie. Daarna gaat het hoofdprogramma verder. Dus, het maakt een activeringsrecord of een stapelframe om de uitvoering voort te zetten.

Figuur 01: Recursie

In het bovenstaande programma, wanneer factorial (3) uit de main wordt aangeroepen, wordt een activeringsrecord in de call stack gemaakt. Vervolgens wordt een factorie (2) stapelframe boven op de stapel gemaakt, enzovoort. Het activeringsrecord houdt informatie bij over lokale variabelen, enzovoort. Telkens wanneer de functie wordt aangeroepen, wordt een nieuwe reeks lokale variabelen boven aan de stapel gemaakt. Deze stapelframes kunnen de snelheid vertragen. Ook in recursie roept een functie zichzelf aan. Tijdcomplexiteit voor een recursieve functie wordt gevonden door het aantal keren dat de functie wordt aangeroepen. Tijdcomplexiteit voor één functieaanroep is O (1). Voor n aantal recursieve oproepen is de tijdcomplexiteit O (n).

Wat is Iteratie?

Iteratie is een blok van instructies dat zich keer op keer herhaalt totdat de gegeven voorwaarde waar is. Iteratie kan worden bereikt met behulp van "for loop", "do-while loop" of "while loop". "For loop" -syntaxis is als volgt.

voor (initialisatie; voorwaarde; wijzigen)

// verklaringen;

Afbeelding 02: "voor lusstroomschema"

Initialisatiestap wordt als eerste uitgevoerd. Deze stap is om loop control-variabelen te declareren en te initialiseren. Als de voorwaarde waar is, worden de instructies binnen de accolades uitgevoerd. Die uitspraken worden uitgevoerd totdat de voorwaarde waar is. Als de voorwaarde onwaar is, gaat de besturing naar de volgende instructie na de "for-lus". Na het uitvoeren van de instructies binnen de lus, gaat de besturing de sectie wijzigen. Het is om de loop-regelvariabele bij te werken. Vervolgens wordt de voorwaarde opnieuw gecontroleerd. Als de voorwaarde waar is, worden de instructies binnen de accolades uitgevoerd. Op deze manier wordt de "for-lus" herhaald.

In "while loop", de instructies in de lus worden uitgevoerd totdat de voorwaarde waar is.

while (voorwaarde)

// statements

In "do-while" -lus, de voorwaarde wordt gecontroleerd aan het einde van de lus. De lus wordt dus minstens één keer uitgevoerd.

do

// statements

while (voorwaarde)

Programma om de faculteit van 3 (3!) Te vinden met behulp van iteratie ("for loop") is als volgt.

int main ()

intn = 3, faculteit = 1;

inti;

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

faculteit = faculteit * i;

printf ("Factorial is% d \ n", faculteit);

retourneer 0;

Wat zijn de overeenkomsten tussen recursie en iteratie?

• Beide zijn technieken om een ​​probleem op te lossen.
• De taak kan in recursie of iteratie worden opgelost.

Wat is het verschil tussen recursie en iteratie?

Recursie versus iteratie
Recursie is een methode om een ​​functie binnen dezelfde functie aan te roepen.	Iteratie is een blok met instructies dat herhaald wordt totdat de gegeven voorwaarde waar is.
Space Complexity
De ruimtecomplexiteit van recursieve programma's is hoger dan bij iteraties.	De ruimtecomplexiteit is lager in iteraties.
Snelheid
Recursie-uitvoering is traag.	Normaal gesproken is iteratie sneller dan recursie.
Staat
Als er geen beëindigingsvoorwaarde is, kan er een oneindige recursie zijn.	Als de voorwaarde nooit onwaar wordt, zal het een oneindige iteratie zijn.
stack
In recursie wordt de stapel gebruikt om lokale variabelen op te slaan wanneer de functie wordt aangeroepen.	In een iteratie wordt de stapel niet gebruikt.
Code leesbaarheid
Een recursief programma is beter leesbaar.	Het iteratieve programma is moeilijker te lezen dan een recursief programma.

Samenvatting - Recursie vs Iteratie

In dit artikel wordt het verschil tussen recursie en iteratie besproken. Beide kunnen worden gebruikt om programmeerproblemen op te lossen. Het verschil tussen recursie en iteratie is dat recursie een mechanisme is om een ​​functie binnen dezelfde functie aan te roepen en iteratie om een ​​reeks instructies herhaaldelijk uit te voeren totdat de gegeven voorwaarde waar is. Als een probleem in recursieve vorm kan worden opgelost, kan het ook worden opgelost met behulp van iteraties.

Download de PDF-versie van Recursie versus Iteratie

U kunt de PDF-versie van dit artikel downloaden en gebruiken voor offline doeleinden, zoals per citaatnotitie. Download hier de PDF-versie Difference Between Recursion and Iteration

Referentie:

1.Point, zelfstudies. "Data Structures and Algorithms Recursion Basics.", Tutorials Point, 15 aug. 2017. Beschikbaar Hier 
2.nareshtechnologies. "Recursie in C-functies | C Taalcursus "YouTube, YouTube, 12 september 2016.  Beschikbaar Hier  
3.yusuf shakeel. "Recursie-algoritme | Factorial - stap voor stap handleiding "YouTube, YouTube, 14 oktober 2013.  Beschikbaar Hier  

Afbeelding met dank aan:

1.'CPT-Recursion-Factorial-Code'door Pluke - Eigen werk, (Public Domain) via Commons Wikimedia 
2. 'For-loop-diagram'door Geen machineleesbare auteur opgegeven - Eigen werk verondersteld. (CC BY-SA 2.5) via Commons Wikimedia