Skillnad mellan rekursion och iteration

Huvudskillnad - Recursion vs iteration
 

Recursion och Iteration kan användas för att lösa programmeringsproblem. Tillvägagångssättet att lösa problemet med recursion eller iteration beror på hur man löser problemet. De nyckelskillnad mellan rekursion och iteration är det rekursion är en mekanism för att ringa en funktion inom samma funktion medan iteration är att utföra en uppsättning instruktioner upprepade gånger tills det givna tillståndet är sant. Recursion and Iteration är viktiga tekniker för att utveckla algoritmer och bygga programvaror.

INNEHÅLL

1. Översikt och nyckelskillnad
2. Vad är Recursion
3. Vad är iteration
4. Likheter mellan rekursion och iteration
5. Jämförelse vid sida vid sida - Recursion vs Iteration i tabellform
6. Sammanfattning

Vad är Recursion?

När en funktion kallar sig inom funktionen kallas den Recursion. Det finns två typer av rekursion. De är ändamålsenlig recursion och oändlig recursion. Finite recursion har ett avslutande tillstånd. Oändlig recursion har inte ett avslutande tillstånd.

Rekursionen kan förklaras med hjälp av programmet för att beräkna factorials.

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

n! = 1, om n = 0;

Se bellow-koden för att beräkna faktorial av 3 (3! = 3 * 2 * 1).

intmain ()

int värde = faktoriellt (3);

printf ("Factorial är% d \ n", värde);

returnera 0;

intfaktoriellt (intn)

om (n == 0)

returnera 1;

annars

returnera n * factorial (n-1);

När man ringer fakultet (3), kommer den funktionen att ringa factorial (2). När man ringer faktoriell (2), kommer den funktionen att kalla factorial (1). Då factorial (1) kommer att ringa factorial (0). Faktoriell (0) kommer att returnera 1. I ovanstående program är n == 0 villkoret i "if block" det grundläggande villkoret. Enligt Likaså kallas den faktoriella funktionen om och om igen.

Rekursiva funktioner är relaterade till stapeln. I C kan huvudprogrammet ha många funktioner. Så, huvud () är anropsfunktionen, och den funktion som kallas av huvudprogrammet är den kallade funktionen. När funktionen kallas, ges kontrollen till den uppringda funktionen. Efter att funktionen utförd är kontrollen tillbaka till huvudet. Sedan fortsätter huvudprogrammet. Så skapar det en aktiveringsrekord eller en stapelram för att fortsätta exekveringen.

Figur 01: Rekursion

I det ovanstående programmet skapas en aktiveringspost i samtalstacken när man ringer faktorial (3) från huvudmenyn. Sedan skapas faktoriell (2) stapelram ovanpå stapeln och så vidare. Aktiveringsposten håller information om lokala variabler etc. Varje gång funktionen kallas skapas en ny uppsättning lokala variabler ovanpå stapeln. Dessa stapelramar kan sakta ner hastigheten. På samma sätt i rekursion, kallar en funktion sig själv. Tidskomplexiteten för en rekursiv funktion hittas av antalet gånger, funktionen heter. Tidskomplexiteten för ett funktionssamtal är O (1). För n antal rekursiva samtal är tidskomplexiteten O (n).

Vad är iteration?

Iteration är ett block av instruktioner som upprepas om och om igen tills det givna villkoret är sant. Iteration kan uppnås med "för loop", "do-while loop" eller "while loop". Syntax för "loop" är som följer.

för (initialisering, villkor, modifiera)

// uttalanden;

Figur 02: "för slinga flödesdiagram"

Initialiseringssteget exekveras först. Detta steg är att deklarera och initiera loop-kontrollvariabler. Om villkoret är sant utförs uttalandena inuti de krökta hängslen. Dessa uttalanden verkställer tills villkoret är sant. Om villkoret är felaktigt går kontrollen till nästa uttalande efter "för loop". Efter att ha genomfört deklarationerna i slingan går kontrollen för att ändra sektionen. Det är att uppdatera loopkontrollvariabeln. Då kontrolleras villkoret igen. Om villkoret är sant, kommer uttalandena inuti de lockiga hävarmarna att utföras. På så sätt iter "for loop" iterates.

I "while loop", uttalandena i slingan exekverar tills tillståndet är sant.

medan (villkor)

// uttalanden

I "do-while" -slinga, villkoret kontrolleras i slutet av slingan. Så körs slingan minst en gång.

do

// uttalanden

medan (villkor)

Program för att hitta fakta om 3 (3!) Med hjälp av iteration ("for loop") är som följer.

int main ()

intn = 3, factorial = 1;

inti;

för (i = 1; i<=n ; i++)

factorial = factorial * jag;

printf ("Factorial är% d \ n", factorial);

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 recursion och iteration?

Recursion vs Iteration
Recursion är ett sätt att ringa en funktion inom samma funktion.	Iteration är ett block av instruktioner som upprepas tills det givna villkoret är sant.
Rymdkomplexitet
Utrymme komplexiteten av rekursiva program är högre än iterationer.	Rymkomplexiteten är lägre i iterationer.
Fart
Rekursionen är långsamt.	Normalt är iteration snabbare än rekursion.
Tillstånd
Om det inte finns något uppsägningstillstånd kan det finnas en oändlig recursion.	Om tillståndet aldrig blir falskt kommer det att bli en oändlig iteration.
Stack
I rekursion används stapeln för att lagra lokala variabler när funktionen heter.	I en iteration används stacken inte.
Kod läsbarhet
Ett rekursivt program är mer läsligt.	Det iterativa programmet är svårare att läsa än ett rekursivt program.

Sammanfattning - Rekursion vs iteration

I denna artikel diskuterades 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 ringa en funktion inom samma funktion och iteration att utföra en uppsättning instruktioner upprepade gånger tills det givna tillståndet är sant. Om ett problem kan lösas i rekursiv form kan den också lösas med hjälp av iterationer.

Ladda ner PDF-versionen av Recursion vs Iteration

Du kan hämta PDF-versionen av den här artikeln och använda den för offlineändamål enligt citationsnotat. Var god ladda ner PDF-versionen här Skillnaden mellan rekursion och efterbehandling

Referens:

1.Point, handledning. "Datastrukturer och algoritmer Recursion Basics.", Tutorials Point, 15 aug 2017. Tillgänglig här 
2.nareshtechnologies. "Rekursion i C Funktioner | C Language Tutorial "YouTube, YouTube, 12 september 2016.  Tillgänglig här  
3.yusuf shakeel. "Rekursionsalgoritm | Factorial - steg för steg guide "YouTube, YouTube, 14 oktober 2013.  Tillgänglig här  

Image Courtesy:

1.CPT-Recursion-Factorial-Code'By Pluke - eget arbete, (Public Domain) via Commons Wikimedia 
2.'For-loop-diagram'En Ingen maskinläsbar författare tillhandahållen - Egent arbete antaget. (CC BY-SA 2.5) via Commons Wikimedia