Rekursion in Python

In der Programmierung gibt es das Konzept der Rekursion - wenn eine Funktion sich selbst aufruft.

Beispiel . Einfache Rekursion mit Zähler

Lassen Sie uns mit Hilfe der Rekursion Zahlen von 1 bis 10 ausgeben:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # hier ruft die Funktion sich selbst auf
		
	func()

Lassen Sie uns besprechen, wie dieser Code funktioniert.

Wir haben eine globale Variable i und eine Funktion func, innerhalb derer der Inhalt der Variable i in die Konsole ausgegeben wird, und dann wird eins dazu addiert.

Wenn unsere Variable i kleiner oder gleich 10 ist, wird die Funktion erneut aufgerufen. Da die Variable i - global ist, wird bei jedem neuen Aufruf der Funktion darin der beim vorherigen Aufruf gesetzte Wert der Variable i enthalten sein.

Es wird sich ergeben, dass die Funktion sich selbst so lange aufruft, bis i größer als 10 wird.

Beachten Sie, dass in unserem Fall die Funktion nicht ohne if gestartet werden kann - wenn man das tut, erhält man einen unendlichen Funktionsaufruf.

Beispiel . Rekursion zum Ausgeben von Elementen verschachtelter Listen

Rekursionen werden am häufigsten für die Iteration durch Listen unterschiedlicher Verschachtelungstiefe verwendet. Nehmen wir an, wir haben die folgende Liste:

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

Lassen Sie uns eine Funktion erstellen, die sie durchläuft. Darin muss zunächst eine Bedingung gesetzt werden, damit ein Element, das ein Primitiv ist, d.h. einfach eine aus der Liste extrahierte Zahl, in die Konsole ausgegeben wird. Und wenn das Element ein komplexes Objekt ist, zum Beispiel eine verschachtelte Liste, dann soll in diesem Fall die Funktion sich selbst aufrufen, d.h. es findet eine Rekursion statt. Um den Typ des Elements zu überprüfen, verwenden wir die Funktion isinstance. Für unser Beispiel schreiben wir im ersten Parameter von isinstance el, und als zweiten - den Typ list:

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

Beim Aufruf der Funktion wird eine Reihe aller Zahlen aus der verschachtelten Liste ausgegeben:

func(lst) # gibt 1, 2, ... 8, 9 aus

Beispiel . Rekursion für Operationen mit Elementen verschachtelter Listen

Rekursionen können auch für verschiedene Operationen mit Elementen verschachtelter Listen verwendet werden. Nehmen wir an, wir haben die folgende Liste:

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

Lassen Sie uns die Summe aller ihrer Elemente erhalten. Dazu deklarieren wir in der Funktion eine Variable res, in der die Summe der Zahlen akkumuliert wird. In der Bedingung schreiben wir, dass wenn das Element ein komplexes Objekt ist, es in den Parameter der Funktion func fällt und zur Summe addiert wird. Das bedeutet, dass das Element sich in der Rekursion befindet, bis es ein Primitiv wird. Und in diesem Fall wird es einfach zur in res geschriebenen Summe addiert:

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

Lassen Sie uns die Funktion aufrufen und ihr Ergebnis in der Konsole ausgeben:

print(func(lst)) # gibt 45 aus

Beispiel . Rekursion zur Akkumulation in eine Liste

Mit Hilfe der Rekursion können verschachtelte Listen in eine eindimensionale Liste aufgelöst werden. Nehmen wir an, wir haben die folgende Liste:

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

Lassen Sie uns in der Funktion eine leere Liste res definieren, in der die Elemente der ursprünglichen Liste akkumuliert werden. Dann starten wir eine Schleife und setzen eine Bedingung - wenn das Element eine Liste ist, dann gelangt es in die Methode extend. Diese Methode fügt die Elemente einer Liste an das Ende einer zweiten Liste an, d.h. die Elemente der verschachtelten Liste gelangen an das Ende der Liste 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))

Das Ergebnis des ausgeführten Codes:

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

Praktische Aufgaben

Geben Sie alle numerischen Elemente eines Wörterbuchs beliebiger Verschachtelungstiefe aus:

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

Finden Sie die Summe der Elemente des Wörterbuchs aus der vorherigen Aufgabe.

Erhalten Sie eine Liste der primitiven Elemente des Wörterbuchs aus der vorherigen Aufgabe.