Rekursioon Pythonis

Programmeerimises on selline mõiste nagu rekursioon - kui funktsioon kutsub välja iseennast.

Näide . Lihtne rekursioon loenduriga

Väljastame rekursiooni abil numbrid 1 kuni 10:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # siin kutsub funktsioon välja iseennast
		
	func()

Arutleme, kuidas see kood töötab.

Meil on globaalne muutuja i ja funktsioon func, mille sees väljastatakse konsooli muutuja i sisu, millele seejärel liidetakse üks.

Kui meie muutuja i on väiksem või võrdne kui 10, siis kutsutakse funktsioon uuesti välja. Kuna muutuja i on globaalne, siis iga uue funktsiooni väljakutsega on selles eelmisel väljakutsel seatud muutuja i väärtus.

Tulemuseks on, et funktsioon kutsub iseennast välja kuni i muutub suuremaks kui 10.

Pidage meeles, et meie juhul ei saa funktsiooni käivitada ilma if-ita - kui seda teha, siis saadakse lõputu funktsioonide väljakutsete ahel.

Näide . Rekursioon pesastatud loendite elementide väljastamiseks

Kõige sagedamini kasutatakse rekursioone erineva pesastustasemega loendite läbimiseks. Olgu meil järgmine loend:

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

Loome funktsiooni, mis käib selle läbi. Selles tuleb esmalt seada tingimus, et element, mis on primitiiv, st lihtsalt loendist eraldatud number, väljastataks konsooli. Ja kui element on keerukam objekt, näiteks pesastatud loend, siis sellisel juhul kutsku funktsioon välja iseennast, st toimub rekursioon. Elemendi tüübi kontrollimiseks kasutame funktsiooni isinstance. Ainult meie näites kirjutame esimeseks parameetriks isinstance el, ja teiseks - tüübi list:

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

Funktsiooni väljakutsel väljastatakse kõik numbrid pesastatud loendist:

func(lst) # väljastab 1, 2, ... 8, 9

Näide . Rekursioon pesastatud loendite elementidega toiminguteks

Rekursioone saab kasutada ka mitmesuguste toimingute tegemiseks pesastatud loendite elementidega. Olgu meil järgmine loend:

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

Leiame kõigi selle elementide summa. Selleks deklareerime funktsioonis muutuja res, millesse koguneb numbrite summa. Tingimuses kirjutame, et kui element on keerukam objekt, siis see läheb funktsiooni func parameetriks ja liidetakse summale. See tähendab, et element jääb rekursiooni, kuni sellest saab primitiiv. Ja sel juhul liidetakse see lihtsalt summale, mis on kirjutatud res-i:

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

Kutsume funktsiooni välja ja väljastame selle tulemi konsooli:

print(func(lst)) # väljastab 45

Näide . Rekursioon kogumiseks loendisse

Rekursiooni abil saab pesastatud loendid lahti pakkida üheks ühemõõtmeliseks loendiks. Olgu meil järgmine loend:

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

Kirjutame funktsiooni tühja loendi res, millesse kogunevad algse loendi elemendid. Seejärel käivitame tsükli ja seame tingimuse - kui element on loend, siis see läheb meetodisse extend. See meetod ühendab ühe loendi elemendid teise loendi lõppu, st pesastatud loendi elemendid lähevad loendi res lõppu:

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

Täidetud koodi tulemus:

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

Praktilised ülesanded

Väljastage kõik sõnastiku numbrilised elemendid suvalise pesastustasemega:

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

Leidke eelmise ülesande sõnastiku elementide summa.

Hankige eelmise ülesande sõnastiku primitiivsete elementide loend.