Ռեկուրսիան 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
}

Գտեք նախորդ առաջադրանքի բառարանում գտնվող տարրերի գումարը.

Ստացեք նախորդ առաջադրանքի բառարանում գտնվող պրիմիտիվ տարրերի ցուցակը.