Rekurzija u Pythonu

U programiranju postoji pojam, rekurzija - kada funkcija poziva samu sebe.

Primer . Jednostavna rekurzija sa brojačem

Hajde da ispišemo pomoću rekurzije brojeve od 1 do 10:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # ovde funkcija poziva samu sebe
		
func()

Hajde da razmotrimo kako ovaj kod radi.

Imamo globalnu promenljivu i i funkciju func, unutar koje se u konzolu ispisuje sadržaj promenljive i, a zatim joj se dodaje jedinica.

Ako je naša promenljiva i manja ili jednaka 10, onda se funkcija poziva ponovo. Pošto je promenljiva i globalna, tada će pri svakom novom pozivu funkcije u njoj biti postavljena vrednost promenljive i iz prethodnog poziva.

Ispostavlja se da će funkcija pozivati samu sebe sve dok i ne postane veća od 10.

Imajte u vidu da u našem slučaju ne možemo funkciju pokrenuti bez if - ako se to uradi, dobićemo beskonačno pozivanje funkcija.

Primer . Rekurzija za ispis elemenata ugnježdenih listi

Najače se rekurzije primenjuju za prolazak kroz liste različitog stepena ugnježdenosti. Neka imamo sledeću listu:

lst = [1, [2, 3], [[4, 5], [6, 7, 8, [9]]]]

Hajde da napravimo funkciju koja će proći kroz nju. U njoj prvo treba postaviti uslov, da element, koji je primitivan, tj. prosto izvučen broj iz liste, bude ispisan u konzolu. A ako je element objekat, na primer, ugnježdena lista, onda neka u tom slučaju funkcija pozove samu sebe, tj. desiće se rekurzija. Za proveru tipa elementa primenimo funkciju isinstance. Samo za naš primer u prvi parametar isinstance upisaćemo el, a drugim - tip list:

def func(lst):
	for el in lst:
		if isinstance(el, list):
			func(el)
		else:
			print(el)

Pri pozivu funkcije ispisaće se niz svih brojeva iz ugnježdene liste:

func(lst) # ispisaće 1, 2, ... 8, 9

Primer . Rekurzija za operacije sa elementima ugnježdenih listi

Rekurzije se mogu primeniti i za različite operacije sa elementima ugnježdenih listi. Neka imamo sledeću listu:

lst = [1, [2, 3], [[4, 5], [6, 7, 8, [9]]]]

Hajde da dobijemo zbir svih njenih elemenata. Za ovo u funkciji deklarišimo promenljivu res, u koju će se nakupiti zbir brojeva. U uslovu upisaćemo da ako je element složen objekat, onda on pada u parametru funkcije func i dodaje se zbiru. Ovo znači da će element biti u rekurziji sve dok ne postane primitivan. I u tom slučaju će se prosto dodati zbiru, zapisanom u res:

def func(lst):
	res = 0
	for el in lst:
		if isinstance(el, list):
			res += func(el)
		else:
			res += el
	return res

Hajde da pozovemo funkciju i ispišemo njen rezultat u konzolu:

print(func(lst)) # ispisaće 45

Primer . Rekurzija za nakupijanje u listu

Pomoću rekurzije možemo raščlaniti ugnježdene liste u jednu jednodimenzionalnu listu. Neka imamo sledeću listu:

lst = [1, [2, 3], [[4, 5], [6, 7, 8, [9]]]]

Hajde da upišemo u funkciji praznu listu res, u koju će se nakupiti elementi početne liste. Zatim pokrenimo ciklus i postavimo uslov - ako element je lista, onda će da upadne u metod extend. Ovaj metod pridružuje elemente jedne liste na kraj druge liste, tj. elementi ugnježdene liste upašće na kraj liste res:

def func(lst):
	res = []
	for el in lst:
		if isinstance(el, list):
			res.extend(func(el))
		else:
			res.append(el)
	return res
	
print(func(lst))

Rezultat izvršenog koda:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Praktični zadaci

Ispišite sve numeričke elemente rečnika proizvoljnog nivoa ugnježdenosti:

{
	'a': {
		'b': 1,
		'c': 2,
		'd': {
			'e': 3,
			'f': 4
		}
	},
	'j': {
		'h': 5,
		'k': 6,
	},
	'l': 7
}

Nađite zbir elemenata rečnika iz prethodnog zadatka.

Dobijte listu primitivnih elemenata rečnika iz prethodnog zadatka.