Рекурсия в 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 ning биринчи параметрига 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 метудига тушadi. Бу метод битта рўйхатнинг элементларини иккинчи рўйхатнинг охирига бириктиради, яъни ичма-ич рўйхат элементлари res рўйхатининг охирига тушadi:

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
}

Олдинги машқдаги луғат элементларининг йиғиндисини топинг.

Олдинги машқдаги луғатнинг примитив элементлари рўйхатини олинг.