Rekursie in Python

In programmering is daar so 'n konsep soos rekursie - wanneer 'n funksie hulself oproep.

Voorbeeld . Eenvoudige rekursie met 'n teller

Kom ons wys getalle van 1 tot 10 met behulp van rekursie:

i = 1

def func():
	global i
	print(i)
	i += 1

	if i <= 10:
		func() # hier roep die funksie haarself op

func()

Kom ons bespreek hoe hierdie kode werk.

Ons het 'n globale veranderlike i en 'n funksie func, binne-in wat die inhoud van die veranderlike i na die konsole uitvoer, en dan word 'n eenheid daaraan toegevoeg.

As ons veranderlike i minder as of gelyk aan 10 is, word die funksie weer opgeroep. Aangesien die veranderlike i globaal is, sal dit by elke nuwe funksie-oproep die waarde van die veranderlike i hê wat by die vorige oproep gestel is.

Dit sal gebeur dat die funksie haarself sal oproep totdat i groter as 10 word.

Let op, in ons geval kan die funksie nie sonder if begin nie - as jy dit doen, sal dit 'n oneindige oproep van funksies wees.

Voorbeeld . Rekursie om elemente van geneste lyste uit te voer

Rekursie word meestal gebruik om lyste van verskillende vlakke van invoeging te deurloop. Kom ons sê ons het die volgende lys:

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

Kom ons skep 'n funksie wat dit sal deurloop. Eerstens moet jy 'n voorwaarde skep, sodat die element wat 'n primitief is, d.w.s. net 'n getal uit die lys gehaal, in die konsole vertoon word. En as die element 'n voorwerp is, byvoorbeeld 'n geneste lys, laat in hierdie geval die funksie haarself oproep, d.w.s. rekursie sal plaasvind. Om die tipe element te kontroleer, gebruik die funksie isinstance. Slegs vir ons voorbeeld, in die eerste parameter isinstance, skryf ons el, en die tweede - tipe list:

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

Wanneer die funksie opgeroep word, sal 'n reeks van al die getalle uit die geneste lys vertoon word:

func(lst) # wys 1, 2, ... 8, 9

Voorbeeld . Rekursie vir operasies met elemente van geneste lyste

Rekursie kan ook gebruik word vir verskeie operasies met elemente van geneste lyste. Kom ons sê ons het die volgende lys:

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

Kom ons kry die som van al sy elemente. Om dit te doen, verklaar 'n veranderlike res in die funksie, waarin die som van getalle sal ophoop. In die voorwaarde skryf ons dat as die element 'n komplekse voorwerp is, sal dit in die funksie parameter func val en by die som gevoeg word. Dit beteken dat die element sal in rekursie wees totdat dit 'n primitief word. En in hierdie geval sal dit net by die som gevoeg word, geskryf in res:

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

Kom ons roep die funksie op en voer die resultaat daarvan na die konsole uit:

print(func(lst)) # wys 45

Voorbeeld . Rekursie om in 'n lys op te bou

Met behulp van rekursie kan jy geneste lyste in een eendimensionele lys uitbrei. Kom ons sê ons het die volgende lys:

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

Kom ons skryf 'n leë lys res in die funksie, waarin die elemente van die oorspronklike lys sal ophoop. Dan begin ons 'n lus en stel 'n voorwaarde - as die element 'n lys is, sal dit in die metode extend val. Hierdie metode heg die elemente van een lys aan die einde van 'n tweede lys, d.w.s. die elemente van die geneste lys sal aan die einde van die lys res val:

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

Die resultaat van die uitgevoerde kode:

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

Praktiese take

Voer alle numeriese elemente van 'n woordeboek met arbitrêre vlakke van invoeging uit:

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

Vind die som van die elemente van die woordeboek uit die vorige taak.

Kry 'n lys van primitiewe elemente van die woordeboek uit die vorige taak.