Rekursi di Python

Dalam pemrograman, ada konsep yang disebut rekursi - ketika suatu fungsi memanggil dirinya sendiri.

Contoh . Rekursi sederhana dengan pencacah

Mari kita tampilkan angka 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 bahas bagaimana kode ini bekerja.

Kita memiliki variabel global i dan fungsi func, di dalamnya kandungan variabel i ditampilkan ke konsol, kemudian ditambah dengan satu.

Jika variabel kita i kurang dari atau sama dengan 10, maka fungsi dipanggil ulang. Karena variabel i - global, maka pada setiap pemanggilan fungsi baru, di dalamnya akan terdapat nilai variabel i yang ditetapkan pada pemanggilan sebelumnya.

Hasilnya, fungsi akan memanggil dirinya sendiri hingga i menjadi lebih besar dari 10.

Perhatikan, bahwa dalam kasus kita, fungsi tidak bisa dijalankan tanpa if - jika ini dilakukan, maka akan terjadi pemanggilan fungsi tak terbatas.

Contoh . Rekursi untuk menampilkan elemen dari daftar bersarang

Rekursi paling sering digunakan untuk menelusuri daftar dengan berbagai tingkat penyarangan. Misalkan kita memiliki daftar berikut:

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

Mari kita buat fungsi yang akan menelusurinya. Di dalamnya, pertama-tama perlu ditetapkan kondisi, sehingga elemen, yang merupakan primitif, yaitu angka yang diambil begitu saja dari daftar, ditampilkan ke konsol. Dan jika elemen tersebut merupakan objek, misalnya, daftar bersarang, maka dalam kasus ini biarkan fungsi memanggil dirinya sendiri, yaitu terjadi rekursi. Untuk memeriksa tipe elemen, kita akan menggunakan fungsi isinstance. Hanya untuk contoh kita, di parameter pertama isinstance kita tulis el, dan yang kedua - tipe list:

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

Saat fungsi dipanggil, akan ditampilkan serangkaian semua angka dari daftar bersarang:

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

Contoh . Rekursi untuk operasi dengan elemen daftar bersarang

Rekursi juga dapat diterapkan untuk berbagai operasi dengan elemen daftar bersarang. Misalkan kita memiliki daftar berikut:

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

Mari kita dapatkan jumlah semua elemennya. Untuk itu, dalam fungsi deklarasikan variabel res, ke dalamnya akan diakumulasikan jumlah angka. Dalam kondisi, tuliskan bahwa jika elemen merupakan objek kompleks, maka ia masuk sebagai parameter fungsi func dan ditambahkan ke jumlah. Ini berarti elemen akan berada dalam rekursi hingga menjadi primitif. Dan dalam kasus ini, ia hanya akan ditambahkan ke jumlah, yang tertulis di 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 tampilkan hasilnya di konsol:

print(func(lst)) # akan menampilkan 45

Contoh . Rekursi untuk akumulasi ke dalam daftar

Dengan rekursi, Anda dapat menguraikan daftar bersarang menjadi satu daftar satu dimensi. Misalkan kita memiliki daftar berikut:

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

Mari kita tulis dalam fungsi sebuah daftar kosong res, ke dalamnya akan diakumulasikan elemen dari daftar asli. Selanjutnya jalankan loop dan tetapkan kondisi - jika elemen adalah sebuah daftar, maka ia akan masuk ke metode extend. Metode ini menggabungkan elemen dari satu daftar ke akhir daftar kedua, yaitu elemen dari daftar bersarang akan masuk ke akhir daftar 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 dari kode yang dijalankan:

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

Tugas Praktis

Tampilkan semua elemen numerik dari kamus dengan tingkat penyarangan arbitrer:

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

Carilah jumlah elemen dari kamus pada tugas sebelumnya.

Dapatkan daftar elemen primitif dari kamus pada tugas sebelumnya.