Rekursion i Python

I programmering finnes det et konsept kalt rekursion - når en funksjon kaller seg selv.

Eksempel . Enkel rekursion med teller

La oss skrive ut tall fra 1 til 10 ved hjelp av rekursion:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # her kaller funksjonen seg selv
		
	func()

La oss diskutere hvordan denne koden fungerer.

Vi har en global variabel i og en funksjon func, inni der innholdet av variabelen i skrives ut til konsollen, og deretter økes den med én.

Hvis variabelen vår i er mindre enn eller lik 10, kalles funksjonen på nytt. Siden variabelen i er global, vil den for hvert nye funksjonskall ha verdien som ble satt i forrige kall av variabelen i.

Resultatet blir at funksjonen vil kalle seg selv inntil i blir større enn 10.

Vær oppmerksom på at i vårt tilfelle kan ikke funksjonen startes uten if - hvis dette gjøres, vil det resultere i et uendelig rekursivt kall av funksjoner.

Eksempel . Rekursion for å skrive ut elementer i nestede lister

Rekursion brukes mest ofte for å gå gjennom lister med ulike nivåer av nesting. La oss si at vi har følgende liste:

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

La oss lage en funksjon som går gjennom den. I den må vi først sette en betingelse for at et element som er en primitiv, dvs. bare et tall hentet fra listen, skal skrives ut til konsollen. Og hvis elementet er et komplekst objekt, for eksempel en nested liste, la funksjonen i dette tilfellet kalle seg selv, dvs. det vil skje en rekursion. For å sjekke typen av element bruker vi funksjonen isinstance. Bare for vårt eksempel skriver vi el i den første parameteren til isinstance, og den andre - typen list:

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

Når funksjonen kalles, vil en rekke med alle tallene fra den nestede listen bli skrevet ut:

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

Eksempel . Rekursion for operasjoner med elementer i nestede lister

Rekursion kan også brukes for ulike operasjoner med elementer i nestede lister. La oss si at vi har følgende liste:

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

La oss finne summen av alle dens elementer. For å gjøre dette, deklarerer vi en variabel res i funksjonen, der summen av tallene vil akkumuleres. I betingelsen spesifiserer vi at hvis elementet er et komplekst objekt, går det inn i parameteren til funksjonen func og legges til i summen. Dette betyr at elementet vil være i rekursion inntil det blir en primitiv. Og i dette tilfellet vil det bare legges til summen som 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

La oss kalle funksjonen og skrive ut dens resultat til konsollen:

print(func(lst)) # skriver ut 45

Eksempel . Rekursion for akkumulering i en liste

Med rekursion kan du pakke ut nestede lister til én endimensjonal liste. La oss si at vi har følgende liste:

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

La oss definere en tom liste res i funksjonen, der elementene fra kildelisten vil akkumuleres. Deretter starter vi en løkke og setter en betingelse - hvis elementet er en liste, går det inn i metoden extend. Denne metoden kobler sammen elementene i én liste på slutten av en annen liste, dvs. elementene i den nestede listen vil havne på slutten av 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 av den utførte koden:

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

Praktiske oppgaver

Skriv ut alle numeriske elementer i en ordbok med vilkårlig nivå av nesting:

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

Finn summen av elementene i ordboken fra forrige oppgave.

Få en liste over de primitive elementene i ordboken fra forrige oppgave.