Rekurzija v Pythonu

V programiranju obstaja koncept, imenovan rekurzija - ko funkcija kliče samo sebe.

Primer . Enostavna rekurzija s števcem

Izpišimo s pomočjo rekurzije števila od 1 do 10:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # tukaj funkcija kliče samo sebe
		
	func()

Razpravljajmo, kako ta koda deluje.

Imamo globalno spremenljivko i in funkcijo func, znotraj katere se izpiše vsebina spremenljivke i v konzolo, nato pa se ji doda ena.

Če je naša spremenljivka i manjša ali enaka 10, se funkcija pokliče ponovno. Ker je spremenljivka i globalna, bo ob vsakem novem klicu funkcije vsebovala vrednost, nastavljeno v prejšnjem klicu funkcije.

Izkazalo se bo, da bo funkcija klicala samo sebe, dokler i ne postane večja od 10.

Upoštevajte, da v našem primeru funkcije ne moremo zagnati brez if - če to storimo, bo prišlo do neskončnega klica funkcij.

Primer . Rekurzija za izpis elementov gnezdeneh seznamov

Rekurzije se najpogosteje uporabljajo za preiskovanje seznamov različnih stopenj gnezditve. Recimo, da imamo naslednji seznam:

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

Ustvarimo funkcijo, ki ga bo preiskala. V njej najprej nastavimo pogoj, da se element, ki je primitiven, t.j. preprosto število, izvlečeno iz seznama, izpiše v konzolo. Če pa je element kompleksen objekt, na primer gnezdni seznam, naj v tem primeru funkcija pokliče samo sebe, t.j. pride do rekurzije. Za preverbo tipa elementa uporabimo funkcijo isinstance. Samo za naš primer v prvi parameter isinstance vpišemo el, in kot drugi - tip list:

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

Ob klicu funkcije se izpišejo vsa števila iz gnezdeneh seznamov:

func(lst) # izpiše 1, 2, ... 8, 9

Primer . Rekurzija za operacije z elementi gnezdeneh seznamov

Rekurzije se lahko uporabljajo tudi za različne operacije z elementi gnezdeneh seznamov. Recimo, da imamo naslednji seznam:

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

Pridobimo vsoto vseh njegovih elementov. Za to v funkciji deklariramo spremenljivko res, v katero se bo kopičila vsota števil. V pogoju določimo, da če je element kompleksen objekt, gre v parametru funkcije func in se prišteje k vsoti. To pomeni, da bo element ostal v rekurziji, dokler ne postane primitiven. In v tem primeru se bo preprosto prištel k vsoti, zapisani v res:

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

Pokličimo funkcijo in izpišimo njen rezultat v konzolo:

print(func(lst)) # izpiše 45

Primer . Rekurzija za kopičenje v seznam

Z rekurzijo lahko razgradimo gnezdene sezname v en enodimenzionalen seznam. Recimo, da imamo naslednji seznam:

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

V funkciji določimo prazen seznam res, v katerega se bodo kopičili elementi izvirnega seznama. Nato zaženemo zanko in določimo pogoj - če je element seznam, gre v metodo extend. Ta metoda pripne elemente enega seznama na konec drugega seznama, t.j. elementi gnezdeneh seznamov pridejo na konec seznama 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 izvedene kode:

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

Praktične naloge

Izpišite vse številske elemente slovarja poljubne stopnje gnezditve:

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

Poiščite vsoto elementov slovarja iz prejšnje naloge.

Pridobite seznam primitivnih elementov slovarja iz prejšnje naloge.