Recursivitate în Python

În programare există un concept numit recursivitate - atunci când o funcție se autoapelează.

Exemplu . Recursivitate simplă cu contor

Să afișăm numerele de la 1 la 10 folosind recursivitatea:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # aici funcția se autoapelează
		
	func()

Să discutăm cum funcționează acest cod.

Avem variabila globală i și funcția func, în interiorul căreia se afișează în consolă conținutul variabilei i, apoi i se adaugă o unitate.

Dacă variabila noastră i este mai mică sau egală cu 10, atunci funcția este apelată din nou. Deoarece variabila i este globală, la fiecare nou apel al funcției va conține valoarea stabilită la apelul anterior.

Se va întâmpla ca funcția să se autoapeleze până când i devine mai mare decât 10.

Rețineți că în cazul nostru nu putem apela funcția fără if - dacă facem acest lucru, vom obține un apel infinit de funcții.

Exemplu . Recursivitate pentru afișarea elementelor din liste imbricate

Cel mai des recursivitatea este aplicată pentru parcurgerea listelor cu diferite grade de imbricare. Să presupunem că avem următoarea listă:

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

Să creăm o funcție care o va parcurge. În ea trebuie mai întâi să stabilim o condiție ca elementul care este un primitiv, adică un număr extras simplu din listă, să fie afișat în consolă. Iar dacă elementul este un obiect complex, de exemplu o listă imbricată, atunci în acest caz funcția să se autoapeleze, adică să aibă loc recursivitatea. Pentru verificarea tipului elementului vom folosi funcția isinstance. Doar pentru exemplul nostru în primul parametru al isinstance vom scrie el, iar al doilea - tipul list:

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

La apelarea funcției se va afișa șirul tuturor numerelor din lista imbricată:

func(lst) # va afișa 1, 2, ... 8, 9

Exemplu . Recursivitate pentru operații cu elemente din liste imbricate

Recursivitatea poate fi aplicată și pentru diverse operații cu elementele din liste imbricate. Să presupunem că avem următoarea listă:

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

Să obținem suma tuturor elementelor sale. Pentru aceasta, în funcție vom declara variabila res, în care se va acumula suma numerelor. În condiție vom specifica că dacă elementul este un obiect complex, atunci acesta intră ca parametru al funcției func și se adaugă la sumă. Aceasta înseamnă că elementul va fi prelucrat recursiv până devine primitiv. Și în acest caz el va fi pur și simplu adăugat la suma scrisă în res:

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

Să apelăm funcția și să afișăm rezultatul ei în consolă:

print(func(lst)) # va afișa 45

Exemplu . Recursivitate pentru acumulare în listă

Cu ajutorul recursivității putem desfășura listele imbricate într-o singură listă unidimensională. Să presupunem că avem următoarea listă:

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

Să specificăm în funcție o listă goală res, în care se vor acumula elementele listei inițiale. Apoi vom porni un ciclu și vom stabili o condiție - dacă elementul este o listă, atunci acesta va intra în metoda extend. Această metodă atașează elementele unei liste la sfârșitul celei de-a doua liste, adică elementele listei imbricate vor fi adăugate la sfârșitul listei 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))

Rezultatul codului executat:

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

Probleme practice

Afișați toate elementele numerice ale unui dicționar cu un nivel arbitrar de imbricare:

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

Găsiți suma elementelor dicționarului din problema anterioară.

Obțineți lista elementelor primitive ale dicționarului din problema anterioară.