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
}

Мурунку тапшырмадагы сөздүктүн элементтеринин суммасын табыңыз.

Мурунку тапшырмадагы сөздүктүн примитивдүү элементтеринин тизмесин алыңыз.