Rekurencja w Pythonie

W programowaniu istnieje takie pojęcie, jak rekurencja - kiedy funkcja wywołuje samą siebie.

Przykład . Prosta rekurencja z licznikiem

Wypiszmy za pomocą rekurencji liczby od 1 do 10:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # tutaj funkcja wywołuje samą siebie
		
	func()

Omówmy, jak działa ten kod.

Mamy globalną zmienną i i funkcję func, wewnątrz której do konsoli wypisywana jest zawartość zmiennej i, a następnie dodawana jest do niej jedynka.

Jeśli nasza zmienna i jest mniejsza lub równa 10, to funkcja jest wywoływana ponownie. Ponieważ zmienna i jest globalna, to przy każdym nowym wywołaniu funkcji będzie w niej ustawiona w poprzednim wywołaniu wartość zmiennej i.

Okaże się, że funkcja będzie wywoływać samą siebie, dopóki i nie stanie się większe niż 10.

Należy pamiętać, że w naszym przypadku nie można funkcji uruchomić bez if - jeśli to zrobić, to otrzymamy nieskończone wywołanie funkcji.

Przykład . Rekurencja do wypisywania elementów zagnieżdżonych list

Rekurencje są najczęściej używane do przeglądania list o różnym stopniu zagnieżdżenia. Załóżmy, że mamy następującą listę:

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

Stwórzmy funkcję, która ją przejdzie. W niej najpierw trzeba ustawić warunek, aby element, który jest prymitywem, tj. po prostu liczbą wyjętą z listy, był wypisywany do konsoli. A jeśli element jest obiektem, na przykład zagnieżdżoną listą, to niech w tym przypadku funkcja wywoła samą siebie, tj. nastąpi rekurencja. Do sprawdzenia typu elementu zastosujemy funkcję isinstance. Tylko dla naszego przykładu w pierwszym parametrze isinstance wpiszemy el, a drugim - typ list:

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

Po wywołaniu funkcji wypisze się szereg wszystkich liczb z zagnieżdżonej listy:

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

Przykład . Rekurencja do operacji na elementach zagnieżdżonych list

Rekurencji można również używać do różnych operacji na elementach zagnieżdżonych list. Załóżmy, że mamy następującą listę:

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

Otrzymajmy sumę wszystkich jej elementów. W tym celu w funkcji zadeklarujmy zmienną res, do której będzie akumulowana suma liczb. W warunku opiszemy, że jeśli element jest złożonym obiektem, to trafi do parametru funkcji func i zostanie dodany do sumy. Oznacza to, że element będzie znajdował się w rekurencji, dopóki nie stanie się prymitywem. I w tym przypadku po prostu doda się do sumy zapisanej w res:

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

Wywołajmy funkcję i wypiszmy jej wynik do konsoli:

print(func(lst)) # wypisze 45

Przykład . Rekurencja do akumulowania w listę

Za pomocą rekurencji można rozłożyć zagnieżdżone listy na jedną jednowymiarową listę. Załóżmy, że mamy następującą listę:

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

Wpiszmy w funkcji pustą listę res, do której będą akumulowane elementy początkowej listy. Następnie uruchommy pętlę i ustawmy warunek - jeśli element jest listą, to trafi do metody extend. Ta metoda dołącza elementy jednej listy na koniec drugiej listy, tj. elementy zagnieżdżonej listy trafią na koniec listy 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))

Wynik wykonanego kodu:

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

Zadania praktyczne

Wypisz wszystkie numeryczne elementy słownika dowolnego poziomu zagnieżdżenia:

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

Znajdź sumę elementów słownika z poprzedniego zadania.

Otrzymaj listę prymitywnych elementów słownika z poprzedniego zadania.