Rekursion i Python

I programmering findes der et koncept kaldet rekursion - når en funktion kalder sig selv.

Eksempel . Simpel rekursion med tæller

Lad os ved hjælp af rekursion udskrive tal fra 1 til 10:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # her kalder funktionen sig selv
		
	func()

Lad os diskutere, hvordan denne kode fungerer.

Vi har en global variabel i og en funktion func, inden i hvilken indholdet af variablen i udskrives til konsollen, og derefter lægges der en enhed til.

Hvis vores variabel i er mindre eller lig med 10, kaldes funktionen igen. Da variablen i er global, vil den ved hvert nyt kald af funktionen have den værdi af variablen i, der blev sat i det foregående kald.

Resultatet bliver, at funktionen vil kalde sig selv indtil i bliver større end 10.

Bemærk, at vi i dette tilfælde ikke kan starte funktionen uden if - hvis dette gøres, får man et uendeligt kald af funktioner.

Eksempel . Rekursion til udskrivning af elementer i indlejrede lister

Rekursion anvendes mest ofte til at gennemgå lister med forskellig indlejringsniveau. Lad os sige, at vi har følgende liste:

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

Lad os oprette en funktion, der gennemgår den. I den skal vi først angive en betingelse, så elementet, som er en primitiv type, dvs. simpelthen et tal trukket ud af listen, udskrives til konsollen. Og hvis elementet er et komplekst objekt, for eksempel en indlejret liste, så lad funktionen i dette tilfælde kalde sig selv, dvs. der sker en rekursion. For at kontrollere typen af elementet anvender vi funktionen isinstance. Kun til vores eksempel skriver vi i den første parameter isinstance el, og den anden - typen list:

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

Ved kald af funktionen udskrives en række af alle tal fra den indlejrede liste:

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

Eksempel . Rekursion til operationer med elementer i indlejrede lister

Rekursion kan også anvendes til forskellige operationer med elementer i indlejrede lister. Lad os sige, at vi har følgende liste:

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

Lad os finde summen af alle dens elementer. Til dette erklærer vi i funktionen en variabel res, hvor summen af tal vil akkumuleres. I betingelsen skriver vi, at hvis elementet er et komplekst objekt, så kommer det i funktionsparameteren func og lægges til summen. Dette betyder, at elementet vil være i rekursion indtil det bliver en primitiv type. Og i dette tilfælde vil det simpelthen lægges til summen, der er skrevet i res:

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

Lad os kalde funktionen og udskrive dens resultat til konsollen:

print(func(lst)) # udskriver 45

Eksempel . Rekursion til akkumulering i en liste

Med rekursion kan man udfolde indlejrede lister til én én-dimensional liste. Lad os sige, at vi har følgende liste:

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

Lad os i funktionen skrive en tom liste res, hvor elementerne fra den oprindelige liste vil blive akkumuleret. Derefter starter vi en løkke og angiver en betingelse - hvis elementet er en liste, så kommer det i metoden extend. Denne metode tilføjer elementerne fra én liste til slutningen af en anden liste, dvs. elementerne fra den indlejrede liste kommer til slutningen af listen 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 af den udførte kode:

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

Praktiske opgaver

Udskriv alle numeriske elementer i en ordbog med et vilkårligt indlejringsniveau:

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

Find summen af elementerne i ordbogen fra den foregående opgave.

Få en liste over de primitive elementer i ordbogen fra den foregående opgave.