02_rekurze

Matrjoška

Matrjoška

Matrjoška

Matrjoška

Fraktály

• Sobě-podobný obrazec
• Opticky složitý tvar
• Generování 

jednoduchými pravidly

• Mraky, sněhové vločky, 

řeky, cévy

Rekurze u funkcí

• Znamená to, že pro výpočet funkce je využita tatáž 

funkce.

• Funkce f1 je volána zatímco jedno z předchozích volání 

f1 ještě nebylo ukončeno návratem.

• Druhy

• přímá rekurze - volá se přímo

• nepřímá rekurze  - volá se zprostředkovaně přes jinou funkci

• lineární rekurze – funkce volá sama sebe jen jednou. 

• Faktoriál

• Hledání pozice dané hodnoty v setříděném poli.

• stromová rekurze – funkce volá sama sebe několikrát

• třídící algoritmy:

Druhy rekurzí

• Tail recursion - rekurze je poslední člen volání 

-> return f()

• Strukturální rekurze - volání funkce přes jinou funkci, 

nebo v jiném místě, než samostatně na konci

• Backtracking - zpětné vyčíslování rekurze 

(obecně funkce)

• Mutual (indirect) recursion - dva objekty, závisí na sobě

• funkce volající se navzájem

• objekty ukazující na sebe navzájem

• např. binární strom se skládá z uzlu a dvou stromů

• Corecursion - duální k rekurzi, od jednoduchého ke 

složitému. 

Obecný zápis rekurze

vstup x

test konečné podmínky,

pokud je splněna, ukonči funkci a 

vrať se (do předchozí úrovně)

výpočet před rekurentním voláním

(pro jednotlivá volání)

rekurentní volání s upraveným x

(jedno, nebo v několika větvích)

test a zpracování návratové hodnoty
výpočet po rekurentním volání

(jednom či více)

návrat do předchozí úrovně

Faktoriál

• použití například ve statistice (pravděpodobnost, 

rozložení, …)

• platí

• n! = n.(n-1)!

n > 0

• n! = 1

n = 0

• algoritmus nerekurzivní:

vstup x

pokud (x == 1)

výsledek = 1

jinak

výsledek = 1

pro n = 1 až x; krok 1

výsledek = n * výsledek

Faktoriál

• n! = n. (n-1)!   - princip rekurze, v popisu (definici)