Rekurzió a Pythonban

A programozásban létezik a rekurzió fogalma - amikor egy függvény önmagát hívja.

Példa . Egyszerű rekurzió számlálóval

Jelenítsünk meg rekurzióval számokat 1-től 10-ig:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # itt a függvény önmagát hívja
		
	func()

Beszéljük meg, hogyan működik ez a kód.

Van egy globális i változónk és egy func függvényünk, amelynek belsejében a konzolra kiíródik a i változó tartalma, majd hozzáadunk egyet.

Ha a i változónk kisebb vagy egyenlő, mint 10, akkor a függvény újra meghívódik. Mivel a i változó globális, minden új függvényhívásnál az előző hívásban beállított érték lesz benne.

Így a függvény addig hívja önmagát, amíg a i nem lesz nagyobb, mint 10.

Vegye figyelembe, hogy esetünkben a függvényt nem indíthatjuk if nélkül - ha ezt megteszi, akkor végtelen függvényhívás lesz belőle.

Példa . Rekurzió beágyazott listák elemeinek kiírására

A rekurziókat leggyakrabban különböző beágyazási szintű listák bejárására használják. Tegyük fel, hogy a következő listánk van:

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

Készítsünk egy függvényt, amely bejárja. Először meg kell adni egy feltételt, hogy a primitív elem, azaz a listából kinyert egyszerű szám, ki legyen írva a konzolra. Ha viszont az elem egy objektum, például egy beágyazott lista, akkor ebben az esetben hívja meg a függvény önmagát, azaz rekurzió történjen. Az elem típusának ellenőrzéséhez használjuk a isinstance függvényt. Csak a példánkban az első paraméterben isinstance-nek írjuk a el-t, a másodikban pedig a list típust:

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

A függvény meghívásakor a beágyazott lista összes száma kiíródik:

func(lst) # kiírja: 1, 2, ... 8, 9

Példa . Rekurzió beágyazott listák elemeivel végzett műveletekre

A rekurzió különböző műveletekhez is használható a beágyazott listák elemeivel. Tegyük fel, hogy a következő listánk van:

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

Kapjuk meg az összes elem összegét. Ehhez a függvényben deklaráljunk egy res változót, amelybe a számok összege gyűlik. A feltételben állítsuk be, hogy ha egy elem összetett objektum, akkor az a func függvény paramétereként kerül be és hozzáadódik az összeghez. Ez azt jelenti, hogy az elem rekurzióban lesz, amíg primitívvé nem válik. És ebben az esetben egyszerűen hozzáadódik a res-ben található összeghez:

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

Hívjuk meg a függvényt és írjuk ki az eredményét a konzolra:

print(func(lst)) # kiírja: 45

Példa . Rekurzió listába gyűjtésre

Rekurzióval a beágyazott listákat egy egydimenziós listává lehet alakítani. Tegyük fel, hogy a következő listánk van:

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

Írjunk a függvénybe egy üres res listát, amelybe az eredeti lista elemei gyűlnek. Ezután indítsunk el egy ciklust és adjunk meg egy feltételt - ha egy elem lista, akkor az kerüljön a extend metódusba. Ez a metódus egy lista elemeit egy másik lista végéhez fűzi, azaz a beágyazott lista elemei a res lista végéhez kerülnek:

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))

A végrehajtott kód eredménye:

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

Gyakorlati feladatok

Írja ki egy tetszőleges beágyazási szintű szótár összes numerikus elemét:

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

Keresse meg az előző feladat szótárának elemeinek összegét.

Kapja meg az előző feladat szótárának primitív elemeiből álló listát.