Rekursioni në Python

Në programim ekziston koncepti i rekursionit - kur një funksion thërret vetveten.

Shembull . Rekursion i thjeshtë me numërues

Le të shfaqim numrat nga 1 në 10 duke përdorur rekursion:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # këtu funksioni thërret vetveten
		
	func()

Le të diskutojmë se si funksionon ky kod.

Kemi një ndryshore globale i dhe një funksion func, brenda të cilit në konsol shfaqet përmbajtja e ndryshores i, dhe pastaj i shtohet një.

Nëse ndryshorja jonë i është më e vogël ose e barabartë me 10, atëherë funksioni thirret përsëri. Meqenëse ndryshorja i - është globale, atëherë në çdo thirrje të re të funksionit në të do të ketë vlerën e caktuar në thirrjen e mëparshme të ndryshores i.

Do të rezultojë se funksioni do të thërrasë vetveten derisa i të bëhet më e madhe se 10.

Kini parasysh që në rastin tonë nuk mundet funksioni të niset pa if - nëse bëhet kështu, do të fitohet një thirrje e pafundme e funksioneve.

Shembull . Rekursion për shfaqjen e elementeve të listave të mbivendosura

Më shpesh rekursionet përdoren për kalimin nëpër lista të shkallëve të ndryshme të mbivendosjes. Le të themi se kemi listën e mëposhtme:

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

Le të krijojmë një funksion që do të kalojë nëpër të. Në të fillim duhet vendosur kushti, që elementi, i cili është primitiv, d.m.th. thjesht një numër i nxjerrë nga lista, të shfaqet në konsol. Dhe nëse elementi është një objekt, për shembull, një listë e mbivendosur, atëherë në këtë rast le të thërret funksioni vetveten, d.m.th. të ndodhë rekursion. Për të kontrolluar llojin e elementit le të përdorim funksionin isinstance. Vetëm për shembullin tonë në parametrin e parë të isinstance do të shkruajmë el, dhe i dyti - llojin list:

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

Gjatë thirrjes së funksionit do të shfaqet një varg i të gjithë numrave nga lista e mbivendosur:

func(lst) # do të shfaqë 1, 2, ... 8, 9

Shembull . Rekursion për operacione me elementët e listave të mbivendosura

Rekursionet mund të përdoren edhe për operacione të ndryshme me elementët e listave të mbivendosura. Le të themi se kemi listën e mëposhtme:

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

Le të gjejmë shumën e të gjithë elementëve të saj. Për këtë, në funksion le të deklarojmë një ndryshore res, në të cilën do të grumbullohet shuma e numrave. Në kusht do të shkruajmë, se nëse elementi është një objekt kompleks, atëherë ai hyn në parametrin e funksionit func dhe i shtohet shumës. Kjo do të thotë se elementi do të jetë në rekursion derisa të bëhet primitiv. Dhe në këtë rast ai thjesht do t'i shtohet shumës, të shkruar në res:

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

Le të thërrasim funksionin dhe të shfaqim rezultatin e tij në konsol:

print(func(lst)) # do të shfaqë 45

Shembull . Rekursion për grumbullim në listë

Me ndihmën e rekursionit mund të shndërrohen listat e mbivendosura në një listë njëdimensionale. Le të themi se kemi listën e mëposhtme:

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

Le të shkruajmë në funksion një listë të zbrazët res, në të cilën do të grumbullohen elementët e listës fillestare. Pastaj le të nisim unazën dhe të vendosim kushtin - nëse elementi është një listë, atëherë ai do të hyjë në metodën extend. Kjo metodë bashkëngjit elementët e një liste në fund të listës së dytë, d.m.th. elementët e listës së mbivendosur do të hyjnë në fund të listës 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))

Rezultati i kodit të ekzekutuar:

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

Detyra praktike

Shfaqni të gjithë elementët numerikë të fjalorit të çdo niveli mbivendosjeje:

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

Gjeni shumën e elementëve të fjalorit nga detyra e mëparshme.

Merrni një listë të elementëve primitivë të fjalorit nga detyra e mëparshme.