Рэкурсія ў Python

У праграмаванні ёсць такое паняцце, як рэкурсія - калі функцыя выклікае сама сябе.

Прыклад . Простая рэкурсія са лічільнікам

Давайце выведзем з дапамогай рэкурсіі лікі ад 1 да 10:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # тут функцыя выклікае сама сябе
		
	func()

Давайце абмяркуем, як працуе гэты код.

У нас ёсць глабальная зменная i і функцыя func, унутры якой у кансоль выводзіцца змесціва зменнай i, а затым да яе дадаецца адзінка.

Калі наша зменная i меншая або роўная 10, то функцыя выклікаецца зноў. Паколькі зменная i - глабальная, то пры кожным новым выкліку функцыі ў ёй будзе зададзенае пры папярэднім выкліку значэнне зменнай i.

Атрымаецца, што функцыя будзе выклікаць сама сябе да таго часу, пакуль i не стане больш за 10.

Улічвайце, што ў нашым выпадку нельга функцыю запусціць без if - калі гэта зрабіць, то атрымаецца бясконцы выклік функцый.

Прыклад . Рэкурсія для вываду элементаў укладзеных спісаў

Найчасцей рэкурсіі ўжываюцца для перабору спісаў рознай ступені ўкладзенасці. Хай у нас ёсць наступны спіс:

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

Давайце створым функцыю, якая перабярэ яго. У ёй спачатку трэба задаць умову, каб элемент, які з'яўляецца прымітывам, г.зн. проста вынятым са спісу лікам, выводзіўся ў кансоль. А калі элемент з'яўляецца аб'ектам, напрыклад, укладзеным спісам, то хай у гэтым выпадку функцыя выкліча сама сябе, г.зн. адбудзецца рэкурсія. Для праверкі тыпу элемента ўжыем функцыю isinstance. Toлькі для нашага прыкладу ў першы параметр isinstance пропишем el, а другім - тып list:

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

Пры выкліку функцыі выйдзе шэраг усіх лікаў з укладзенага спісу:

func(lst) # выведе 1, 2, ... 8, 9

Прыклад . Рэкурсія для аперацый з элементамі ўкладзеных спісаў

Рэкурсіі можна ўжываць і для розных аперацый з элементамі ўкладзеных спісаў. Хай у нас ёсць наступны спіс:

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

Давайце атрымаем суму ўсіх яго элементаў. Для гэтага ў функцыі аб'явім зменную res, у якую будзе назапашвацца сума лікаў. У умове пропишем, што калі элемент з'яўляецца складаным аб'ектам, то ён трапляе ў параметры функцыі func і дадаецца да сумы. Гэта значыць, што элемент будзе знаходзіцца ў рэкурсіі пакуль не стане прымітывам. І ў гэтым выпадку ён проста дадасца да сумы, запісанай у res:

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

Давайце выклічам функцыю і выведзем яе вынік у кансоль:

print(func(lst)) # выведе 45

Прыклад . Рэкурсія для назапашвання ў спіс

З дапамогай рэкурсіі можна разкласці ўкладзеныя спісы ў адзін аднамерны спіс. Хай у нас ёсць наступны спіс:

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

Давайце пропишем у функцыі пусты спіс res, у які будуць назапашвацца элементы зыходнага спісу. Далей запусцім цыкл і зададзім умову - калі элемент з'яўляецца спісам, то ён трапляе ў метад extend. Гэты метад далучае элементы аднаго спісу ў канец другога спісу, г.зн. элементы ўкладзенага спісу трапляюць у канец спісу 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))

Вынік выкананага кода:

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

Практычныя задачы

Выведзіце ўсе лікавыя элементы слоўніка адвольнай ступені ўкладзенасці:

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

Знайдзіце суму элементаў слоўніка з папярэдняй задачы.

Атрымайце спіс прымітыўных элементаў слоўніка з папярэдняй задачы.