9. Rekurze

Při rekurzivním volání volá funkce samu sebe. Aby nedošlo k nekonečné smyčce, musí toho volání obsahovat ukončovací podmínku. Obecně lze rekurzi zapsat

def funkce(promenna):
   if (ukoncovaci podminka):
      funkce(zmenena_promenna)         

Pomocí rekurze můžeme například implementovat for cyklus:

def recursivePrint(index, array):
    if (index < len(array) ):
        print(array[index], end=' ' );
        recursivePrint(index+1, array)
        print(array[index], end=' ' );
 
a = []
for i in range(10):
    a.append(i*i)
 
print("List je",a)
recursivePrint(0, a);

• Napište rekurzivní funkci power(x,n), která bude počítat $x^n$
• Porovnejte s iterativní verzí

• Uvažujme seznam, který může obsahovat jako prvky další seznamy, např.:

a=[1, 2, [3, [4, 5], 6, [7]], [8, 9], 10]

• Napište funkci flatten, která vytvoří jeden seznam, který bude obsahovat všechny prvky ze seznamu a vložené do tohoto seznamu.
• Výsledkem funkce flatten(a):

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

• K testu prvku, zda je pole (list), použijte funkci type:

if type(x) is list:

• Napište funkci binomial(k,n), která počítá hodnotu $ n \choose k $
• Můžete využít vztah $ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} $
• Počáteční podmínky $\binom{n}{0}=\binom{n}{n}=1$ a $\binom{n}{1}=\binom{n}{n-1}=n$

Napište rekurzivní výpočet Fibonacciho posloupnosti. Pro tuto posloupnost platí:

• $F_n = F_{n-1} + F_{n-2}$
• První členy posloupnosti jsou $F_0 = 0$ a $F_1 = 1$.