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-сіз іске қосуға болмайды - егер мұны жасасақ, онда функциялардың шексіз шақыруы пайда болады.

Мысал . Ішкі список элементтерін шығару үшін рекурсия

Рекурсиялар көбінесе әртүрлі деңгейдегі ішкі list-терді айналып өту үшін қолданылады. Бізде келесі list бар делік:

lst = [1, [2, 3], [[4, 5], [6, 7, 8, [9]]]]

Оны айналып өтетін функция жасайық. Онда алдымен элемент примитив болған жағдайда, яғни list-тен жай ғана алынған сан, консольге шығарылуы үшін шарт қою керек. Ал егер элемент күрделі нысан болса, мысалы, ішкі list болса, онда функция өзін-өзі шақырсын, яғни рекурсия орын алады. Элемент түрін тексеру үшін isinstance функциясын қолданамыз. Тек біздің мысал үшін isinstance-тің бірінші параметріне el, ал екіншісіне list түрін жазамыз:

def func(lst):
	for el in lst:
		if isinstance(el, list):
			func(el)
		else:
			print(el)

Функцияны шақырған кезде ішкі list-тің барлық сандарының қатары шығады:

func(lst) # 1, 2, ... 8, 9 шығарады

Мысал . Ішкі список элементтерімен операциялар үшін рекурсия

Рекурсияны ішкі list элементтерімен әртүрлі операциялар жасау үшін де қолдануға болады. Бізде келесі list бар делік:

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 шығарады

Мысал . List-те жинақтау үшін рекурсия

Рекурсия көмегімен ішкі list-терді бір өлшемді list-ке айналдыруға болады. Бізде келесі list бар делік:

lst = [1, [2, 3], [[4, 5], [6, 7, 8, [9]]]]

Функцияда бастапқы list элементтері жиналатын бос res list-ін жазайық. Содан кейін циклді іске қосамыз және шарт қоямыз - егер элемент list болса, онда ол extend әдісіне түседі. Бұл әдіс бір list-тің элементтерін екінші list-тің соңына қосады, яғни ішкі list-тің элементтері res list-інің соңына түседі:

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
}

Алдыңғы тапсырманың сөздік элементтерінің қосындысын табыңыз.

Алдыңғы тапсырманың сөздігінен примитивті элементтер list-ін алыңыз.