7. Rekurze

V řešení k příkladům z cvičení v třetím týdnu byla jedna z možností, jak stanovit největší společný dělitel, pomocí funkce, která ve svém těle volala samu sebe:

# Uloha 7 z cv03 pomoci rekurze
 
def gcd(m,n):
    if n == 0:   # pri rekurzivnim volani je nutne mit ve funkci podminku, ktera ukonci funkci
        return m
    else:  # pokud ukoncovaci podminka neni splnena, funkce zavola samu sebe s upravenymi argumenty
        return gcd(n, m%n)  # funkce vola samu sebe

# Uloha 7 z cv03 pomoci cyklu
def gcd(m,n):
    while n != 0:
        m, n = n, m%n 
    return m

Formálně tedy při rekurznivním volání je ve funkci s jedním nebo více argumenty podmínka na základě které se buď zavolá funkce znovu s novým argumentem, nebo se funkce ukončí

def funkce(argument):
   if podminka:
      funkce(novy_argument)      

# vypis cisel od 0 do 9 pomoci rekurze
 
def vypisuj(i,N):
    if i<N:  # pokud je i mensi nez N, vypise i0 a zavola funkci pro i+1
        print(i,end = ' ')
        vypisuj(i+1,N)
 
 
vypisuj(0,10)

pro pochopení, jak program prochází funkci při rekurzivním volání, a jak následně funkce opouští, si přidáme ještě jeden výpis a využijem debuger (snížíme počet čísel na 3)

# vypis cisel od 0 do 3 pomoci rekurze
 
def vypisuj(i,N):
    if i<N:  # pokud je i mensi nez N, vypise i0 a zavola funkci pro i+1
        print(i,end = ' ')
        vypisuj(i+1,N)
        print(i,end = ' ')  # vypis i po vystupu z funkce (v momente, kdy neni splne podminka)
 
vypisuj(0,3)

Úloha 1 - Nalezení maximálního čísla v seznamu

• Vezmeme první prvek v seznamu a dále zavoláme funkci pro nalezení maximalního prvku ve zbylém seznamu
• Poté porovnáme obě hodnoty a vrátíme větší hodnotu
• Pokud je délka seznamu == 1, vrátíme prvek tohoto seznamu

def najdi_maximum(seznam):
 
    # <vas kod>    
 

Úloha 2 - Pomocí rekurze implementujte funkci, která vrátí n-tý člen (indexujeme od 0) Fibonacciho posloupnosti - pokuste se poté o efektivnější implementaci, která bude využívat již vypočítané hodnoty posloupnosti, které budou ukládány v globálně dostupné proměnédostupném poli - zamyslete se nad implementací jak pomocí slovníku tak pomocí pole

# Fib. posloupnost pomoci rekurze
 
def myfibonacci(n):
 
    # <vas kod>
 
n = 10
Fn =  myfibonacci(n)
print("F({0:d}) = {1:d}".format(n,Fn))

Úloha 3 - Pomocí rekurze napište funkci, která ze seznamu tvořeného seznamy, vrátí 1D seznam

Vstup:

[1, 2, [3, 4, [5, 7], 3], 4]

Výstup

[1, 2, 3, 4, 5, 7, 3, 4]

vstup = [[1, 2, [3, 4, [5, 7], 3], 4]]
 
def narovnej(vstup):
    # <vas kod>

Úloha 4 - Pomocí rekurze najděte cestu na konec “bludiště”.

• Pro jednoduchost budeme předpokládat 1D bludiště, kde index pole bude značit jednotlivá políčka od 0 do 5, kdy 0 představuje zeď a 5 je cíl. Start bude na políčku 2.
• V programu bude funkce, která zjistí, jestli se nenacházíte v cíli (konec hledání), funkce vrátí True
• Nebo ve zdi nebo na políčku, přes které jste již šli, funkce vrátí False
• Nebo zavolá samu sebe s argumentem x-1 nebo x+1 (posun na sousední poličko)
• V každém kroku ukládejte hodnoty True do pole, značícího již navštívená políčka
• Pokud je návratová hodnota funkce True, uložte do pole ukazujícího správnou cestu hodnotu True

Úloha 5 - Implementujte Euklideův algoritmus pro výpočet největšího společného dělitele pomocí rekurzivního násobení matice

Při Euklidově algoritmu (úloha v třetím cvičení) dochází k opakovanému odečítání menší z dvojice čísel od většího čísla, až dokud jsou si obě čísla rovny

Opakované odečítání dvojice čísel lze zapsat jako rekurzivní součin matic. Pro dvojici čísel m a n, kde m > 1: $$\begin{bmatrix} m_{k+1} \cr n_{k+1} \end{bmatrix} = \begin{bmatrix} 1 & -1 \cr 0 & 1 \end{bmatrix} \begin{bmatrix} m_{k} \cr n_{k} \end{bmatrix}$$ Pokud je m < n, pak dojde k prohození jejich hodnot a vypočet pokračuje až do m == n

Úloha 6 - Efektivnější varianta Euklideova algoritmu pro výpočet největšího společného dělitele pomocí maticového násobení

Opakované odečítání dvojice čísel lze zapsat jako rekurzivní součin matic. Pro dvojici čísel m a n, kde m > 1: $$\begin{bmatrix} m_{k+1} \cr n_{k+1} \end{bmatrix} = \begin{bmatrix} 0 & 1 \cr 1 & -(\frac{m}{n}) \end{bmatrix} \begin{bmatrix} m_{k} \cr n_{k} \end{bmatrix}$$ Pokud je m < n, pak dojde k prohození jejich hodnot a vypočet pokračuje až do m == n. ($\frac{m}{n}$) je zaokrouhlen dolu