Pythonda Rekursiya

Dasturlashda rekursiya deb ataladigan tushuncha mavjud - bu funksiya o'zini o'zi chaqiradi.

Misol . Hisoblagich bilan oddiy rekursiya

Keling, rekursiya yordamida 1 dan 10 gacha bo'lgan sonlarni chiqaramiz:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # bu yerda funksiya o'zini o'zi chaqiradi
		
	func()

Keling, ushbu kod qanday ishlashini muhokama qilaylik.

Bizda global o'zgaruvchi i va func funksiyasi mavjud bo'lib, uning ichida i o'zgaruvchisining qiymati konsolga chiqariladi, so'ngra unga bir qo'shiladi.

Agar i o'zgaruvchimiz 10 dan kichik yoki teng bo'lsa, funksiya qayta chaqiriladi. i o'zgaruvchi global bo'lgani uchun, har bir yangi funksiya chaqiruvida unda oldingi chaqiruvda o'rnatilgan i o'zgaruvchisining qiymati bo'ladi.

Natijada, funksiya i 10 dan katta bo'lgunga qadar o'zini o'zi chaqiraveradi.

E'tiboringizni qaratamiz, bizning holatda funksiyani if siz ishga tushirib bo'lmaydi - agar buni qilsak, cheksiz funksiya chaqiruvlari paydo bo'ladi.

Misol . Ichma-ich ro'yxat elementlarini chiqarish uchun rekursiya

Rekursiyalar ko'pincha turli darajadagi ichki ro'yxatlarni ko'rib chiqish uchun qo'llaniladi. Quyidagi ro'yxatga ega bo'laylik:

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

Keling, uni ko'rib chiqadigan funksiya yarataylik. Unda avval shart berish kerak, primitiv bo'lgan element, ya'ni ro'yxatdan oddiy olingan son, konsolga chiqarilsin. Agar element murakkab ob'ekt bo'lsa, masalan, ichki ro'yxat, bu holda funksiya o'zini o'zi chaqirsin, ya'ni rekursiya sodir bo'lsin. Element turini tekshirish uchun isinstance funksiyasidan foydalanamiz. Faqat bizning misolimiz uchun isinstance ning birinchi parametrida el ni, ikkinchisida esa list turini yozamiz:

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

Funksiyani chaqirganda ichki ro'yxatdagi barcha sonlar qatori chiqariladi:

func(lst) # 1, 2, ... 8, 9 ni chiqaradi

Misol . Ichma-ich ro'yxat elementlari bilan amallar uchun rekursiya

Rekursiyalarni ichki ro'yxat elementlari bilan turli amallar bajarish uchun ham qo'llash mumkin. Quyidagi ro'yxatga ega bo'laylik:

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

Keling, uning barcha elementlari yig'indisini olamiz. Buning uchun funksiyada res o'zgaruvchisini e'lon qilamiz, unga sonlar yig'indisi yig'iladi. Shartda shuni yozamiz, agar element murakkab ob'ekt bo'lsa, u func funksiyasining parametrida bo'ladi va yig'indiga qo'shiladi. Bu shuni anglatadiki, element primitiv bo'lgunga qadar rekursiyada bo'ladi. Va bu holda u shunchaki res ga yozilgan yig'indiga qo'shiladi:

def func(lst):
	res = 0
	for el in lst:
		if isinstance(el, list):
			res += func(el)
		else:
			res += el
	return res

Keling, funksiyani chaqiramiz va uning natijasini konsolga chiqaramiz:

print(func(lst)) # 45 ni chiqaradi

Misol . Ro'yxatga yig'ish uchun rekursiya

Rekursiya yordamida ichki ro'yxatlarni bitta bir o'lchamli ro'yxatga yoyish mumkin. Quyidagi ro'yxatga ega bo'laylik:

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

Keling, funksiyada bo'sh res ro'yxatini yozamiz, unga boshlang'ich ro'yxat elementlari yig'iladi. Keyin tsiklni ishga tushiramiz va shart beramiz - agar element ro'yxat bo'lsa, u extend metodiga tushadi. Ushbu metod bir ro'yxat elementlarini ikkinchi ro'yxatning oxiriga qo'shadi, ya'ni ichki ro'yxat elementlari res ro'yxatining oxiriga tushadi:

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))

Bajarilgan kod natijasi:

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

Amaliy vazifalar

Ixtiyoriy darajadagi ichki lug'atning barcha raqamli elementlarini chiqaring:

{
	'a': {
		'b': 1,
		'c': 2,
		'd': {
			'e': 3,
			'f': 4
		}
	},
	'j': {
		'h': 5,
		'k': 6,
	},
	'l': 7
}

Oldingi vazifadagi lug'at elementlari yig'indisini toping.

Oldingi vazifadagi lug'atning primitiv elementlari ro'yxatini oling.