Rekursija Python'e

Programavime yra tokia sąvoka kaip rekursija – kai funkcija iškviečia pati save.

Pavyzdys . Paprasta rekursija su skaitikliu

Panaudokime rekursiją, kad išvestume skaičius nuo 1 iki 10:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # čia funkcija iškviečia pati save
		
	func()

Aptarkime, kaip šis kodas veikia.

Mes turime globalų kintamąjį i ir funkciją func, kurios viduje į konsolę išvedama kintamojo i reikšmė, o tada prie jo pridedamas vienetas.

Jei mūsų kintamasis i yra mažesnis arba lygus 10, tada funkcija iškviečiama dar kartą. Kadangi kintamasis i – globalus, tai kiekvienu nauju funkcijos iškvietimu jame bus ankstesniame iškvietime nustatyta kintamojo i reikšmė.

Pasirodo, kad funkcija iškviestų pati save tol, kol i netaps didesnis už 10.

Atminkite, kad mūsų atveju negalima funkcijos paleisti be if – jei tai padaryti, gausis begalinis funkcijų iškvietimas.

Pavyzdys . Rekursija įdėtų sąrašų elementų išvedimui

Rekursijos dažniausiai naudojamos įvairių gilumų sąrašų peržiūrai. Tarkime, kad turime tokį sąrašą:

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

Sukurkime funkciją, kuri jį peržiūrės. Joje pirmiausia reikia nustatyti sąlygą, kad elementas, kuris yra primityvas, t.y. tiesiog iš sąrašo išimtas skaičius, būtų išvestas į konsolę. O jei elementas yra sudėtingas objektas, pavyzdžiui, įdėtas sąrašas, tai tokiu atveju tegul funkcija iškviečia pati save, t.y. įvyks rekursija. Elemento tipo patikrinimui panaudokime funkciją isinstance. Tik mūsų pavyzdyje į pirmą parametrą isinstance įrašykime el, o antruoju – tipą list:

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

Iškvietus funkciją, bus išvesta visų skaičių iš įdėto sąrašo eilė:

func(lst) # išves 1, 2, ... 8, 9

Pavyzdys . Rekursija operacijoms su įdėtų sąrašų elementais

Rekursijas galima taikyti ir įvairioms operacijoms su įdėtų sąrašų elementais. Tarkime, kad turime tokį sąrašą:

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

Gaukime visų jo elementų sumą. Tam funkcijoje deklaruosime kintamąjį res, į kurį bus kaupiama skaičių suma. Sąlygoje parašykime, kad jei elementas yra sudėtingas objektas, tai jis pateks į funkcijos parametrą func ir bus pridėtas prie sumos. Tai reiškia, kad elementas liks rekursijoje tol, kol taps primityvu. Ir tokiu atveju jis tiesiog bus pridėtas prie sumos, įrašytos į res:

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

Iškvieskime funkciją ir išveskime jos rezultatą į konsolę:

print(func(lst)) # išves 45

Pavyzdys . Rekursija kaupimui į sąrašą

Naudojant rekursiją, galima išskleisti įdėtus sąrašus į vieną vienmatį sąrašą. Tarkime, kad turime tokį sąrašą:

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

Funkcijoje parašykime tuščią sąrašą res, į kurį bus surenkami pradinio sąrašo elementai. Tada paleiskime ciklą ir nustatykime sąlygą – jei elementas yra sąrašas, tai jis pateks į metodą extend. Šis metodas prijungia vieno sąrašo elementus kito sąrašo galą, t.y. įdėto sąrašo elementai pateks į sąrašo res galą:

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

Vykdyto kodo rezultatas:

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

Praktinės užduotys

Išveskite visus skaitinius žodyno elementus savavališko gilumo:

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

Raskite ankstesnės užduoties žodyno elementų sumą.

Gaukite ankstesnės užduoties žodyno primityvųjų elementų sąrašą.