Rekurencja polega na tym, że zakładamy pewien stan początkowy (w tym wypadku a_0=0 i a_1=1). Każde wywołanie funkcji będzie wymagało wywołania tej samej funkcji dla poprzedzających ją argumentów.

Poniżej przedstawiamy funkcję:

def fib_rek(n):
if n == 0:
return 0
if n == 1:
return 1
return fib_rek(n - 1) + fib_rek(n - 2)


Powyższa funkcja pozwala nam na obliczenie n-tej liczby fibonacciego poprzez rekurencję. Tzn. definiujemy pierwsze dwie liczby ciągu a_0=0 i a_1=1. Następne liczby tworzymy kolejne wyrazy za pomocą wywołania funkcji dla argumentów n-1 i n-2.

Wywołaj powyższy kod w dowolnym kompilatorze języka Python (Online Python Compiler (Interpreter)) i podaj wynik print(fib_rek(18)).
2584
3875
1241
13583