Увод у рекурзију у Питхон-у

Преглед садржаја

Želite li da detaljno upoznate rekurziju u programiranju? Ovaj vodič o rekurziji u Pythonu će vam dati sjajnu osnovu.

Rekurzija je izuzetno korisna tehnika za rešavanje različitih problema, koju bi svaki programer trebalo da ima u svom alatu. Iako je u početku možda teško shvatiti je, rekurzija vam može omogućiti da dođete do elegantnijih rešenja za kompleksne zadatke.

U ovom tutorijalu ćemo primeniti pristup učenja rekurzije kroz Python. Konkretno, obradićemo sledeće teme:

Osnove rekurzije
Kako funkcionišu rekurzivne funkcije
Implementacija rekurzivnih funkcija u Pythonu
Razlike između iterativnog i rekurzivnog pristupa rešavanju problema

Započnimo!

Šta je rekurzija?

Rekurzija predstavlja programersku tehniku gde funkcija ponavlja svoj poziv kako bi se problem rešio.

U svojoj suštini, rekurzija je metoda rešavanja problema koja uključuje razlaganje složenog zadatka na manje, identične podzadatke. Na taj način, omogućava vam da rešite problem u terminima njegovih jednostavnijih verzija.

Kako se rekurzija sprovodi u kodu? Da bismo to razumeli, pogledajmo kako funkcionišu rekurzivne funkcije.

Razumevanje rekurzivnih funkcija

Rekurzivna funkcija je definisana tako da poziva samu sebe unutar svoje definicije. Svaki rekurzivni poziv predstavlja smanjenu ili pojednostavljenu verziju inicijalnog problema.

Kako bi se osiguralo da rekurzija na kraju stane, rekurzivne funkcije moraju sadržati jedan ili više baznih slučajeva – uslova pod kojima funkcija prestaje da se poziva i vraća rezultat.

Hajde da ovo detaljnije razmotrimo. Rekurzivna funkcija se sastoji od:

Bazni slučaj: To je uslov (ili skup uslova) koji određuje kada rekurzija treba da se zaustavi. Kada je bazni slučaj ispunjen, funkcija vraća rezultat bez daljih rekurzivnih poziva. Bazni slučaj je ključan za sprečavanje beskonačne rekurzije.
Rekurzivni slučaj: On definiše kako se problem razlaže na manje podprobleme. U ovom delu funkcije, funkcija poziva samu sebe sa izmenjenim ulaznim parametrima. Svaki rekurzivni poziv je, stoga, korak ka postizanju baznog slučaja.

Sada, hajde da razmotrimo šta se dešava kada pozovete rekurzivnu funkciju.

Kako rekurzija radi „ispod haube“

Kada se funkcija pozove, zapis konteksta njenog izvršavanja se postavlja na stek poziva. Ovaj zapis sadrži informacije o argumentima funkcije, lokalnim promenljivima i mestu na koje treba da se vrati kada funkcija završi sa izvršavanjem.

Kod rekurzivnih funkcija, kada funkcija pozove samu sebe, novi zapis se dodaje na stek poziva, čime se efektivno suspenduje izvršavanje trenutne funkcije. Stek omogućava Pythonu da prati sve pozive funkcija na čekanju, uključujući one iz rekurzivnih poziva.

Rekurzija se nastavlja sve dok se ne dostigne bazni slučaj. Kada bazni slučaj vrati rezultat, pozivi funkcija se razrešavaju jedan po jedan – pri čemu svaka funkcija vraća svoj rezultat na prethodni nivo steka poziva. Ovaj proces se nastavlja sve dok se početni poziv funkcije ne završi.

Implementacija rekurzije u Pythonu

U ovom odeljku ćemo istražiti tri jednostavna primera rekurzije:

Izračunavanje faktorijela broja
Izračunavanje Fibonačijevih brojeva
Implementacija binarne pretrage koristeći rekurziju.

Za svaki primer, prvo ćemo definisati problem, dati rekurzivnu Python implementaciju, a zatim objasniti kako implementacija funkcioniše.

#1. Izračunavanje faktorijela pomoću rekurzije

Problem: Izračunati faktorijel nenegativnog celog broja n, označen sa n!. Matematički, faktorijel broja n je proizvod svih pozitivnih celih brojeva od 1 do n.

Izračunavanje faktorijela je pogodno za rekurziju, kao što je prikazano na slici:

Evo rekurzivne funkcije za izračunavanje faktorijela datog broja n:


def factorial(n):
	# Bazni slučaj
    if n == 0 or n == 1:
        return 1
	# Rekurzivni slučaj: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

Hajde da izračunamo 5! koristeći `factorial()` funkciju:


factorial_5 = factorial(5)
print(factorial(5))
# Izlaz: 120

Pogledajmo sada kako funkcija radi:

Imamo bazni slučaj koji proverava da li je n jednako 0 ili 1. Ako je uslov ispunjen, funkcija vraća 1. Podsetimo se da je 0! jednako 1, kao i 1!.
Ako je n veće od 1, izračunavamo n! množenjem n sa faktorijelom od n-1. Ovo se izražava kao n * factorial(n – 1).
Funkcija nastavlja da vrši rekurzivne pozive sa opadajućim vrednostima od n sve dok ne dostigne bazni slučaj.

#2. Fibonačijevi brojevi sa rekurzijom

Problem: Pronaći član na n-tom indeksu u Fibonačijevom nizu. Fibonačijev niz se definiše na sledeći način: F(0) = 0, F(1) = 1 i F(n) = F(n-1) + F(n-2) za n >= 2.


def fibonacciSeq(n):
	# Bazni slučajevi
    if n == 0:
        return 0
    elif n == 1:
        return 1
	# Rekurzija: F(n) = F(n-1) + F(n-2)
    else:
        return fibonacciSeq(n - 1) + fibonacciSeq(n - 2)

Pokrenimo funkciju:


fib_5 = fibonacciSeq(5)
print(fib_5)
# Izlaz: 5

Evo kako funkcija radi:

Počnimo sa baznim slučajevima. Ako je n 0, vraća 0. A ako je n 1, vraća 1. Podsetimo se F(0) = 0 i F(1) = 1.
U rekurzivnom slučaju, ako je n veće od 1, funkcija izračunava F(n) dodavanjem F(n-1) i F(n-2) članova. Ovo se izražava kao fibonacciSeq(n – 1) + fibonacciSeq(n – 2).
Funkcija nastavlja da vrši rekurzivne pozive sa opadajućim vrednostima od n sve dok ne dostigne bazne slučajeve.

#3. Rekurzivna implementacija binarne pretrage

Problem: Implementirati algoritam binarne pretrage pomoću rekurzije kako biste pronašli poziciju ciljnog elementa u sortiranoj listi.

Evo rekurzivne implementacije binarne pretrage:


def binarySearch(arr, target, low, high):
	# Bazni slučaj: cilj nije pronađen
    if low > high:
        return -1

    mid = (low + high) // 2

	# Bazni slučaj: cilj pronađen
    if arr[mid] == target:
        return mid
	# Rekurzivni slučaj: pretraži levu ili desnu polovinu niza
    elif arr[mid] > target:
        return binarySearch(arr, target, low, mid - 1)
    else:
        return binarySearch(arr, target, mid + 1, high)

Funkcija `binarySearch` nastavlja da deli interval pretrage na pola sa svakim rekurzivnim pozivom sve dok ne pronađe cilj ili ne utvrdi da cilj nije u listi.

Evo primera pokretanja funkcije:


arr = [5, 8, 13, 24, 37, 49, 51, 64, 72, 88, 96]
target = 37
idx = binarySearch(arr, target, 0, len(arr)-1)
print(idx)
# Izlaz: 4

Hajde da razložimo šta funkcija radi:

U implementaciji rekurzivne binarne pretrage, imamo dva bazna slučaja. Prvo, ako `low` postane veće od `high`, to znači da ciljni element nije u listi. Zato vraćamo -1 kako bismo označili da cilj nije pronađen.
Drugi bazni slučaj proverava da li je element na srednjem indeksu unutar trenutnog intervala pretrage jednak cilju. Ako se poklapaju, vraćamo srednji indeks, pokazujući da smo pronašli cilj.
U rekurzivnom slučaju, ako je srednji element veći od cilja, rekurzivno pretražujemo levu polovinu niza pozivanjem `binarySearch(arr, target, low, mid – 1)`. Ako je srednji element manji od cilja, tražimo desnu polovinu pozivanjem `binarySearch(arr, target, mid + 1, high)`.

Rekurzivni naspram iterativnog pristupa

Iterativni pristup – korišćenje petlji – je još jedan uobičajeni pristup rešavanju problema. Dakle, kako se razlikuje od rekurzije? Pogledajmo.

Prvo, uporedićemo rekurzivna i iterativna rešenja za isti problem: izračunavanje faktorijela broja.

Evo rekurzivne implementacije faktorijela:


def factorialRec(n):
	# Bazni slučaj
    if n == 0 or n == 1:
        return 1
	# Rekurzivni slučaj: n! = n * (n-1)!
    else:
        return n * factorial(n - 1)

Pošto znamo da je faktorijel nenegativnog broja proizvod svih brojeva od 1 do n, možemo napisati i iterativnu implementaciju koristeći petlje.


def factorialIter(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

Obe ove implementacije daju identične rezultate.


factorial_5 = factorialRec(5)
print(factorial_5)
# Izlaz: 120

factorial_5 = factorialIter(5)
print(factorial_5)
# Izlaz: 120

Da li je iterativni pristup poželjniji od rekurzije? Kada imamo duboku rekurziju – sa previše poziva funkcija – može doći do grešaka zbog prekoračenja dubine rekurzije. Petlja je bolja opcija za probleme čija rekurzivna implementacija zahteva previše poziva funkcija da bi se došlo do baznog slučaja.

Hajde da sumiramo razlike između iterativnih i rekurzivnih implementacija:

Karakteristika	Rekurzivni pristup	Iterativni pristup
Struktura	Koristi rekurzivne pozive funkcija i oslanja se na stek poziva.	Koristi petlje za iteraciju bez dodatnih poziva funkcija.
Bazni slučajevi	Zahteva eksplicitne bazne slučajeve za zaustavljanje rekurzije.	Uobičajeno koristi uslove petlje za završetak.
Performanse	Može biti sporija zbog memorijskog opterećenja. Duboka rekurzija ponekad može dovesti do grešaka prekoračenja steka.	Generalno je efikasnija memorijski i manje je podložna greškama prekoračenja steka.
Otklanjanje grešaka	Može biti izazovno za otklanjanje grešaka zbog više poziva funkcija i ugnežđenih konteksta izvršavanja.	Obično je lakše otklanjati greške zbog jednostavnog linearnog toka izvršavanja.

Zaključak

U ovom članku, počeli smo sa razumevanjem šta je rekurzija i kako da definišemo rekurzivne funkcije sa baznim slučajevima i rekurzivnim odnosima.

Zatim smo napisali Python kod – rekurzivne implementacije uobičajenih programskih problema. Na kraju, naučili smo razlike između iterativnog i rekurzivnog pristupa i prednosti i mane svakog od njih.

Zatim pogledajte ovu listu pitanja za Python intervju.