Belangrijk verschil - Recursie versus 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 hangt af van de manier om het probleem op te lossen. 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 softwaretoepassingen.
Wat is recursie?
Als een functie zichzelf aanroept binnen de functie, staat het bekend als recursie. Er zijn twee soorten recursie. Ze zijn eindige recursie en oneindige recursie. Eindige recursie heeft een eindvoorwaarde. Oneindige recursie heeft geen beëindigingsvoorwaarde.
Recursie kan worden uitgelegd met behulp van het programma om faculteiten te berekenen.
n!=n(n-1)!, als n>0
n!=1, als n=0;
Raadpleeg de onderstaande code om de faculteit van 3(3!=321) te berekenen.
intmain () {
int waarde=faculteit (3);
printf(“Factoriaal is %d\n”, waarde);
retour 0;
}
intfactorieel (intn) {
if(n==0) {
retour 1;
}
anders {
return n faculteit(n-1);
}
}
Bij het aanroepen van faculteit (3), roept die functie faculteit (2) aan. Bij het aanroepen van faculteit (2), roept die functie faculteit (1) aan. Dan zal faculteit (1) faculteit (0) aanroepen. faculteit (0) retourneert 1. In het bovenstaande programma is de n==0 voorwaarde in het “if block” de basisvoorwaarde. Volgens de Evenzo wordt de faculteitsfunctie 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 besturing gegeven aan de aangeroepen functie. Nadat de functie-uitvoering is voltooid, keert de besturing terug naar main. Daarna gaat het hoofdprogramma verder. Het creëert dus een activeringsrecord of een stapelframe om door te gaan met de uitvoering.
Figuur 01: Recursie
In het bovenstaande programma wordt bij het aanroepen van faculteit (3) vanuit het hoofd een activeringsrecord in de oproepstack gemaakt. Vervolgens wordt er een faculteit (2) stapelframe bovenop de stapel gemaakt, enzovoort. Het activeringsrecord houdt informatie bij over lokale variabelen enz. Elke keer dat de functie wordt aangeroepen, wordt er een nieuwe set lokale variabelen bovenaan de stapel gemaakt. Deze stapelframes kunnen de snelheid vertragen. Evenzo roept een functie zichzelf aan in recursie. Tijdcomplexiteit voor een recursieve functie wordt gevonden door het aantal keren dat de functie wordt aangeroepen. De tijdcomplexiteit 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 steeds opnieuw wordt herhaald 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.
for (initialisatie; voorwaarde; wijzigen) {
// uitspraken;
}
Figuur 02: “voor lusstroomdiagram”
Initialisatiestap wordt als eerste uitgevoerd. Deze stap is om luscontrolevariabelen te declareren en te initialiseren. Als de voorwaarde waar is, worden de instructies tussen de accolades uitgevoerd. Die instructies 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 in de lus, gaat de besturing naar de sectie wijzigen. Het is om de regelvariabele van de lus bij te werken. Daarna wordt de toestand opnieuw gecontroleerd. Als de voorwaarde waar is, worden de instructies tussen de accolades uitgevoerd. Op deze manier wordt de "for-lus" herhaald.
In “while loop” worden de instructies binnen de lus uitgevoerd totdat de voorwaarde waar is.
terwijl (voorwaarde){
//statements
}
In de "do-while"-lus wordt de voorwaarde 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;
for(i=1; i<=n; i++){
faculteit=faculteiti;
}
printf(“Factoriaal is %d\n”, faculteit);
retour 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?
Recursie versus iteratie |
|
| 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. |
| Ruimtecomplexiteit | |
| De ruimtecomplexiteit van recursieve programma's is hoger dan iteraties. | Ruimtecomplexiteit is lager in iteraties. |
| Snelheid | |
| Recursie-uitvoering is traag. | Normaal gesproken is iteratie sneller dan recursie. |
| Conditie | |
| Als er geen beëindigingsvoorwaarde is, kan er een oneindige recursie zijn. | Als de voorwaarde nooit onwaar wordt, zal het een oneindige herhaling zijn. |
| Stapel | |
| 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. |
| Codeleesbaarheid | |
| Een recursief programma is beter leesbaar. | Het iteratieve programma is moeilijker te lezen dan een recursief programma. |
Samenvatting – Recursie versus iteratie
Dit artikel besprak het verschil tussen recursie en iteratie. 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 te herhalen om een reeks instructies herhaaldelijk uit te voeren totdat de gegeven voorwaarde waar is. Als een probleem recursief 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 volgens de citatienota. Download hier de PDF-versie. Verschil tussen recursie en iteratie
