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ým rozdílem mezi rekurzí a iterací je, že rekurze je mechanismus k volání funkce v rámci stejné funkce, zatímco iterace spočívá v opakovaném provádění sady instrukcí, dokud není daná podmínka pravdivá. 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í vedle sebe - rekurze vs. iterace v tabulkové formě
6. Shrnutí
Co je rekurze?
Když se funkce v rámci funkce volá, je známá jako Rekurze. Existují dva typy rekurze. Jsou to konečná rekurze a nekonečná rekurze. Konečná rekurze má podmínku ukončení. Nekonečná rekurze nemá podmínku ukončení.
Rekurzi lze vysvětlit pomocí programu pro výpočet faktoriálů.
n! = n * (n-1) !, pokud n> 0
n! = 1, pokud n = 0;
Pro výpočet faktoriálu 3 (3! = 3 * 2 * 1) použijte níže uvedený kód.
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);
}
}
Při volání faktoriálu (3) bude tato funkce volat faktoriál (2). Při volání faktoriálu (2) bude tato funkce volat faktoriál (1). Potom faktoriál (1) zavolá faktoriál (0). faktoriál (0) vrátí 1. Ve výše uvedeném programu je podmínkou n == 0 v bloku „if“základní podmínka. Podle Podobně je faktoriální funkce volána znovu a znovu.
Rekurzivní funkce souvisí se zásobníkem. V jazyce C může mít hlavní program mnoho funkcí. Main () je tedy volací funkce a funkce, která je volána hlavním programem, je volaná funkce. Když je funkce volána, je dána kontrola volané funkci. Po dokončení provádění funkce se ovládací prvek vrátí do main. Poté hlavní program pokračuje. Vytvoří tedy aktivační záznam nebo rámec zásobníku, aby mohl pokračovat v provádění.
Obrázek 01: Rekurze
Ve výše uvedeném programu při volání faktoriálu (3) z main vytvoří záznam aktivace v zásobníku volání. Poté se na vrcholu zásobníku vytvoří faktoriální (2) rám zásobníku atd. Aktivační záznam uchovává informace o lokálních proměnných atd. Při každém volání funkce se v horní části zásobníku vytvoří nová sada lokálních proměnných. Tyto rámce zásobníku mohou zpomalit rychlost. Podobně v rekurzi se funkce sama volá. Časovou složitost rekurzivní funkce zjistíme podle počtu volání funkce. Složitost času pro jedno volání funkce je O (1). Pro n počet rekurzivních volání je časová složitost O (n).
Co je iterace?
Iterace je blok instrukcí, které se opakují znovu a znovu, dokud není daná podmínka pravdivá. Iterace lze dosáhnout pomocí „smyčky for“, „smyčky do-while“nebo „while“. Syntaxe „pro smyčku“je následující.
pro (inicializace; podmínka; upravit) {
// příkazy;
}
Obrázek 02: „pro vývojový diagram smyčky“
Nejprve se provede krok inicializace. Tento krok je deklarovat a inicializovat proměnné řízení smyčky. Pokud je podmínka pravdivá, příkazy uvnitř složených závorek se provedou. Tyto příkazy se provádějí, dokud není podmínka pravdivá. Pokud je podmínka nepravdivá, přejde ovládací prvek na další příkaz za smyčkou „for“. Po provedení příkazů uvnitř smyčky přejde ovládací prvek do sekce. Jde o aktualizaci proměnné řízení 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 iteruje smyčka „pro“.
V „smyčce while“se příkazy uvnitř smyčky provádějí, dokud není podmínka pravdivá.
while (podmínka) {
// příkazy
}
Ve smyčce „do-while“se stav kontroluje na konci smyčky. Smyčka se tedy provede alespoň jednou.
dělat{
// příkazy
} while (podmínka)
Program vyhledání 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 („Faktoriál je% d / n“, faktoriál);
návrat 0;
}
Jaké jsou podobnosti mezi rekurzí a iterací?
- Obě jsou techniky řešení problému.
- Úkol lze vyřešit buď rekurzí nebo iterací.
Jaký je rozdíl mezi rekurzí a iterací?
Rozdílný článek uprostřed před tabulkou
Rekurze vs iterace |
|
| Rekurze je metoda volání funkce v rámci stejné funkce. | Iterace je blok instrukcí, které se opakují, dokud není daná podmínka pravdivá. |
| Složitost vesmíru | |
| Složitost prostoru rekurzivních programů je vyšší než iterace. | Složitost prostoru je v iteracích nižší. |
| Rychlost | |
| Provádění rekurze je pomalé. | Normálně je iterace rychlejší než rekurze. |
| Stav | |
| Pokud neexistuje podmínka ukončení, může dojít k nekonečné rekurzi. | Pokud se podmínka nikdy nestane nepravdivou, bude to nekonečná iterace. |
| Zásobník | |
| Při rekurzi se zásobník používá k ukládání místních proměnných, když se funkce volá. | 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ával 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 k volání funkce v rámci stejné funkce a iterace k opakovanému provádění sady pokynů, dokud není daná podmínka pravdivá. Pokud lze problém vyřešit rekurzivní formou, lze jej vyřešit také pomocí iterací.
Stáhněte si PDF verzi Rekurze vs Iterace
Můžete si stáhnout verzi tohoto článku ve formátu PDF a použít jej pro offline účely podle citace. Stáhněte si zde PDF verzi. Rozdíl mezi rekurzí a iterací
