Rekurencja jest jednym ze sposobów rozwiązywania problemu. Sposób ten zakłada rozbijanie problemu na coraz to mniejsze i mniejsze części, aż dojdziemy do momentu, że problem będzie tak niewielki, że zostanie łatwo rozwiązany.

W programowaniu rekurencja sprowadza się do funkcji, które same siebie wywołują.

Rekurencja opiera się na 3 prawach:

• funkcja rekurencyjna musi posiadać bazowy problem
• funkcja rekurencyjna musi zmierzać do bazowego problemu
• funkcja rekurencyjna musi sama siebie wywoływać

Standardowym przykładem funkcji rekurencyjnej jest obliczanie silni. Dla przypomnienia 3! = 1*2*3 = 6

def silnia (x) :
    if x < 1 :
        return 1
    else :
        return x * silnia (x - 1)

print(silnia(3))

Efekt: 6

Dla przypadku gdy wartość x = 1 wynikiem jest 1.

Dla pozostałych przypadków, a zakładamy, że funkcja przyjmuje wartości liczb naturalnych, funkcja zwraca aktualną wartość pomnożoną przez wartość wywołanej funkcji z parametrem wejściowym o jeden mniejszym.

W podanym przykładzie kolejne kroki przedstawiają się następująco:

• wywołanie silnia(3)
• funkcja zwraca 3 * silnia(2)
• funkcja silnia (2) zwraca 2 * silnia(1)
• silnia(1) jest problemem bazowym, zwraca więc 1
• wyniki kolejnych zwróceń składają się w całość, mamy 3 * 2 * 1, co daje nam wynik 6

Spróbujmy jeszcze obliczyć rekurencyjnie sumę liczb od 1 do n, gdzie n jest dowolną liczbą naturalną. Dla wartości 5 wynik powinien przedstawiać się następująco: 1 + 2 + 3 + 4 + 5 = 15

def suma (n) :
    if n == 1 :
        return 1
    else :
        return n + suma(n-1)

print(suma(5))

Efekt: 15