Rekurzia: Rozdiel medzi revíziami

Z Kiwiki
Skočit na navigaci Skočit na vyhledávání
d
Riadok 37: Riadok 37:
 
* Číslo 2 je najmenšie prvačíslo.
 
* Číslo 2 je najmenšie prvačíslo.
 
* Prvočíslo je každé celé kladné číslo, ktoré nie je deliteľné žiadnym iným menším prvočíslom ako je toto číslo samotné.
 
* Prvočíslo je každé celé kladné číslo, ktoré nie je deliteľné žiadnym iným menším prvočíslom ako je toto číslo samotné.
−
 
−
'''Faktoriál'''
 
−
 
−
*0!=1
 
−
*n!=n*(n-1)!
 
−
 
−
'''Fibonnaciho funkcia'''
 
−
*Fib(0)=0
 
−
*Fib(1)=1
 
−
*Fib(i)=Fib(i-1)+Fib(i-2), pre i>1
 
  
 
'''Katalánske čísla'''
 
'''Katalánske čísla'''
Riadok 64: Riadok 54:
 
\end{cases}
 
\end{cases}
 
</math>
 
</math>
−
 
 
Už pre malé hodnoty m a n dosahuje veľkých hodnôt. Napríklad A(4,2) je celé číslo, ktoré má 19 729 cifier.
 
Už pre malé hodnoty m a n dosahuje veľkých hodnôt. Napríklad A(4,2) je celé číslo, ktoré má 19 729 cifier.
  
Riadok 92: Riadok 81:
 
}  
 
}  
 
</source>
 
</source>
 +
 +
 +
=Ukážky rekurzívne definovaných funkcií=
 +
==Faktoriál==
 +
'''Definícia:'''
 +
 +
*0!=1
 +
*n!=n*(n-1)!
 +
 +
Pri tvorbe funkcie pre výpočet faktoriálu budeme postupovať presne podľa rekurzívnej definície:
 +
<source lang="c">
 +
long faktorial(int n) {
 +
if(n==0) return 1; // 0!=1
 +
return n*faktorial(n-1); // n!=n*(n-1)!
 +
}
 +
</source>
 +
 +
==Fibonacciho postupnosť==
 +
 +
'''Definícia:'''
 +
 +
*Fib(0)=0
 +
*Fib(1)=1
 +
*Fib(i)=Fib(i-1)+Fib(i-2), pre i>1
 +
 +
Rovnako aj tu budeme postupovať presne podľa rekurzívnej definície:
 +
<source lang="c">
 +
long fibonacci(int n) {
 +
if(n<2) return n; // fib(0)=0, fib(1)=1
 +
return fibonacci(n-1)+fibonacci(n-2); // fib(n)=fib(n-1)+fib(n-2)
 +
}
 +
</source>
 +
 +
==Najväčší spoločný deliteľ==
 +
Najväčší spoločný deliteľ <ref>Výpočet NSD - http://sputsoft.com/2009/10/computing-the-greatest-common-divisor/</ref>, <ref>NSD - definícia http://en.wikipedia.org/wiki/Greatest_common_divisor</ref> dvoch celých čísel m,n rieši Euklidov algoritmus. Jeho najjednoduchšia forma sa dá popísať nasledovne:
 +
# vstupné hodnoty: m, n
 +
# Ak je m=n, tak koniec (krok 6)
 +
# ak je m>n, tak m=m-n
 +
# ak je n>m, tak n=n-m
 +
# skok na krok 2
 +
# NSD(m,n)=m (keďze m a n sú rovanké je jedno, ktorú premennú budeme považovať za výsledok)
 +
 +
NSD vieme definovať aj rekurzívne:
 +
*<math>NSD(m,0)=\ m</math>
 +
*<math>NSD(m,n)=NSD(n,m\ \mbox{mod }n)</math>
 +
 +
V jazyku C to môžeme zapísať nasledovne:
 +
 +
<source lang="c">
 +
long nsd(int m, int n) {
 +
if(n==0) return m;
 +
return nsd(n,m%n);
 +
}
 +
</source>
 +
 +
==Hanoiské veže==
 +
...
  
 
=Odkazy=
 
=Odkazy=
 
<references/>
 
<references/>

Verzia zo dňa a času 22:52, 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.

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

Prirodzené čísla definujme nasledovne:

  • 0 patrí do množiny [math]\mathbb{N}[/math]
  • ak patrí n do množiny [math]\mathbb{N}[/math], potom n + 1 patrí tiež do množiny [math]\mathbb{N}[/math]

Množina prirodzených čísel je taká najmenšia množina reálnych čísel, ktorá spĺňa 2 predchádajúce kritériá.

Prvočísla

Prvočísla definujme ako:

  • Číslo 2 je najmenšie prvačíslo.
  • Prvočíslo je každé celé kladné číslo, ktoré nie je deliteľné žiadnym iným menším prvočíslom ako je toto číslo samotné.

Katalánske čísla

  • [math]C_0=1[/math]
  • [math]C_{n+1}=\frac{(4n+2)C_n}{n+2}[/math]

Ackermanova funkcia

Ackermanova funkcia[2] je príklad neprimitívnej rekurzívne definovanej funkcie, ktorá veľmi rýchlo rastie. Pre kladné m, n môžeme Ackermanovu funkciu vyjadriť nasledokvne: [math] A(m,n) = \begin{cases} n+1, & ak\ m=0 \\ A(m-1,1), & ak\ m\gt 0,\ n=0 \\ A(m-1,A(m,n-1)), & ak\ m\gt 0,\ n\gt 0 \end{cases} [/math] Už pre malé hodnoty m a n dosahuje veľkých hodnôt. Napríklad A(4,2) je celé číslo, ktoré má 19 729 cifier.

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


Ukážky rekurzívne definovaných funkcií

Faktoriál

Definícia:

  • 0!=1
  • n!=n*(n-1)!

Pri tvorbe funkcie pre výpočet faktoriálu budeme postupovať presne podľa rekurzívnej definície: 

long faktorial(int n) {
 if(n==0) return 1; // 0!=1
 return n*faktorial(n-1); // n!=n*(n-1)!
}

Fibonacciho postupnosť

Definícia:

  • Fib(0)=0
  • Fib(1)=1
  • Fib(i)=Fib(i-1)+Fib(i-2), pre i>1

Rovnako aj tu budeme postupovať presne podľa rekurzívnej definície: 

long fibonacci(int n) {
 if(n<2) return n; // fib(0)=0, fib(1)=1
 return fibonacci(n-1)+fibonacci(n-2); // fib(n)=fib(n-1)+fib(n-2)
}

Najväčší spoločný deliteľ

Najväčší spoločný deliteľ [3], [4] dvoch celých čísel m,n rieši Euklidov algoritmus. Jeho najjednoduchšia forma sa dá popísať nasledovne:

  1. vstupné hodnoty: m, n
  2. Ak je m=n, tak koniec (krok 6)
  3. ak je m>n, tak m=m-n
  4. ak je n>m, tak n=n-m
  5. skok na krok 2
  6. NSD(m,n)=m (keďze m a n sú rovanké je jedno, ktorú premennú budeme považovať za výsledok)

NSD vieme definovať aj rekurzívne:

  • [math]NSD(m,0)=\ m[/math]
  • [math]NSD(m,n)=NSD(n,m\ \mbox{mod }n)[/math]

V jazyku C to môžeme zapísať nasledovne: 

long nsd(int m, int n) {
 if(n==0) return m; 
 return nsd(n,m%n);
}

Hanoiské veže

...

Odkazy

  1. ↑ http://en.wikipedia.org/wiki/Recursive_acronym
  2. ↑ Ackermanova funkcia - http://en.wikipedia.org/wiki/Ackermann_function
  3. ↑ Výpočet NSD - http://sputsoft.com/2009/10/computing-the-greatest-common-divisor/
  4. ↑ NSD - definícia http://en.wikipedia.org/wiki/Greatest_common_divisor
Zdroj: „http://www.kiwiki.info/index.php?title=Rekurzia&oldid=627“