Рекурзија у 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. Само за наш пример у први параметар 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
}

Пронађите збир елемената речника из претходног задатка.

Добијте листу примитивних елемената речника из претходног задатка.