Rekurzia: Rozdiel medzi revíziami
d |
|||
| Riadok 46: | Riadok 46: | ||
;Doterajšie riešenie:Funkcia, ktorý vypíše len jedno číslo (n) | ;Doterajšie riešenie:Funkcia, ktorý vypíše len jedno číslo (n) | ||
void vypis(int n) { cout<<n; } | void vypis(int n) { cout<<n; } | ||
| − | ;Doplnenie rekurzie | + | ;Doplnenie rekurzie:Vo funkcii ''vypis'' pridam volanie funkcie vypis, ktorá má parameter n o 1 menší |
void vypis(int n) { cout<<n; vypis(--n); } | void vypis(int n) { cout<<n; vypis(--n); } | ||
;Analýza riešenia;Vyrobili sme deadlock, čiže uviaznutie programu. Funckia vypis sa nikdy neukonci, bude sa volať do nekonečna (resp. dotiaľ, dokiaľ bude mať program dostatok pamäti. Potom spadne). | ;Analýza riešenia;Vyrobili sme deadlock, čiže uviaznutie programu. Funckia vypis sa nikdy neukonci, bude sa volať do nekonečna (resp. dotiaľ, dokiaľ bude mať program dostatok pamäti. Potom spadne). | ||
| Riadok 57: | Riadok 57: | ||
} | } | ||
</source> | </source> | ||
| − | |||
| − | |||
=Odkazy= | =Odkazy= | ||
<references/> | <references/> | ||
Verzia zo dňa a času 10:04, 1. január 2010
Rekurzia (po latinsky: recurrere = bežať naspäť) je matematike a informatike využitie časti vlastnej vnútornej štruktúry. V definícii funkcie sa nachádza volanie samotnej funkcie. Inak povedané, funkcia volá samú seba.
Obsah
Rekuzia - definície, princípy
Rekurzia v grafike
Najjednoduchsim prikladom rekuzie, ktorý sa dá zobraziť je dať 2 zrkadlá oproti sebe (Obr. 1). Ďalším príkladom môže byť spustenie programu vzdialená pracovná plocha, kde adresa vzdialeného počítača bude ten počítač, na ktorom bola aplikácia spustená (Obr. 2). Rekurzia sa občas objaví i na obaloch potravín (Obr. 3).
Obr. 1 Rekurzívny obraz v zrkadlách
Obr. 2 Rekurzívny obraz ´vzdialenej´ pracovnej plochy
Obr. 3 Rekurzívny obal kakaa
Rekurzia v názvoch vecí
Pracujeme z názvami a skratkami, ktoré sú už také zaužívané, že ani nerozmýšľame čo znamenajú. Čo znamenajú skratky GNU, wine (program v linuxe, nie víno), PNG, LAME (mp3 enkodér), PHP, YAML, VISA ....
- PNG - Oficiálne "Portable Network Graphics", Neoficiálne "PNG is Not Gif"
- LAME - LAME Ain't an MP3 Encoder
- Wine -Wine Is Not an Emulator
- PHP - PHP: Hypertext Preprocessor
- YAML - YAML Ain't Markup Language
- VISA - Visa International Service Association
- GNU - GNU's Not Unix
- Slovná definícia pojmu Rekurzia
- pozri Rekurzia
Zoznam viacerých skratiek je v anglickej verzii wikipédie [1].
Rekurzia v matematike
- Prirodzené čísla
- Faktoriál
- Fibonnaciho fonkcia
- Katalánske čísla
- Hanoiské veže
Rekurzia v informatike
Princíp fungovania rekurzívnych funkcií:
- Zložitý problém môžeme riešiť rekurzívnym spôsobom tak, že:
- Daný problém rozložíme na elementárne podproblémy, ktoré dokážeme jednoducho vyriešiiť.
- Tieto podproblémy musia byť rovnakého typu.
- Riešenie spočíva v opakovanom (rep. rekurzívnom) vykonávaní funkcie riešiacej daný problém.
- Dôležitou bodom je určiť podmienku, kedy sa ukončí riešenie úlohy.
Príklad: Vypíšte za sebou čísla od n do 0. Nech n=5
- Zložitý´ problém
- vypísať dané čísla: (Dajme tomu, že nepoznám cykly)
- Rozloženie problému na elementárne podproblémy
- vypíšem len jedno číslo (to viem)
- Podmienka ukončenia výpisu
- Prestanem keď vypíšem posledné číslo - 0
- Doterajšie riešenie
- Funkcia, ktorý vypíše len jedno číslo (n)
void vypis(int n) { cout<<n; }
- Doplnenie rekurzie
- Vo funkcii vypis pridam volanie funkcie vypis, ktorá má parameter n o 1 menší
void vypis(int n) { cout<<n; vypis(--n); }
- Analýza riešenia;Vyrobili sme deadlock, čiže uviaznutie programu. Funckia vypis sa nikdy neukonci, bude sa volať do nekonečna (resp. dotiaľ, dokiaľ bude mať program dostatok pamäti. Potom spadne).
- Doplnenie ukončujúcej podmienky
- Vypisovanie ukončím pri výpise 1.
void vypis(int n) {
cout<<n;
if(n>0)
vypis(--n);
}
