U ovom vodiču naučit ćete stvoriti rekurzivnu funkciju (funkciju koja se sama poziva).
Što je rekurzija?
Rekurzija je postupak definiranja nečega u smislu samog sebe.
Primjer fizičkog svijeta bio bi postavljanje dva paralelna ogledala okrenuta jedno prema drugome. Bilo koji objekt između njih reflektirao 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 tzv recurse.
Rekurzivna funkcija u Pythonu
Slijedi primjer rekurzivne funkcije za pronalaženje faktora 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): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1)) num = 3 print("The factorial of", num, "is", factorial(num))
Izlaz
Faktorijal broja 3 je 6
U gornjem primjeru factorial()je rekurzivna funkcija kako se sama naziva.
Kad 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 jednaka jedinici. Ovaj rekurzivni poziv može se objasniti u sljedećim koracima.
faktorijel (3) # 1. poziv s 3 3 * faktorijem (2) # 2. poziv s 2 3 * 2 * faktorijem (1) # 3. poziv s 1 3 * 2 * 1 # povratak s 3. poziva kao broj = 1 3 * 2 # povratak iz drugog poziva 6 # povratak iz prvog poziva
Pogledajmo sliku koja prikazuje korak po korak procesa onoga što se događa:
Rad rekurzivne faktorijelne funkcije
Naša se rekurzija završava kad se broj smanji na 1. To se naziva osnovni uvjet.
Svaka rekurzivna funkcija mora imati osnovni uvjet koji zaustavlja rekurziju ili se funkcija sama beskonačno poziva.
Interpretator Python ograničava dubinu rekurzije kako bi izbjegao beskonačne rekurzije, što rezultira preljevima stoga.
Prema zadanim postavkama, maksimalna dubina rekurzije je 1000. Ako se granica prijeđe, rezultira RecursionError. Pogledajmo jedan takav uvjet.
def recursor(): recursor() recursor()
Izlaz
Traceback (najnoviji zadnji poziv): Datoteka "", red 3, u datoteci "", red 2, u datoteci "", red 2, u datoteci "", red 2, u (Prethodni redak ponovljen još 996 puta ) RecursionError: premašena je maksimalna dubina rekurzije
Prednosti rekurzije
- Rekurzivne funkcije čine da kod izgleda čisto i elegantno.
- Složeni zadatak može se rastaviti na jednostavnije pod-probleme pomoću rekurzije.
- Generiranje sekvenci lakše je s rekurzijom nego korištenjem neke ugniježđene iteracije.
Mane rekurzije
- Ponekad je teško pratiti logiku iza rekurzije.
- Rekurzivni pozivi skupi su (neučinkoviti) jer zauzimaju puno memorije i vremena.
- Teško je otkloniti pogreške u rekurzivnim funkcijama.
