Python - Rekuzija


Šta je rekurzija?

Rekurzija je postupak definisanja nečega u smislu samog sebe. Primjer fizičkog svijeta bio bi postavljanje dva paralelna ogledala okrenuta jedno prema drugom. Bilo koji objekt između njih reflektovao bi se rekurzivno.



Python rekurzivna funkcija

U Pythonu znamo da funkcija može pozivati druge funkcije. Moguće je čak i da se funkcija sama pozove. Ove vrste konstrukcija nazivaju se rekurzivnim funkcijama. Sljedeća slika prikazuje rad rekurzivne funkcije koja se naziva recurse.



Slijedi primjer rekurzivne funkcije za pronalaženje faktorijela cijelog broja. Faktorijal broja je umnožak svih cijelih brojeva od 1 do tog broja. Na primjer: faktor od 6 (označen kao 6!) je 1 * 2 * 3 * 4 * 5 * 6 = 720.


Primjer rekurzivne funkcije

def factorial(x):
    """Ovo je rekurzivna funkcija koja
     pronalazi faktorijel cijelog broja"""

    if x == 1:
        return 1
    else:
        return (x * factorial(x-1))


num = 3
print("Faktorijal od", num, "je", factorial(num))

U primjeru, factorial() je rekurzivna funkcija kako se sama naziva. Kada ovu funkciju pozovemo s pozitivnim cijelim brojem, rekurzivno će se pozvati smanjenjem broja. Svaka funkcija množi broj s faktorijelom broja ispod sebe dok ne bude jednak jedinici. Ovaj rekurzivni poziv može se objasniti u sljedećim koracima.

factorial(3)          # 1-vi poziva sa 3
3 * factorial(2)      # 2-gi poziva sa 2
3 * 2 * factorial(1)  # 3-ći poziva sa 1
3 * 2 * 1             # povratak sa 3-ćeg poziva kao broj = 1
3 * 2                 # povratak sa 2-gog
6                     # povratak sa 1-vog

Pogledajmo sliku koja prikazuje korak po korak procesa onoga što se događa:


Naša se rekurzija završava kad se broj smanji na 1. To se naziva osnovni uslov. Svaka rekurzivna funkcija mora imati osnovni uslov koji zaustavlja rekurziju ili se funkcija sama beskonačno poziva.

Interpretator Python ograničava dubinu rekurzije kako bi izbjegao beskonačne rekurzije, što rezultuje preljevima steka (stack overflows). Prema zadanim postavkama, maksimalna dubina rekurzije je 1000. Ako se granica pređe, to rezultuje RecursionError. Pogledajmo jedan takav uslov.

def recursor():
    recursor()
recursor()

Izlaz primjera izgledao bi ovako:

Traceback (most recent call last):
  File "<string>", line 3, in <module>
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded


Prednosti rekurzije

  1. Rekurzivne funkcije čine da kod izgleda čisto i elegantno.
  2. Složeni zadatak može se rastaviti na jednostavnije pod-probleme pomoću rekurzije.
  3. Generisanje sekvence je lakše s rekurzijom nego korištenjem neke ugniježdene iteracije.


Mane rekurzije

  1. Ponekad je teško pratiti logiku iza rekurzije.
  2. Rekurzivni pozivi su skupi (neefikasni), jer zauzimaju puno memorije i vremena.
  3. Teško je otkloniti greške u rekurzivnim funkcijama.