Rekurzija je postupak koji u svojoj definiciji koristi samog sebe. U Pajtonu se implementira kao funkcija koja poziva samu sebe.

Ustaljen primer rekurzije je faktorijel. Faktorijel prirodnog broja N možemo definisati kao proizvod broja N i faktorijela njegovog prethodnika u nizu prirodnih brojeva - N-1. Ukoliko je N=1, faktorijel je jednak 1.

Ukoliko faktorijel obeležimo slovom f, onda ovu definiciju možemo zapisati ovako:
f(N) = N * f(N-1).
Sledi implementacija u Pajtonu.



In [8]:

    
def factorial(num):
    if num == 1:
        return 1
    else:
        return num * factorial(num - 1)
    
N = 5
fact = factorial(N)
print("Factorial of %d is %d" % (N, fact))









    



Factorial of 5 is 120

Još jedan ustaljeni primer rekurzije je Fibonačijev niz. Fibonačijev niz se definiše na sledeći način: prvi i drugi član niza jednaki su 1, a svaki sledeći član niza jednak je zbiru prethodna dva člana. Prvih nekoliko članova Fibnačijevog niza: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...
Sledi implementacija u Pajtonu: funkcija koja računa N-ti element Fibonačijevog niza.



In [9]:

    
def fibonacci(nth):
    if nth <= 2:
        return 1
    else:
        return fibonacci(nth - 1) + fibonacci(nth - 2)

nth = 10
fib = fibonacci(nth)
print("The %dth element of the Fibonacci series is: %d" % (nth, fib))









    



The 10th element of the Fibonacci series is: 55