Klíčový rozdíl – rekurze vs iterace
Rekurze a iterace 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 v tom, že rekurze je mechanismus pro volání funkce v rámci stejné funkce, zatímco iterace má opakovaně provádět sadu instrukcí, dokud není daná podmínka pravdivá. Rekurze a iterace jsou hlavní techniky pro vývoj algoritmů a vytváření softwarových aplikací.
Co je rekurze?
Když funkce volá sama sebe v rámci funkce, nazývá se to rekurze. Existují dva typy rekurze. Jsou to konečná rekurze a nekonečná rekurze. Konečná rekurze má ukončovací podmínku. 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;
Podle níže uvedeného kódu vypočítejte faktoriál 3(3!=321).
intmain () {
int value=faktoriál (3);
printf(“Faktorial je %d\n”, hodnota);
return 0;
}
intfactorial (intn) {
if(n==0) {
return 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ínka n==0 v bloku „if“základní podmínkou. Podle Podobně se faktoriál volá znovu a znovu.
Rekurzivní funkce souvisí se zásobníkem. V C může mít hlavní program mnoho funkcí. Takže main () je volající funkce a funkce, která je volána hlavním programem, je volaná funkce. Když je funkce volána, řízení je předáno volané funkci. Po dokončení provádění funkce se ovládací prvek vrátí do hlavního. Poté pokračuje hlavní program. Vytvoří tedy aktivační záznam nebo zásobníkový rámec pro pokračování v provádění.
Obrázek 01: Rekurze
Ve výše uvedeném programu při volání faktoriálu (3) z main vytvoří aktivační záznam v zásobníku volání. Poté se na vrcholu stohu vytvoří faktoriál (2) a tak dále. Aktivační záznam uchovává informace o lokálních proměnných atd. Při každém volání funkce se na vrcholu zásobníku vytvoří nová sada lokálních proměnných. Tyto zásobníkové snímky mohou zpomalit rychlost. Podobně v rekurzi volá funkce sama sebe. Časová složitost rekurzivní funkce se zjistí počtem volání funkce. Časová složitost 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 znovu a znovu opakuje, dokud není daná podmínka splněna. Iteraci lze provést pomocí „cyklu for“, „smyčky do-while“nebo „smyčky while“. Syntaxe „for loop“je následující.
for (inicializace; podmínka; úprava) {
// výpisy;
}
Obrázek 02: „pro vývojový diagram smyčky“
První se provede inicializační krok. Tímto krokem je deklarace a inicializace proměnných řízení smyčky. Pokud je podmínka pravdivá, provedou se příkazy ve složených závorkách. Tyto příkazy se provádějí, dokud není podmínka pravdivá. Pokud je podmínka nepravdivá, ovládací prvek přejde na další příkaz za „cyklem for“. Po provedení příkazů uvnitř smyčky přejde ovládací prvek do sekce úprav. Jde o aktualizaci řídicí proměnné smyčky. Poté se stav znovu zkontroluje. Pokud je podmínka pravdivá, provedou se příkazy ve složených závorkách. Tímto způsobem se opakuje „cyklus for“.
V „smyčce while“se příkazy uvnitř cyklu provádějí, dokud není podmínka pravdivá.
zatímco (podmínka){
//výpisy
}
V cyklu „do-while“se podmínka kontroluje na konci cyklu. Smyčka se tedy provede alespoň jednou.
dělat{
//výpisy
} while(condition)
Program pro nalezení faktoriálu 3 (3!) pomocí iterace („cyklus for“) je následující.
int main(){
intn=3, faktoriál=1;
inti;
for(i=1; i<=n; i++){
faktoriální=faktoriáli;
}
printf(“Faktoriál je %d\n”, faktoriál);
return 0;
}
Jaké jsou podobnosti mezi rekurzí a iterací?
- Oba jsou techniky k vyřešení problému.
- Úkol lze vyřešit rekurzí nebo iterací.
Jaký je rozdíl mezi rekurzí a iterací?
Rekurze vs iterace |
|
| Rekurze je metoda volání funkce v rámci stejné funkce. | Iterace je blok instrukcí, který se opakuje, dokud není daná podmínka splněna. |
| Složitost prostoru | |
| Prostorová složitost rekurzivních programů je vyšší než u iterací. | Složitost prostoru je v iteracích nižší. |
| Speed | |
| Provádění rekurze je pomalé. | Normálně je iterace rychlejší než rekurze. |
| Stav | |
| Pokud neexistuje žádná podmínka ukončení, může nastat nekonečná rekurze. | Pokud se podmínka nikdy nestane nepravdivou, bude to nekonečná iterace. |
| Stack | |
| V rekurzi se zásobník používá k ukládání lokálních proměnných, když je funkce volána. | V iteraci se zásobník nepoužívá. |
| Čitelnost kódu | |
| Rekurzivní program je čitelnější. | Iterativní program je hůře čitelný než rekurzivní program. |
Shrnutí – rekurze vs iterace
Tento článek pojednával o rozdílu mezi rekurzí a iterací. Oba mohou být použity k řešení problémů s programováním. Rozdíl mezi rekurzí a iterací je v tom, že rekurze je mechanismus pro volání funkce v rámci stejné funkce a její opakování, aby se opakovaně provedla sada instrukcí, dokud není daná podmínka pravdivá. Pokud lze problém vyřešit v rekurzivní formě, lze jej vyřešit také pomocí iterací.
Stáhněte si PDF verzi rekurze vs iterace
Můžete si stáhnout PDF verzi tohoto článku a použít ji pro offline účely podle citace. Stáhněte si PDF verzi zde Rozdíl mezi rekurzí a iterací
