Recursie in Python

In programmeren bestaat het concept recursie - wanneer een functie zichzelf aanroept.

Voorbeeld . Eenvoudige recursie met teller

Laten we met behulp van recursie getallen van 1 tot 10 weergeven:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # hier roept de functie zichzelf aan
		
	func()

Laten we bespreken hoe deze code werkt.

We hebben een globale variabele i en een functie func, waarin de inhoud van de variabele i naar de console wordt uitgevoerd, en er vervolgens één wordt bij opgeteld.

Als onze variabele i kleiner dan of gelijk aan 10 is, wordt de functie opnieuw aangeroepen. Omdat de variabele i globaal is, zal bij elke nieuwe aanroep van de functie de waarde van de variabele i, ingesteld tijdens de vorige aanroep, erin zitten.

Het resultaat is dat de functie zichzelf zal blijven aanroepen totdat i groter wordt dan 10.

Houd er rekening mee dat het in ons geval niet mogelijk is de functie te starten zonder if - als dit wordt gedaan, resulteert dit in een oneindige aanroep van functies.

Voorbeeld . Recursie voor het weergeven van elementen van geneste lijsten

Recursie wordt het meest gebruikt voor het doorlopen van lijsten met verschillende nestingsniveaus. Stel we hebben de volgende lijst:

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

Laten we een functie maken die deze doorloopt. Er moet eerst een voorwaarde worden gesteld, zodat het element dat een primitief is, d.w.z. simpelweg een uit de lijst gehaald getal, naar de console wordt uitgevoerd. En als het element een object is, bijvoorbeeld een geneste lijst, laat de functie in dat geval zichzelf aanroepen, d.w.z. er treedt recursie op. Om het type element te controleren gebruiken we de functie isinstance. Alleen voor ons voorbeeld schrijven we in de eerste parameter van isinstance el, en als tweede - het type list:

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

Bij het aanroepen van de functie wordt een reeks van alle getallen uit de geneste lijst weergegeven:

func(lst) # geeft 1, 2, ... 8, 9 weer

Voorbeeld . Recursie voor bewerkingen met elementen van geneste lijsten

Recursie kan ook worden gebruikt voor verschillende bewerkingen met elementen van geneste lijsten. Stel we hebben de volgende lijst:

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

Laten we de som van al zijn elementen verkrijgen. Declareer hiervoor in de functie een variabele res, waarin de som van de getallen wordt opgehoopt. Stel in de voorwaarde dat als het element een complex object is, het in de parameter van de functie func terechtkomt en wordt opgeteld bij de som. Dit betekent dat het element in recursie blijft totdat het een primitief wordt. En in dat geval wordt het simpelweg opgeteld bij de som, geschreven in res:

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

Laten we de functie aanroepen en het resultaat ervan naar de console uitvoeren:

print(func(lst)) # geeft 45 weer

Voorbeeld . Recursie voor accumulatie in een lijst

Met behulp van recursie kunnen geneste lijsten worden uitgevouwen tot één ééndimensionale lijst. Stel we hebben de volgende lijst:

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

Laten we in de functie een lege lijst res declareren, waarin de elementen van de oorspronkelijke lijst worden opgehoopt. Start vervolgens een lus en stel een voorwaarde - als het element een lijst is, komt het terecht in de methode extend. Deze methode voegt de elementen van de ene lijst toe aan het einde van de tweede lijst, d.w.z. de elementen van de geneste lijst komen aan het einde van de lijst res terecht:

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

Het resultaat van de uitgevoerde code:

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

Praktische opdrachten

Geef alle numerieke elementen weer van een woordenboek met een willekeurig nestingsniveau:

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

Bereken de som van de elementen van het woordenboek uit de vorige opdracht.

Verkrijg een lijst met de primitieve elementen van het woordenboek uit de vorige opdracht.