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 rekursion eller iteration beror på sättet att lösa problemet. Huvudskillnaden mellan rekursion och iteration är att rekursion är en mekanism för att anropa en funktion inom samma funktion medan iteration är att utföra en uppsättning instruktioner upprepade gånger tills det angivna villkoret är sant. Rekursion och Iteration är viktiga tekniker för att utveckla algoritmer och bygga programapplikationer.
INNEHÅLL
1. Översikt och nyckelskillnad
2. Vad är rekursion
3. Vad är itteration
4. Likheter mellan rekursion och itteration
5. Jämförelse sida vid sida - Rekursion mot Iteration i tabellform
6. Sammanfattning
Vad är rekursion?
När en funktion kallar sig inom funktionen kallas den rekursion. Det finns två typer av rekursion. De är ändlig rekursion och oändlig rekursion. Ändlig rekursion har ett avslutande tillstånd. Oändlig rekursion har inte ett avslutande tillstånd.
Rekursion kan förklaras med hjälp av programmet för att beräkna fakta.
n! = n * (n-1) !, om n> 0
n! = 1, om n = 0;
Se nedanstående kod för att beräkna en faktor av 3 (3! = 3 * 2 * 1).
intmain () {
int värde = faktor (3);
printf ("Faktor är% d / n", värde);
returnera 0;
}
intakt (intn) {
om (n == 0) {
retur 1;
}
annat {
returnera n * faktor (n-1);
}
}
När du ringer till factorial (3) kallar den funktionen factorial (2). När du ringer till factorial (2) kallar den funktionen factorial (1). Då kallar factorial (1) factorial (0). factorial (0) returnerar 1. I ovanstående program är n == 0 villkor i "if blocket" basvillkoret. Enligt Likewise kallas fakturafunktionen 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 funktionen har utförts återställs 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 ovanstående program skapar det en aktiveringspost i samtalsstacken när man anropar en faktor (3) från huvud. Då skapas en (2) stapelram ovanpå stapeln och så vidare. Aktiveringsposten håller information om lokala variabler etc. Varje gång funktionen anropas skapas en ny uppsättning lokala variabler överst i stacken. Dessa stackramar kan sakta ner hastigheten. På samma sätt i rekursion kallar en funktion sig själv. Tidskomplexitet för en rekursiv funktion hittas av antalet gånger, funktionen kallas. Tidskomplexitet för ett funktionsanrop är O (1). För n antal rekursiva samtal är tidskomplexiteten O (n).
Vad är Iteration?
Iteration är ett instruktionsblock som upprepas om och om igen tills det angivna villkoret är sant. Iteration kan uppnås med "for loop", "do-while loop" eller "while loop". "För loop" syntax är som följer.
för (initialisering; villkor; modifiera) {
// uttalanden;
}
Bild 02:”för slingflödesdiagram”
Initieringssteget körs först. Detta steg är att deklarera och initiera loopkontrollvariabler. Om villkoret är sant utförs påståenden i de lockiga hängslen. Dessa uttalanden utförs tills villkoret är sant. Om villkoret är falskt går kontrollen till nästa uttalande efter "for loop". Efter att ha utfört uttalandena i slingan går kontrollen till att ändra avsnittet. Det är att uppdatera loop-variabeln. Sedan kontrolleras tillståndet igen. Om villkoret är sant, kommer uttalandena i de lockiga hängslen att utföras. På det sättet itererar "for loop".
I "while loop" körs påståendena inuti loop tills dess att villkoret är sant.
medan (villkor) {
// uttalanden
}
I "do-while" -slinga kontrolleras tillståndet i slutet av slingan. Så slingan körs minst en gång.
do{
// uttalanden
} medan (villkor)
Programmet för att hitta faktorn 3 (3!) Med iteration (“for loop”) är som följer.
int main () {
intn = 3, factorial = 1;
inti;
för (i = 1; i <= n; i ++) {
faktoria = faktoria * i;
}
printf ("Faktor är% d / n", faktoria);
returnera 0;
}
Vad ä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?
Skilja artikeln mitt före bordet
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 angivna villkoret är sant. |
| Rymdkomplexitet | |
| Rymdkomplexiteten hos rekursiva program är högre än iterationer. | Rymdkomplexitet är lägre i iterationer. |
| Hastighet | |
| Rekursionsexekveringen är långsam. | Normalt är iteration snabbare än rekursion. |
| Skick | |
| 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
Denna artikel 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 iteration att utföra en uppsättning instruktioner upprepade gånger tills det angivna villkoret är sant. Om ett problem kan lösas i rekursiv form kan det också lösas med iterationer.
Ladda ner 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 itteration
