nyckelskillnad – rekursion vs iteration
Rekursion och Iteration kan användas för att lösa programmeringsproblem. Tillvägagångssättet för att lösa problemet med hjälp av rekursion eller iteration beror på sättet att lösa problemet. Den viktigaste skillnaden mellan rekursion och iteration är att rekursion är en mekanism för att anropa en funktion inom samma funktion medan iteration är att exekvera en uppsättning instruktioner upprepade gånger tills det givna villkoret är sant. Rekursion och iteration är viktiga tekniker för att utveckla algoritmer och bygga mjukvaruapplikationer.
Vad är rekursion?
När en funktion anropar sig själv inom funktionen kallas den för rekursion. Det finns två typer av rekursion. De är finit rekursion och oändlig rekursion. Finit rekursion har ett avslutande tillstånd. Oändlig rekursion har inget avslutande villkor.
Rekursion kan förklaras med hjälp av programmet för att beräkna faktoraler.
n!=n(n-1)!, om n>0
n!=1, om n=0;
Se nedanstående kod för att beräkna faktorial av 3(3!=321).
intmain () {
int värde=faktoriellt (3);
printf("Faktoral är %d\n", värde);
return 0;
}
intfatorial (intn) {
if(n==0) {
retur 1;
}
else {
return n factorial(n-1);
}
}
När du anropar faktoriell (3), kommer den funktionen att anropa faktoriell (2). När du anropar faktoriell (2), kommer den funktionen att anropa faktoriell (1). Då kommer factorial (1) att anropa factorial (0). factorial (0) kommer att returnera 1. I programmet ovan är n==0-villkoret i "om-blocket" basvillkoret. Enligt Likaså anropas faktorfunktionen om och om igen.
Rekursiva funktioner är relaterade till stacken. I C kan huvudprogrammet ha många funktioner. Så, main () är den anropande funktionen, och funktionen som anropas av huvudprogrammet är den anropade funktionen. När funktionen anropas ges kontrollen till den anropade funktionen. Efter att funktionsexekveringen är klar, återgår kontrollen till main. Sedan fortsätter huvudprogrammet. Så det skapar en aktiveringspost eller en stackram för att fortsätta körningen.
Figur 01: Rekursion
I programmet ovan, när man anropar faktoriell (3) från main, skapar det en aktiveringspost i samtalsstacken. Sedan skapas en faktoriell (2) stapelram ovanpå stapeln och så vidare. Aktiveringsposten lagrar information om lokala variabler etc. Varje gång funktionen anropas skapas en ny uppsättning lokala variabler på toppen av stacken. Dessa stackramar kan sakta ner hastigheten. Likaså i rekursion kallar en funktion sig själv. Tidskomplexiteten för en rekursiv funktion hittas av antalet gånger som funktionen anropas. Tidskomplexiteten för ett funktionsanrop är O(1). För n antal rekursiva samtal är tidskomplexiteten O(n).
Vad är Iteration?
Iteration är ett block med instruktioner som upprepas om och om igen tills det givna villkoret är sant. Iteration kan uppnås med "for loop", "do-while loop" eller "while loop". "for loop"-syntax är som följer.
for (initiering; villkor; modifiera) {
// uttalanden;
}
Figur 02: "för loop-flödesdiagram"
Initieringssteget körs först. Detta steg är att deklarera och initiera loopkontrollvariabler. Om villkoret är sant, exekveras uttalandena inuti de lockiga klammerparenteserna. Dessa uttalanden körs tills villkoret är sant. Om villkoret är falskt går kontrollen till nästa sats efter "for loop". Efter att ha kört satserna i slingan går kontrollen till modifieringssektionen. Det är för att uppdatera loopkontrollvariabeln. Sedan kontrolleras tillståndet igen. Om villkoret är sant kommer uttalandena inuti de lockiga klammerparenteserna att köras. På så sätt upprepas "för-slingan".
I "while loop" körs satserna inuti loopen tills villkoret är sant.
while (skick){
//statements
}
I “do-while”-loopen kontrolleras villkoret i slutet av loopen. Så slingan körs minst en gång.
do{
//statements
} while(condition)
Programmera för att hitta faktorvärdet för 3 (3!) med iteration (“för loop”) är som följer.
int main(){
intn=3, factorial=1;
inti;
for(i=1; i<=n; i++){
faktoriell=faktorielli;
}
printf(“Faktorial är %d\n”, faktoriell);
return 0;
}
Vilka är likheterna mellan rekursion och iteration?
- Båda är tekniker för att lösa ett problem.
- Uppgiften kan lösas antingen i rekursion eller iteration.
Vad är skillnaden mellan rekursion och iteration?
Rekursion vs Iteration |
|
| Rekursion är en metod för att anropa en funktion inom samma funktion. | Iteration är ett block med instruktioner som upprepas tills det givna villkoret är sant. |
| Rymdens komplexitet | |
| Rymdens komplexitet för rekursiva program är högre än iterationer. | Rymdens komplexitet är lägre i iterationer. |
| Speed | |
| Rekursionsexekveringen är långsam. | Norm alt är iteration snabbare än rekursion. |
| Skicka | |
| Om det inte finns något uppsägningsvillkor kan det finnas en oändlig rekursion. | Om villkoret aldrig blir falskt blir det en oändlig iteration. |
| Stack | |
| I rekursion används stacken för att lagra lokala variabler när funktionen anropas. | I en iteration används inte stacken. |
| Kodläsbarhet | |
| Ett rekursivt program är mer läsbart. | Det iterativa programmet är svårare att läsa än ett rekursivt program. |
Sammanfattning – Rekursion vs Iteration
Den här artikeln diskuterade skillnaden mellan rekursion och iteration. Båda kan användas för att lösa programmeringsproblem. Skillnaden mellan rekursion och iteration är att rekursion är en mekanism för att anropa en funktion inom samma funktion och iterera den för att exekvera en uppsättning instruktioner upprepade gånger tills det givna villkoret är sant. Om ett problem kan lösas i rekursiv form kan det också lösas med iterationer.
Ladda ned PDF-versionen av Recursion vs Iteration
Du kan ladda ner PDF-versionen av den här artikeln och använda den för offlineändamål enligt citat. Ladda ner PDF-versionen här Skillnaden mellan rekursion och iteration
