Kľúčový rozdiel – rekurzia verzus iterácia
Rekurzia a iterácia môžu byť použité 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 v tom, že rekurzia je mechanizmus na volanie funkcie v rámci tej istej funkcie, zatiaľ čo iterácia spočíva v opakovanom vykonávaní súboru inštrukcií, kým nie je daná podmienka pravdivá. Rekurzia a iterácia sú hlavné techniky na vývoj algoritmov a vytváranie softvérových aplikácií.
Čo je rekurzia?
Keď funkcia volá samu seba v rámci funkcie, nazýva sa to 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;
Na výpočet faktoriálu 3(3!=321) použite kód uvedený nižšie.
intmain () {
int value=faktoriál (3);
printf(“Faktoriál je %d\n”, hodnota);
return 0;
}
intfactorial (intn) {
if(n==0) {
return 1;
}
else {
návrat n faktoriál(n-1);
}
}
Pri volaní faktoriálu (3) bude táto funkcia volať faktoriál (2). Pri volaní faktoriálu (2) bude táto funkcia volať faktoriál (1). Potom faktoriál (1) zavolá faktoriál (0). faktoriál (0) vráti 1. Vo vyššie uvedenom programe je základná podmienka n==0 v bloku „if“. 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í. Takže main () je volajúca funkcia a funkcia, ktorú volá hlavný program, je volaná funkcia. Keď je funkcia zavolaná, ovládanie je odovzdané volanej funkcii. Po dokončení vykonávania funkcie sa ovládací prvok vráti do hlavného. Potom pokračuje hlavný program. Takže vytvorí aktivačný záznam alebo zásobníkový rámec, aby mohol pokračovať vo vykonávaní.
Obrázok 01: Rekurzia
Vo vyššie uvedenom programe pri volaní faktoriálu (3) z main vytvorí aktivačný záznam v zásobníku hovorov. Potom sa na vrchu stohu vytvorí faktoriál (2) a tak ďalej. Aktivačný záznam uchováva informácie o lokálnych premenných atď. Pri každom volaní funkcie sa na vrchu zásobníka vytvorí nová sada lokálnych premenných. Tieto zásobníkové snímky môžu spomaliť rýchlosť. Podobne pri rekurzii funkcia volá samu seba. Časová zložitosť pre rekurzívnu funkciu sa zistí počtom volaní funkcie. Časová zložitosť 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 znova a znova opakuje, kým nie je daná podmienka pravdivá. Iteráciu je možné dosiahnuť pomocou „cyklus for“, „cyklus do-while“alebo „cyklus while“. Syntax „for loop“je nasledovná.
for (inicializácia; podmienka; úprava) {
// výpisy;
}
Obrázok 02: „pre vývojový diagram slučky“
Prvý sa vykoná krok inicializácie. Týmto krokom je deklarácia a inicializácia premenných riadenia slučky. Ak je podmienka pravdivá, vykonajú sa príkazy v zložených zátvorkách. Tieto príkazy sa vykonávajú, kým podmienka nie je pravdivá. Ak je podmienka nepravdivá, ovládací prvok prejde na ďalší príkaz po „cykle for“. Po vykonaní príkazov v slučke prejde ovládací prvok do sekcie úprav. Ide o aktualizáciu riadiacej premennej slučky. Potom sa znova skontroluje stav. Ak je podmienka pravdivá, vykonajú sa príkazy v zložených zátvorkách. Týmto spôsobom sa opakuje „cyklus for“.
V „cykle while“sa príkazy v rámci cyklu vykonávajú, kým nie je podmienka pravdivá.
počas (podmienka){
//statements
}
V slučke „do-while“sa podmienka kontroluje na konci cyklu. Cyklus sa teda vykoná aspoň raz.
do{
//statements
} while(condition)
Program na nájdenie faktoriálu 3 (3!) pomocou iterácie (“cyklus for”) je nasledujúci.
int main(){
intn=3, faktoriál=1;
inti;
for(i=1; i<=n; i++){
faktoriál=faktoriáli;
}
printf(“Faktoriál je %d\n”, faktoriál);
return 0;
}
Aké sú podobnosti medzi rekurziou a iteráciou?
- Obaja sú techniky na vyriešenie problému.
- Úlohu je možné vyriešiť rekurziou alebo iteráciou.
Aký je rozdiel medzi rekurziou a iteráciou?
Rekurzia verzus iterácia |
|
| Rekurzia je metóda volania funkcie v rámci tej istej funkcie. | Iterácia je blok inštrukcií, ktorý sa opakuje, kým nie je daná podmienka pravdivá. |
| Zložitosť priestoru | |
| Priestorová zložitosť rekurzívnych programov je vyššia ako pri iteráciách. | Vesmírna zložitosť je v iteráciách nižšia. |
| Speed | |
| Spustenie rekurzie je pomalé. | Normálne je iterácia rýchlejšia ako rekurzia. |
| Stav | |
| Ak neexistuje podmienka ukončenia, môže nastať nekonečná rekurzia. | Ak sa podmienka nikdy nestane nepravdivou, bude to nekonečná iterácia. |
| Stack | |
| Pri rekurzii sa zásobník používa na ukladanie lokálnych premenných pri volaní funkcie. | V iterácii sa zásobník nepoužíva. |
| Čitateľnosť kódu | |
| Rekurzívny program je čitateľnejší. | Iteračný program je ťažšie čitateľný ako rekurzívny program. |
Zhrnutie – Rekurzia verzus iterácia
Tento článok diskutoval o rozdieloch medzi rekurziou a iteráciou. Obe môžu byť použité na riešenie problémov s programovaním. Rozdiel medzi rekurziou a iteráciou je v tom, že rekurzia je mechanizmus na volanie funkcie v rámci tej istej funkcie a jej opakovanie na vykonanie množiny inštrukcií opakovane, kým nie je daná podmienka pravdivá. Ak sa dá problém vyriešiť v rekurzívnej forme, dá sa vyriešiť aj pomocou iterácií.
Stiahnite si verziu PDF Rekurzia vs Iterácia
Verziu tohto článku si môžete stiahnuť vo formáte PDF a použiť ju na offline účely podľa citácie. Stiahnite si PDF verziu tu Rozdiel medzi rekurziou a iteráciou
