რეკურსია 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
}

იპოვეთ წინა ამოცანის ლექსიკონის ელემენტების ჯამი.

მიიღეთ წინა ამოცანის ლექსიკონის პრიმიტიული ელემენტების სია.