Rekurze v Pythonu

V programování existuje pojem rekurze - když funkce volá sama sebe.

Příklad . Jednoduchá rekurze s čítačem

Vypišme pomocí rekurze čísla od 1 do 10:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # zde funkce volá sama sebe
		
	func()

Pojďme si vysvětlit, jak tento kód funguje.

Máme globální proměnnou i a funkci func, uvnitř které se do konzole vypisuje obsah proměnné i a poté se k ní přičte jedna.

Pokud je naše proměnná i menší nebo rovna 10, pak je funkce volána znovu. Protože proměnná i je globální, tak při každém novém volání funkce v ní bude hodnota nastavená při předchozím volání funkce.

Výsledkem bude, že funkce bude volat sama sebe dokud i nebude větší než 10.

Mějte na paměti, že v našem případě nelze funkci spustit bez if - pokud to uděláme, dostaneme nekonečné volání funkcí.

Příklad . Rekurze pro výpis prvků vnořených seznamů

Rekurze se nejčastěji používají pro průchod seznamů různé úrovně vnoření. Předpokládejme, že máme následující seznam:

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

Vytvořme funkci, která jej projde. V ní je nejprve potřeba nastavit podmínku, aby prvek, který je primitivem, tj. prostě číslem vytaženým ze seznamu, byl vypsán do konzole. A pokud je prvek objektem, například vnořeným seznamem, pak v tomto případě ať funkce zavolá sama sebe, tj. dojde k rekurzi. Pro kontrolu typu prvku použijeme funkci isinstance. Pouze pro náš příklad do prvního parametru 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)

Při volání funkce se vypíše řada všech čísel z vnořeného seznamu:

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

Příklad . Rekurze pro operace s prvky vnořených seznamů

Rekurze lze aplikovat i pro různé operace s prvky vnořených seznamů. Předpokládejme, že máme následující seznam:

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

Získejme součet všech jeho prvků. K tomu ve funkci deklarujme proměnnou res, do které se bude akumulovat součet čísel. V podmínce nastavíme, že pokud je prvek složitým objektem, pak se dostane v parametru funkce func a přičte se ke součtu. To znamená, že prvek bude v rekurzi dokud se nestane primitivem. A v tomto případě se jednoduše přičte k součtu zapsanému v res:

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

Zavolejme funkci a vypišme její výsledek do konzole:

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

Příklad . Rekurze pro akumulaci do seznamu

Pomocí rekurze lze rozložit vnořené seznamy do jednoho jednorozměrného seznamu. Předpokládejme, že máme následující seznam:

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

Nastavme ve funkci prázdný seznam res, do kterého se budou akumulovat prvky původního seznamu. Dále spustíme cyklus a nastavíme podmínku - pokud je prvek seznamem, pak se dostane do metody extend. Tato metoda připojuje prvky jednoho seznamu na konec druhého seznamu, tj. prvky vnořeného seznamu se dostanou na konec seznamu 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ýsledek provedeného kódu:

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

Praktické úlohy

Vypište všechny číselné prvky slovníku libovolné úrovně vnoření:

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

Najděte součet prvků slovníku z předchozí úlohy.

Získejte seznam primitivních prvků slovníku z předchozí úlohy.