Rozdiel medzi rekurziou a iteráciou

Kľúčový rozdiel - rekurzia vs Iterácia
 

Rekurziu a iteráciu možno použiť na riešenie problémov s programovaním. Prístup k riešeniu problému pomocou rekurzie alebo iterácie závisí od spôsobu riešenia problému. kľúčový rozdiel medzi rekurziou a iteráciou je to rekurzia je mechanizmus na vyvolanie funkcie v rámci tej istej funkcie, zatiaľ čo iterácia má opakovane vykonávať množinu pokynov, až kým daná podmienka nie je splnená.. Rekurzia a iterácia sú hlavnými technikami vývoja algoritmov a zostavovania softvérových aplikácií.

OBSAH

1. Prehľad a kľúčový rozdiel
2. Čo je rekurzia
3. Čo je iterácia
4. Podobnosti medzi rekurziou a iteráciou
5. Porovnanie vedľa seba - Rekurzia verzus Iterácia v tabuľkovej forme
6. Zhrnutie

Čo je rekurzia?

Keď sa funkcia volá v rámci funkcie, je známa ako Rekurzia. Existujú dva typy rekurzie. Sú to konečná rekurzia a nekonečná rekurzia. Konečná rekurzia má ukončovaciu podmienku. Nekonečná rekurzia nemá ukončovaciu podmienku.

Rekurzia sa dá vysvetliť pomocou programu na výpočet faktoriálov.

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

n! = 1, ak n = 0;

Pomocou nasledujúceho kódu vypočítajte faktoriál 3 (3! = 3 * 2 * 1).

intmain ()

int hodnota = faktoriál (3);

printf („Factorial is% d \ n“, hodnota);

návrat 0;

intfactorial (intn)

ak (n == 0)

návrat 1;

else

návrat n * faktoriál (n-1);

Pri volaní faktoriálu (3) táto funkcia vyvolá faktoriál (2). Pri volaní faktoriálu (2) sa touto funkciou volá faktoriál (1). Potom faktoriál (1) zavolá faktoriál (0). faktoriál (0) sa vráti 1. V uvedenom programe je podmienka n == 0 v podmienke „if block“ základnou podmienkou. Podľa podobne sa faktoriálna funkcia volá znova a znova.

Rekurzívne funkcie súvisia so zásobníkom. V C môže mať hlavný program veľa funkcií. Main () je volajúcou funkciou a funkcia, ktorá sa volá hlavným programom, je nazývaná funkcia. Keď je funkcia vyvolaná, je ovládaniu vyvolaná funkcia. Po dokončení vykonávania funkcie sa ovládací prvok vráti do hlavného režimu. Potom pokračuje hlavný program. Vytvorí sa tak aktivačný záznam alebo rám zásobníka, aby sa pokračovalo vo vykonávaní.

Obrázok 01: Rekurzia

Vo vyššie uvedenom programe, keď volá faktoriál (3) z hlavného, ​​vytvorí aktivačný záznam v zásobníku hovorov. Potom sa na vrch stohu atď. Vytvorí rámček faktoriálnych (2) stohov. Aktivačný záznam uchováva informácie o lokálnych premenných atď. Vždy, keď sa funkcia volá, vytvorí sa v hornej časti zásobníka nová sada lokálnych premenných. Tieto rámce zásobníkov môžu spomaliť zrýchlenie. Podobne ako pri rekurzii, funkcia sa volá sama. Časová zložitosť rekurzívnej funkcie sa zistí, koľkokrát sa funkcia volá. Časová náročnosť pre jedno volanie funkcie je O (1). Pre n počet rekurzívnych hovorov je časová zložitosť O (n).

Čo je iterácia?

Iterácia je blok inštrukcií, ktorý sa opakuje znovu a znovu, až kým nie je splnená daná podmienka. Iterácia sa dá dosiahnuť pomocou „for loop“, „do-while loop“ alebo „while loop“. Syntax „for loop“ je nasledovná.

pre (inicializácia; stav; úprava)

// Vyhlásenia;

Obrázok 02: „pre vývojový diagram slučky“

Inicializačný krok sa vykoná ako prvý. Tento krok má deklarovať a inicializovať riadiace premenné slučky. Ak je podmienka splnená, vykonajú sa výroky v zložených zátvorkách. Tieto výroky sa vykonávajú až do splnenia podmienky. Ak je podmienka nesprávna, ovládací prvok prejde na nasledujúci príkaz za „za slučkou“. Po vykonaní príkazov vo vnútri slučky, ovládací prvok prejde na úpravu sekcie. Je to aktualizácia premennej riadenia slučky. Potom sa stav znova skontroluje. Ak je podmienka splnená, vykonajú sa výroky v zložených zátvorkách. Týmto spôsobom sa iteruje „for loop“.

V „while loop“, príkazy vo vnútri slučky sa vykonávajú až do splnenia podmienky.

while (condition)

//Vyhlásenia

V slučke „do-while“, stav je skontrolovaný na konci slučky. Slučka sa teda vykoná aspoň raz.

robiť

//Vyhlásenia

kým (podmienka)

Program na nájdenie faktoriálu 3 (3!) Pomocou iterácie („pre slučku“) je nasledujúci.

int main ()

intn = 3, faktoriál = 1;

Inti;

pre (i = 1; i<=n ; i++)

faktoriál = faktoriál * i;

printf („Factorial is% d \ n“, factorial);

návrat 0;

Aké sú podobnosti medzi rekurziou a iteráciou?

• Obidva sú techniky riešenia problému.
• Úlohu možno vyriešiť buď rekurziou alebo iteráciou.

Aký je rozdiel medzi rekurziou a iteráciou?

Rekurzia vs. Iterácia
Rekurzia je spôsob vyvolania funkcie v rámci tej istej funkcie.	Iterácia je blok inštrukcií, ktorý sa opakuje dovtedy, kým nie je daná podmienka splnená.
Vesmírna zložitosť
Priestorová zložitosť rekurzívnych programov je vyššia ako iterácia.	Pri iteráciách je zložitosť vesmíru nižšia.
rýchlosť
Vykonanie rekurzie je pomalé.	Zvyčajne je iterácia rýchlejšia ako rekurzia.
podmienka
Ak nedôjde k ukončeniu, môže dôjsť k nekonečnej rekurzii.	Ak sa stav nikdy nestane nepravdivým, bude to nekonečná iterácia.
Stoh
V rekurzii sa zásobník používa na ukladanie miestnych premenných, keď sa volá funkcia.	V iterácii sa zásobník nepoužíva.
Čitateľnosť kódu
Rekurzívny program je čitateľnejší.	Iteračný program sa číta ťažšie ako rekurzívny program.

Zhrnutie - rekurzia vs Iterácia

Tento článok sa zaoberal rozdielom medzi rekurziou a iteráciou. Obidve sa dajú použiť na riešenie problémov s programovaním. Rozdiel medzi rekurziou a iteráciou spočíva v tom, že rekurzia je mechanizmus na vyvolanie funkcie v rámci tej istej funkcie a iterácia na opakované vykonávanie množiny inštrukcií, kým nie je daná podmienka splnená. Ak sa dá problém vyriešiť rekurzívnou formou, môže sa vyriešiť aj pomocou iterácií.

Stiahnite si verziu PDF rekurzie verzus iterácia

Môžete si stiahnuť verziu tohto článku vo formáte PDF a použiť ju na účely offline podľa citácie. Stiahnite si PDF verziu tu Rozdiel medzi rekurziou a iteráciou

referencie:

1.Point, Návody. „Základy opakovania štruktúr údajov a algoritmov.“, Príručky, 15. augusta 2017. K dispozícii tu 
2.nareshtechnologies. „Rekurzia vo funkciách C | Výukový program v jazyku C “YouTube, YouTube, 12. september 2016. K dispozícii tu  
3.yusuf shakeel. „Algoritmus rekurzie | Factorial - sprievodca krok za krokom “YouTube, YouTube, 14. októbra 2013. K dispozícii tu  

S láskavým dovolením:

1.'CPT-Rekurzia-Factorial-Code'By Pluke - Vlastné diela, (Public Domain), na Commons Wikimedia 
2. „Schéma pre opakované slučky“ Nie je k dispozícii žiadny strojovo čitateľný autor - predpokladá sa vlastná práca. (CC BY-SA 2.5) prostredníctvom Commons Wikimedia