Rekursija Python

Programmēšanā pastāv tāds jēdziens kā rekursija - kad funkcija izsauc pati sevi.

Piemērs . Vienkārša rekursija ar skaitītāju

Izmantosim rekursiju, lai izvadītu skaitļus no 1 līdz 10:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # šeit funkcija izsauc pati sevi
		
	func()

Apspriedīsim, kā šis kods darbojas.

Mums ir globālais mainīgais i un funkcija func, kuras iekšienē konsole tiek izvadīts mainīgā i saturs, un pēc tam tam tiek pieskaitīta vieninieks.

Ja mūsu mainīgais i ir mazāks vai vienāds ar 10, tad funkcija tiek izsaukta atkārtoti. Tā kā mainīgais i - globāls, tad ar katru jaunu funkcijas izsaukšanu tajā būs iepriekšējā izsaukumā iestatītā mainīgā i vērtība.

Izrādīsies, ka funkcija izsauks pati sevi līdz brīdim, kad i kļūs lielāks par 10.

Ņemiet vērā, ka mūsu gadījumā nevar funkciju palaist bez if - ja to izdarītu, tad iegūtu bezgalīgu funkciju izsaukšanu.

Piemērs . Rekursija elementu izvadei iegultajos sarakstos

Visbiežāk rekursijas tiek izmantotas sarakstu ar dažādu iegulšanas pakāpju pārlasei. Pieņemsim, ka mums ir šāds saraksts:

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

Izveidosim funkciju, kas to pārlās. Vispirms tajā jāiestata nosacījums, lai elements, kas ir primitīvs, t.i., vienkārši no saraksta izvilkts skaitlis, tiktu izvadīts konsolē. Un, ja elements ir sarežģīts objekts, piemēram, iegults saraksts, tad šajā gadījumā lai funkcija izsauc pati sevi, t.i., notiks rekursija. Lai pārbaudītu elementa tipu, izmantosim funkciju isinstance. Tikai mūsu piemēram pirmajā parametrā isinstance ierakstīsim el, un otrā - tipu list:

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

Izsakot funkciju, tiks izvadīta visu skaitļu sērija no iegultā saraksta:

func(lst) # izvadīs 1, 2, ... 8, 9

Piemērs . Rekursija operācijām ar elementiem iegultajos sarakstos

Rekursijas var izmantot arī dažādām darbībām ar elementiem iegultajos sarakstos. Pieņemsim, ka mums ir šāds saraksts:

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

Iegūsim visu tā elementu summu. Lai to izdarītu, funkcijā deklarēsim mainīgo res, kurā tiks uzkrāta skaitļu summa. Nosacījumā ierakstīsim, ka, ja elements ir sarežģīts objekts, tad tas nonāk funkcijas parametrā func un tiek pieskaitīts summai. Tas nozīmē, ka elements būs rekursijā līdz kļūs primitīvs. Un šajā gadījumā tas vienkārši tiks pieskaitīts summai, kas ierakstīta res:

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

Izsauksim funkciju un izvadīsim tās rezultātu konsolē:

print(func(lst)) # izvadīs 45

Piemērs . Rekursija uzkrāšanai sarakstā

Izmantojot rekursiju, var izkļaut iegultos sarakstus vienā viendimensijas sarakstā. Pieņemsim, ka mums ir šāds saraksts:

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

Funkcijā ierakstīsim tukšu sarakstu res, kurā tiks uzkrāti sākotnējā saraksta elementi. Pēc tam palaidīsim ciklu un iestatīsim nosacījumu - ja elements ir saraksts, tad tas nonāk metodē extend. Šī metode pievieno viena saraksta elementus otrā saraksta beigās, t.i., iegultā saraksta elementi nonāks saraksta res beigās:

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

Izpildītā koda rezultāts:

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

Praktiskie uzdevumi

Izvadiet visus vārdnīcas skaitliskos elementus patvaļīgā iegulšanas līmenī:

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

Atrodiet iepriekšējā uzdevuma vārdnīcas elementu summu.

Iegūstiet iepriekšējā uzdevuma vārdnīcas primitīvo elementu sarakstu.