Warning
This page is located in archive.

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

Úkol 1: umocňování

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

Úkol 2: narovnání

  • 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:

Úkol 3: binomický koeficient

  • 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$

Úkol 4: výpočet Fibonacciho posloupnosti

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$.
courses/bab37zpr/tutorials/lab09.txt · Last modified: 2019/11/26 11:51 by viteks