Belangrijkste verschil - Recursie versus iteratie
Recursie en iteratie kunnen worden gebruikt om programmeerproblemen op te lossen. De aanpak om het probleem op te lossen door middel van recursie of iteratie, hangt af van de manier waarop het probleem wordt opgelost. Het belangrijkste verschil tussen recursie en iteratie is dat recursie een mechanisme is om een functie binnen dezelfde functie aan te roepen, terwijl iteratie is om een reeks instructies herhaaldelijk uit te voeren totdat de gegeven voorwaarde waar is. Recursie en iteratie zijn belangrijke technieken voor het ontwikkelen van algoritmen en het bouwen van softwareapplicaties.
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 aanroept, staat deze bekend als recursie. Er zijn twee soorten recursie. Het zijn eindige recursie en oneindige recursie. Eindige recursie heeft een beëindigende voorwaarde. Oneindige recursie heeft geen beëindigende voorwaarde.
Recursie kan worden verklaard met behulp van het programma om faculteiten te berekenen.
n! = n * (n-1)!, als n> 0
n! = 1, als n = 0;
Raadpleeg de balgcode om faculteit van 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) {
terugkeer 1;
}
anders {
retourneer n * faculteit (n-1);
}
}
Wanneer faculteit (3) wordt aangeroepen, roept die functie faculteit (2) aan. Wanneer faculteit (2) wordt aangeroepen, roept die functie faculteit (1) aan. Dan zal faculteit (1) faculteit (0) aanroepen. factorial (0) zal 1 teruggeven. In het bovenstaande programma is n == 0 conditie in het “if block” de basis conditie. Volgens de Evenzo wordt de faculteitfunctie keer op keer aangeroepen.
Recursieve functies zijn gerelateerd aan de stapel. In C kan het hoofdprogramma veel functies hebben. Dus main () is de aanroepende functie, en de functie die wordt aangeroepen door het hoofdprogramma is de aangeroepen functie. Wanneer de functie wordt aangeroepen, wordt de controle aan de aangeroepen functie gegeven. Nadat de uitvoering van de functie is voltooid, keert de besturing terug naar main. Daarna gaat het hoofdprogramma verder. Het maakt dus een activeringsrecord of een stapelframe om de uitvoering voort te zetten.
Figuur 01: recursie
In het bovenstaande programma wordt bij het aanroepen van factorial (3) vanuit main een activeringsrecord in de call-stack gemaakt. Vervolgens wordt factorieel (2) stapelframe gemaakt bovenop de stapel, enzovoort. Het activeringsrecord houdt informatie bij over lokale variabelen enz. Elke keer dat de functie wordt aangeroepen, wordt een nieuwe set lokale variabelen bovenaan de stapel aangemaakt. Deze stapelframes kunnen de snelheid vertragen. Evenzo roept bij recursie een functie zichzelf aan. Tijdscomplexiteit voor een recursieve functie wordt bepaald door het aantal keren dat de functie wordt aangeroepen. Tijdscomplexiteit voor één functieaanroep is O (1). Voor n aantal recursieve aanroepen is de tijdcomplexiteit O (n).
Wat is iteratie?
Iteratie is een blok instructies dat zich keer op keer herhaalt totdat de gegeven voorwaarde waar is. Iteratie kan worden bereikt door middel van "for loop", "do-while loop" of "while loop". De syntaxis "for loop" is als volgt.
voor (initialisatie; voorwaarde; wijzigen) {
// verklaringen;
}
Figuur 02: "voor lusstroomschema"
De initialisatiestap wordt eerst uitgevoerd. Deze stap is het declareren en initialiseren van lusbesturingsvariabelen. 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 controle naar de volgende instructie na de "for-lus". Na het uitvoeren van de instructies in de lus, gaat de besturing naar de sectie wijzigen. Het is om de regelvariabele van de lus bij te werken. Vervolgens wordt de toestand opnieuw gecontroleerd. Als de voorwaarde waar is, worden de instructies binnen de accolades uitgevoerd. Op deze manier itereert de "for-lus".
In "while-lus" worden de instructies in de lus uitgevoerd totdat de voorwaarde waar is.
while (voorwaarde) {
// verklaringen
}
In de "do-while" -lus wordt de conditie aan het einde van de lus gecontroleerd. De lus wordt dus minstens één keer uitgevoerd.
Doen{
// verklaringen
} while (voorwaarde)
Programma om de faculteit van 3 (3!) Te vinden met behulp van iteratie ("for lus") 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 worden opgelost in recursie of iteratie.
Wat is het verschil tussen recursie en iteratie?
Diff Artikel Midden voor Tafel
Recursie versus herhaling |
|
| Recursie is een methode om een functie binnen dezelfde functie aan te roepen. | Iteratie is een blok instructies dat wordt herhaald totdat de gegeven voorwaarde waar is. |
| Complexiteit van de ruimte | |
| De ruimtecomplexiteit van recursieve programma's is hoger dan iteraties. | De complexiteit van de ruimte is lager in iteraties. |
| Snelheid | |
| De uitvoering van de recursie 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. |
| Stapel | |
| Bij recursie wordt de stapel gebruikt om lokale variabelen op te slaan wanneer de functie wordt aangeroepen. | Bij 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 versus herhaling
In dit artikel is 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 deze herhaalt 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 met iteraties worden opgelost.
Download de pdf-versie van recursie versus iteratie
U kunt de PDF-versie van dit artikel downloaden en voor offline doeleinden gebruiken volgens de citatienota. Download hier de pdf-versie. Verschil tussen recursie en herhaling
