Rekursion i Python

Inom programmering finns det ett koncept som kallas rekursion - när en funktion anropar sig själv.

Exempel . Enkel rekursion med räknare

Låt oss skriva ut tal från 1 till 10 med hjälp av rekursion:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # här anropar funktionen sig själv
		
	func()

Låt oss diskutera hur den här koden fungerar.

Vi har en global variabel i och en funktion func, inuti vilken innehållet i variabeln i skrivs ut till konsolen, och sedan ökas den med ett.

Om vår variabel i är mindre eller lika med 10, anropas funktionen igen. Eftersom variabeln i är global, kommer den vid varje nytt anrop av funktionen ha det värde som satts vid föregående anrop av variabeln i.

Resultatet blir att funktionen kommer att anropa sig själv tills i blir större än 10.

Tänk på att i vårt fall kan funktionen inte startas utan if - om man gör det blir det ett oändligt anrop av funktioner.

Exempel . Rekursion för att skriva ut element i nästlade listor

Rekursion används oftast för att gå igenom listor med olika nivåer av nästling. Låt oss säga att vi har följande lista:

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

Låt oss skapa en funktion som går igenom den. I den behöver vi först sätta ett villkor så att elementet som är en primitiv, d.v.s. bara ett tal extraherat från listan, skrivs ut till konsolen. Och om elementet är ett objekt, till exempel en nästlad lista, låt i det fallet funktionen anropa sig själv, d.v.s. en rekursion sker. För att kontrollera typ av element använder vi funktionen isinstance. Bara för vårt exempel i den första parametern isinstance skriver vi el, och den andra - typen list:

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

När funktionen anropas kommer en rad med alla tal från den nästlade listan att skrivas ut:

func(lst) # skriver ut 1, 2, ... 8, 9

Exempel . Rekursion för operationer med element i nästlade listor

Rekursion kan också användas för olika operationer med element i nästlade listor. Låt oss säga att vi har följande lista:

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

Låt oss få summan av alla dess element. För att göra detta, deklarera en variabel res i funktionen, i vilken summan av talen kommer ackumuleras. I villkoret skriver vi att om elementet är ett komplext objekt, så hamnar det i funktionsparametern func och adderas till summan. Det betyder att elementet kommer att vara i rekursion tills det blir en primitiv. Och i det fallet kommer det bara att adderas till summan som skrivs i res:

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

Låt oss anropa funktionen och skriva ut dess resultat till konsolen:

print(func(lst)) # skriver ut 45

Exempel . Rekursion för ackumulering till en lista

Med hjälp av rekursion kan man lägga ut nästlade listor i en enda endimensionell lista. Låt oss säga att vi har följande lista:

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

Låt oss skriva en tom lista res i funktionen, i vilken element från originallistan kommer ackumuleras. Sedan startar vi en loop och sätter ett villkor - om elementet är en lista, så hamnar det i metoden extend. Denna metod fäster element från en lista i slutet av en andra lista, d.v.s. element från den nästlade listan hamnar i slutet av listan 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))

Resultatet av den utförda koden:

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

Praktiska uppgifter

Skriv ut alla numeriska element i en ordbok med godtycklig nivå av nästling:

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

Hitta summan av elementen i ordboken från föregående uppgift.

Få en lista med primitiva element i ordboken från föregående uppgift.