Rekursi dalam Python

Dalam pengaturcaraan, terdapat konsep yang dipanggil rekursi - apabila fungsi memanggil dirinya sendiri.

Contoh . Rekursi mudah dengan pembilang

Mari kita output nombor dari 1 hingga 10 menggunakan rekursi:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # di sini fungsi memanggil dirinya sendiri
		
	func()

Mari kita bincangkan bagaimana kod ini berfungsi.

Kami mempunyai pembolehubah global i dan fungsi func, di dalamnya kandungan pembolehubah i dipaparkan ke konsol, dan kemudian satu ditambah kepadanya.

Jika pembolehubah kami i kurang daripada atau sama dengan 10, maka fungsi dipanggil sekali lagi. Oleh kerana pembolehubah i - global, maka pada setiap panggilan fungsi baru ia akan mempunyai nilai pembolehubah i yang ditetapkan pada panggilan sebelumnya.

Hasilnya, fungsi akan memanggil dirinya sendiri sehingga i menjadi lebih besar daripada 10.

Perhatikan bahawa dalam kes kami, fungsi tidak boleh dijalankan tanpa if - jika ini dilakukan, panggilan fungsi tak terhingga akan terhasil.

Contoh . Rekursi untuk output elemen senarai bersarang

Rekursi paling kerap digunakan untuk menghuraikan senarai dengan tahap sarangan yang berbeza. Katakan kami mempunyai senarai berikut:

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

Mari kita buat fungsi yang akan menghuraikannya. Di dalamnya, pertama sekali perlu menetapkan syarat supaya elemen yang merupakan primitif, iaitu nombor yang hanya diekstrak dari senarai, dipaparkan ke konsol. Dan jika elemen itu adalah objek kompleks, contohnya, senarai bersarang, maka dalam kes ini biarkan fungsi memanggil dirinya sendiri, iaitu rekursi akan berlaku. Untuk menyemak jenis elemen, kami menggunakan fungsi isinstance. Hanya untuk contoh kami, dalam parameter pertama isinstance kami tulis el, dan yang kedua - jenis list:

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

Apabila fungsi dipanggil, semua nombor dari senarai bersarang akan dipaparkan:

func(lst) # akan output 1, 2, ... 8, 9

Contoh . Rekursi untuk operasi dengan elemen senarai bersarang

Rekursi juga boleh digunakan untuk pelbagai operasi dengan elemen senarai bersarang. Katakan kami mempunyai senarai berikut:

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

Mari kita dapatkan jumlah semua elemennya. Untuk melakukan ini, dalam fungsi isytiharkan pembolehubah res, di mana jumlah nombor akan terkumpul. Dalam syarat, tulis bahawa jika elemen adalah objek kompleks, maka ia masuk ke dalam parameter fungsi func dan ditambah kepada jumlah. Ini bermakna elemen akan berada dalam rekursi sehingga ia menjadi primitif. Dan dalam kes ini, ia hanya akan ditambah kepada jumlah yang ditulis dalam res:

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

Mari kita panggil fungsi dan output hasilnya ke konsol:

print(func(lst)) # akan output 45

Contoh . Rekursi untuk pengumpulan ke dalam senarai

Menggunakan rekursi, anda boleh menguraikan senarai bersarang kepada satu senarai satu dimensi. Katakan kami mempunyai senarai berikut:

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

Mari kita tulis dalam fungsi senarai kosong res, di mana elemen senarai asal akan terkumpul. Seterusnya, jalankan gelung dan tetapkan syarat - jika elemen adalah senarai, maka ia akan masuk ke dalam kaedah extend. Kaedah ini menyambungkan elemen satu senarai ke hujung kedua senarai, iaitu elemen senarai bersarang akan masuk ke hujung senarai 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))

Hasil kod yang dilaksanakan:

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

Tugas Praktikal

Output semua elemen berangka kamus dengan tahap sarangan sewenang-wenangnya:

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

Cari jumlah elemen kamus dari tugas sebelumnya.

Dapatkan senarai elemen primitif kamus dari tugas sebelumnya.