Rozdíl mezi rekurzí a iterací

Klíčový rozdíl - rekurze vs Iterace
 

Rekurzi a iteraci lze použít k řešení problémů s programováním. Přístup k řešení problému pomocí rekurze nebo iterace závisí na způsobu řešení problému. klíčový rozdíl mezi rekurzí a iterací je to rekurze je mechanismus pro vyvolání funkce v rámci stejné funkce, zatímco iterace má provádět řadu instrukcí opakovaně, dokud není daná podmínka splněna. Rekurze a iterace jsou hlavní techniky pro vývoj algoritmů a vytváření softwarových aplikací.

OBSAH

1. Přehled a klíčový rozdíl
2. Co je rekurze
3. Co je iterace
4. Podobnosti mezi rekurzí a iterací
5. Porovnání bok po boku - rekurze vs. itrace v tabulkové formě
6. Shrnutí

Co je rekurze?

Když funkce volá sebe uvnitř funkce, to je známé jako rekurze. Existují dva typy rekurze. Jsou to konečná rekurze a nekonečná rekurze. Konečná rekurze má ukončovací stav. Nekonečná rekurze nemá ukončovací podmínku.

Rekurzi lze vysvětlit pomocí programu pro výpočet faktoriálů.

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

n! = 1, pokud n = 0;

Níže uvedený kód vypočítá faktoriál 3 (3! = 3 * 2 * 1).

intmain ()

int hodnota = faktoriál (3);

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

návrat 0;

intfactorial (intn)

if (n == 0)

návrat 1;

jinde

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

Při volání faktoriálu (3) tato funkce vyvolá faktoriál (2). Při volání faktoriálu (2) tato funkce vyvolá faktoriál (1). Pak faktoriál (1) zavolá faktoriál (0). faktoriál (0) se vrátí 1. Ve výše uvedeném programu je podmínkou n == 0 v „if block“ základní podmínka. Podle obdobně je faktorová funkce volána znovu a znovu.

Rekurzivní funkce jsou spojeny se zásobníkem. V C může mít hlavní program mnoho funkcí. Main () je volající funkce a funkce, která je vyvolána hlavním programem, je volaná funkce. Když je funkce volána, ovládání je dáno volané funkci. Po dokončení provádění funkce se ovládací prvek vrátí do hlavního režimu. Pak pokračuje hlavní program. Vytvoří tak aktivační záznam nebo rámeček zásobníku, aby pokračovalo ve provádění.

Obrázek 01: Rekurze

Ve výše uvedeném programu, když volá faktoriál (3) z hlavního, vytvoří aktivační záznam v zásobníku volání. Poté se nahoře na hromádce atd. Vytvoří rámeček faktoriálního (2) zásobníku. Aktivační záznam uchovává informace o lokálních proměnných atd. Při každém vyvolání funkce se v horní části zásobníku vytvoří nová sada lokálních proměnných. Tyto rámečky zásobníku mohou zpomalit zrychlení. Stejně jako v rekurzi se funkce nazývá sama. Časová složitost rekurzivní funkce se zjistí podle toho, kolikrát je funkce vyvolána. Časová složitost jednoho volání funkce je O (1). Pro n počet rekurzivních hovorů je časová složitost O (n).

Co je to Iterace?

Iterace je blok pokynů, který se opakuje znovu a znovu, dokud není daná podmínka splněna. Iteraci lze dosáhnout pomocí „for loop“, „do-while loop“ nebo „while loop“. Syntaxe „for loop“ je následující.

pro (inicializace; stav; úprava)

// prohlášení;

Obrázek 02: „pro vývojový diagram smyčky“

Inicializační krok se provede jako první. Tento krok je deklarovat a inicializovat řídicí proměnné smyčky. Pokud je podmínka pravdivá, provedou se příkazy uvnitř složených závorek. Tyto příkazy se provádějí, dokud není podmínka splněna. Pokud je podmínka nepravdivá, přejde ovládací prvek k dalšímu příkazu za „for loop“. Po provedení příkazů uvnitř smyčky ovládací prvek přejde do sekce úprav. Jedná se o aktualizaci řídicí proměnné smyčky. Poté je stav znovu zkontrolován. Pokud je podmínka pravdivá, provedou se příkazy uvnitř složených závorek. Tímto způsobem se iteruje „for loop“.

V „while loop“, příkazy uvnitř smyčky se provádějí, dokud není podmínka splněna.

while (podmínka)

// příkazy

Ve smyčce „do-while“, stav je zkontrolován na konci smyčky. Smyčka se tedy provede alespoň jednou.

dělat

// příkazy

while (podmínka)

Program pro nalezení faktoriálu 3 (3!) Pomocí iterace („pro smyčku“) je následující.

int main ()

intn = 3, faktoriál = 1;

inti;

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

faktoriál = faktoriál * i;

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

návrat 0;

Jaké jsou podobnosti mezi rekurzí a iterací?

• Oba jsou techniky řešení problému.
• Úkol může být vyřešen buď rekurzí, nebo iterací.

Jaký je rozdíl mezi rekurzí a iterací?

Rekurze vs. itrace
Rekurze je metoda vyvolání funkce v rámci stejné funkce.	Iterace je blok pokynů, který se opakuje, dokud není daná podmínka splněna.
Vesmírná složitost
Složitost prostoru rekurzivních programů je vyšší než iterace.	Složitost prostoru je v iteracích nižší.
Rychlost
Realizace rekurze je pomalá.	Obvykle je iterace rychlejší než rekurze.
Stav
Pokud není podmínka ukončení, může dojít k nekonečné rekurzi.	Pokud se stav nikdy nestane falešným, bude to nekonečná iterace.
Zásobník
V rekurzi se zásobník používá k ukládání lokálních proměnných při vyvolání funkce.	V iteraci se zásobník nepoužívá.
Čitelnost kódu
Rekurzivní program je čitelnější.	Iterativní program je těžší číst než rekurzivní program.

Shrnutí - Rekurze vs Iterace

Tento článek pojednává o rozdílu mezi rekurzí a iterací. Oba lze použít k řešení problémů s programováním. Rozdíl mezi rekurzí a iterací spočívá v tom, že rekurze je mechanismus pro vyvolání funkce v rámci stejné funkce a iterace pro opakované provádění sady pokynů, dokud není daná podmínka splněna. Pokud lze problém vyřešit rekurzivní formou, lze jej také vyřešit pomocí iterací.

Stáhněte si verzi PDF rekurze versus iterace

Můžete si stáhnout PDF verzi tohoto článku a použít ji pro účely offline podle citace. Stáhněte si PDF verzi zde Rozdíl mezi rekurzí a iterací

Odkaz:

1.Point, Návody. „Základy opakování datových struktur a algoritmů.“, Cvičení, 15. srpna 2017. K dispozici zde 
2.nareshtechnologie. „Rekurze ve funkcích C | Výukový program v jazyce C ”YouTube, YouTube, 12. září 2016. K dispozici zde  
3.yusuf shakeel. „Algoritmus rekurze | Factorial - průvodce krok za krokem “YouTube, YouTube, 14. října 2013. K dispozici zde  

Obrázek se svolením:

1.'CPT-Recursion-Factorial-Code'By Pluke - Vlastní práce, (Public Domain), prostřednictvím Commons Wikimedia 
2.'For-loop-diagram'By Nebyl poskytnut žádný strojově čitelný autor - předpokládá se vlastní práce. (CC BY-SA 2.5) prostřednictvím Commons Wikimedia