Rekurzia: Rozdiel medzi revíziami

Z Kiwiki
Skočit na navigaci Skočit na vyhledávání
(Vytvorená stránka „'''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 v…“)
 
Riadok 1: Riadok 1:
−
'''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 samej seba.
+
'''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.
 +
 
 +
=Rekuzia - definície, princípy=
 +
==Rekurzia v grafike==
 +
Najjednoduchsim prikladom rekuzie, ktorý sa dá zobraziť je dať 2 zrkadlá oproti sebe. Ď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á. Rekurzia sa občas objaví i na obaloch potravín (pozri obrázok).
 +
<gallery>
 +
Image:recursionMirror.jpg|Rekurzívny obraz v zrkadlách
 +
Image:recursionLogMeIn.jpg|Rekurzívny obraz ´vzdialenej´ pracovnej plochy
 +
Image:recursionCacao.jpg|Rekurzívny obal kakaa
 +
</gallery>
 +
 
 +
==Rekurzia v matematike==
 +
==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.
 +
<source lang="c">
 +
void vypis(int n) {
 +
cout<<n;
 +
if(n>0)
 +
  vypis(--n);
 +
}
 +
</source>
  
−
=Formálna definícia rekurzie=
 
 
Na začiatok uvedieme niekoľko prípadov rekurzívnej definície funkcie:
 
Na začiatok uvedieme niekoľko prípadov rekurzívnej definície funkcie:

Verzia zo dňa a času 14:01, 31. december 2009

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.

Rekuzia - definície, princípy

Rekurzia v grafike

Najjednoduchsim prikladom rekuzie, ktorý sa dá zobraziť je dať 2 zrkadlá oproti sebe. Ď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á. Rekurzia sa občas objaví i na obaloch potravín (pozri obrázok).

  • Rekurzívny obraz v zrkadlách

  • Rekurzívny obraz ´vzdialenej´ pracovnej plochy

  • Rekurzívny obal kakaa

Rekurzia v matematike

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); 
}

Na začiatok uvedieme niekoľko prípadov rekurzívnej definície funkcie:

Zdroj: „http://www.kiwiki.info/index.php?title=Rekurzia&oldid=489“