Рекурзија во 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
}

Најдете ја сумата на елементите на речникот од претходната задача.

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