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

Ҷамъи элементҳои луғатро аз масъалаи қаблин ёбед.

Рӯйхати элементҳои примитивии луғатро аз масъалаи қаблин ба даст оред.