Kľúčový rozdiel - rekurzia vs iterácia
Na riešenie problémov s programovaním je možné použiť rekurziu a iteráciu. Prístup k riešeniu problému pomocou rekurzie alebo iterácie závisí od spôsobu riešenia problému. Kľúčovým rozdielom medzi rekurziou a iteráciou je, že rekurzia je mechanizmus na vyvolanie funkcie v rámci tej istej funkcie, zatiaľ čo pri iterácii ide o opakované vykonávanie sady pokynov, kým nie je splnená daná podmienka. Rekurzia a iterácia sú hlavné techniky na vývoj algoritmov a tvorbu 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 vs iterácia v tabuľkovej forme
6. Zhrnutie
Čo je to rekurzia?
Keď sa funkcia v rámci funkcie nazýva, je známa ako rekurzia. Existujú dva typy rekurzie. Sú to konečná rekurzia a nekonečná rekurzia. Konečná rekurzia má konečnú podmienku. Nekonečná rekurzia nemá konečnú podmienku.
Rekurziu je možné vysvetliť pomocou programu na výpočet faktoriálov.
n! = n * (n-1) !, ak n> 0
n! = 1, ak n = 0;
Podľa nižšie uvedeného kódu vypočítajte faktoriál 3 (3! = 3 * 2 * 1).
intmain () {
int hodnota = faktoriál (3);
printf („Faktoriál je% d / n“, hodnota);
návrat 0;
}
intfactorial (intn) {
if (n == 0) {
návrat 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 bude faktoriál (1) nazývaný faktoriál (0). faktoriál (0) vráti 1. Vo vyššie uvedenom programe je podmienkou n == 0 podmienka „ak blok“základná podmienka. Podľa Podobne sa faktoriálna funkcia volá znova a znova.
Rekurzívne funkcie súvisia so zásobníkom. V jazyku C môže mať hlavný program mnoho funkcií. Main () je teda volacia funkcia a funkcia, ktorá je volaná hlavným programom, je volaná funkcia. Keď je funkcia volaná, je daná kontrola volanej funkcii. Po dokončení vykonávania funkcie sa ovládací prvok vráti do main. Potom pokračuje hlavný program. Takže vytvorí záznam o aktivácii alebo rámec zásobníka, aby mohol pokračovať v vykonávaní.
Obrázok 01: Rekurzia
Vo vyššie uvedenom programe pri volaní faktoriálu (3) z mainu sa vytvorí aktivačný záznam v zásobníku hovorov. Potom sa vytvorí faktoriálny (2) rám stohu na vrchu stohu a tak ďalej. Záznam o aktivácii uchováva informácie o miestnych premenných atď. Zakaždým, keď sa volá funkcia, v hornej časti zásobníka sa vytvorí nová sada miestnych premenných. Tieto stohové rámce môžu spomaliť rýchlosť. Rovnako tak pri rekurzii sa funkcia nazýva sama. Časovú zložitosť rekurzívnej funkcie zistíme počtom opakovaní funkcie. Časová zložitosť pre jedno volanie funkcie je O (1). Pre n počet rekurzívnych volaní je časová zložitosť O (n).
Čo je iterácia?
Iterácia je blok pokynov, ktoré sa opakujú znova a znova, kým nie je splnená daná podmienka. Iteráciu je možné dosiahnuť pomocou príkazov „for loop“, „do-while loop“alebo „while loop“. Syntax „pre slučku“je nasledovná.
pre (inicializácia; podmienka; upraviť) {
// Vyhlásenia;
}
Obrázok 02: „pre postupový diagram slučky“
Najskôr 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 vo vnútri zložených zátvoriek. Tieto príkazy sa vykonávajú, kým nie je splnená podmienka. Ak je podmienka nepravdivá, ovládací prvok prejde na ďalší príkaz po „cykle for“. Po vykonaní príkazov vo vnútri cyklu prejde ovládací prvok na úpravu sekcie. Má aktualizovať riadiacu premennú slučky. Potom sa stav znova skontroluje. Ak je podmienka pravdivá, vykonajú sa príkazy vo vnútri zložených zátvoriek. Týmto spôsobom iteruje cyklus „for“.
V cykle „while“sa príkazy vo vnútri cyklu vykonávajú, kým nie je splnená podmienka.
while (podmienka) {
//Vyhlásenia
}
V slučke „do-while“sa stav kontroluje na konci slučky. Smyčka sa teda vykoná aspoň raz.
robiť {
//Vyhlásenia
} while (podmienka)
Program na vyhľadanie faktoriálu 3 (3!) Pomocou iterácie („pre cyklus“) je nasledovný.
int main () {
intn = 3, faktoriál = 1;
inti;
pre (i = 1; i <= n; i ++) {
faktoriál = faktoriál * i;
}
printf („Faktoriál je% d / n“, faktoriál);
návrat 0;
}
Aké sú podobnosti medzi rekurziou a iteráciou?
- Obe sú techniky riešenia problému.
- Úlohu je možné vyriešiť buď rekurziou alebo iteráciou.
Aký je rozdiel medzi rekurziou a iteráciou?
Rozdielny článok v strede pred tabuľkou
Rekurzia vs iterácia |
|
| Rekurzia je metóda volania funkcie v rámci tej istej funkcie. | Iterácia je blok pokynov, ktoré sa opakujú, kým nie je splnená daná podmienka. |
| Zložitosť vesmíru | |
| Priestorová zložitosť rekurzívnych programov je vyššia ako pri iteráciách. | Zložitosť priestoru je v iteráciách nižšia. |
| Rýchlosť | |
| Vykonávanie rekurzie je pomalé. | Normálne je iterácia rýchlejšia ako rekurzia. |
| Stav | |
| Ak neexistuje podmienka ukončenia, môže dôjsť k nekonečnej rekurzii. | Ak sa podmienka nikdy nestane nepravdivou, bude to nekonečná iterácia. |
| Stoh | |
| Pri rekurzii sa zásobník používa na ukladanie lokálnych 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ší. | Iteratívny program sa číta ťažšie ako rekurzívny program. |
Zhrnutie - rekurzia vs iterácia
Tento článok pojednával o rozdieloch medzi rekurziou a iteráciou. Oba je možné 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 jej iterácia na opakované vykonávanie sady pokynov, kým nie je splnená daná podmienka. Ak sa dá problém vyriešiť rekurzívnou formou, dá sa vyriešiť aj pomocou iterácií.
Stiahnite si PDF verziu rekurzie vs iterácie
Môžete si stiahnuť verziu tohto článku vo formáte PDF a použiť ho na offline účely podľa citačnej poznámky. Tu si stiahnite verziu PDF. Rozdiel medzi rekurziou a iteráciou
