Рекурсия в 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
}

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

Получете списък с примитивните елементи от речника от предходната задача.