Rekurzia v Pythone

V programovaní existuje pojem rekurzia - keď funkcia volá sama seba.

Príklad . Jednoduchá rekurzia s počítadlom

Vypíšme pomocou rekurzie čísla od 1 do 10:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # tu funkcia volá sama seba
		
	func()

Poďme diskutovať o tom, ako tento kód funguje.

Máme globálnu premennú i a funkciu func, vnútri ktorej sa do konzoly vypíše obsah premennej i a potom sa k nej pripočíta jedna.

Ak je naša premenná i menšia alebo rovná 10, funkcia sa zavolá znovu. Pretože premenná i je globálna, pri každom novom volaní funkcie v nej bude nastavená hodnota premennej i z predchádzajúceho volania.

Výsledkom bude, že funkcia bude volať sama seba, kým i nebude väčšia ako 10.

Majte na pamäti, že v našom prípade nie je možné funkciu spustiť bez if - ak by sa to urobilo, vzniklo by nekonečné volanie funkcií.

Príklad . Rekurzia na výpis prvkov vnorených zoznamov

Rekurzie sa najčastejšie používajú na prechádzanie zoznamov rôzneho stupňa vnorenia. Majme nasledujúci zoznam:

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

Vytvorme funkciu, ktorá ho prejde. V nej je najprv potrebné nastaviť podmienku, aby prvok, ktorý je primitívom, t.j. jednoducho číslom vybratým zo zoznamu, bol vypísaný do konzoly. A ak je prvkom zložený objekt, napríklad vnorený zoznam, v tomto prípade nech funkcia zavolá sama seba, t.j. dôjde k rekurzii. Na kontrolu typu prvku použijeme funkciu isinstance. Len pre náš príklad do prvého parametra isinstance napíšeme el a druhým bude typ list:

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

Pri volaní funkcie sa vypíše rad všetkých čísel z vnoreného zoznamu:

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

Príklad . Rekurzia pre operácie s prvkami vnorených zoznamov

Rekurzie možno použiť aj pre rôzne operácie s prvkami vnorených zoznamov. Majme nasledujúci zoznam:

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

Získajme súčet všetkých jeho prvkov. Na to vo funkcii deklarujme premennú res, do ktorej sa bude hromadiť súčet čísel. V podmienke napíšme, že ak je prvok zloženým objektom, dostane sa v parametri funkcie func a pripočíta sa k súčtu. To znamená, že prvok bude v rekurzii, kým sa nestane primitívom. A v tomto prípade sa jednoducho pripočíta k súčtu zapísanému v res:

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

Zavolajme funkciu a vypíšme jej výsledok do konzoly:

print(func(lst)) # vypíše 45

Príklad . Rekurzia pre nahromadenie do zoznamu

Pomocou rekurzie je možné rozložiť vnorené zoznamy do jedného jednorozmerného zoznamu. Majme nasledujúci zoznam:

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

Napíšme vo funkcii prázdny zoznam res, do ktorého sa budú hromadiť prvky pôvodného zoznamu. Ďalej spustíme cyklus a nastavíme podmienku - ak je prvok zoznamom, dostane sa do metódy extend. Táto metóda pripája prvky jedného zoznamu na koniec druhého zoznamu, t.j. prvky vnoreného zoznamu sa dostanú na koniec zoznamu 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))

Výsledok vykonaného kódu:

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

Praktické úlohy

Vypíšte všetky číselné prvky slovníka ľubovoľnej úrovne vnorenia:

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

Nájdite súčet prvkov slovníka z predchádzajúcej úlohy.

Získajte zoznam primitívnych prvkov slovníka z predchádzajúcej úlohy.