Rekursio Pythonissa

Ohjelmoinnissa on käsite nimeltä rekursio - kun funktio kutsuu itseään.

Esimerkki . Yksinkertainen rekursio laskurilla

Tulostetaan rekursion avulla numerot 1:stä 10:een:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # tässä funktio kutsuu itseään
		
	func()

Keskustellaan kuinka tämä koodi toimii.

Meillä on globaali muuttuja i ja funktio func, jonka sisällä konsoliin tulostetaan muuttujan i sisältö, jonka jälkeen siihen lisätään yksi.

Jos muuttujamme i on pienempi tai yhtä suuri kuin 10, funktiota kutsutaan uudelleen. Koska muuttuja i on globaali, jokaisella funktion uudella kutsulla siinä on edellisellä kutsulla asetettu muuttujan i arvo.

Käy niin, että funktio kutsuu itseään kunnes i tulee suuremmaksi kuin 10.

Huomioi, että tässä tapauksessa funktiota ei voida käynnistää ilman if - jos tämä tehdään, saadaan ääretön funktiokutsujen sarja.

Esimerkki . Rekursio sisäkkäisten listojen elementtien tulostamiseen

Recursiota käytetään useimmiten eriasteisten sisäkkäisten listojen läpikäyntiin. Olkoon meillä seuraava lista:

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

Luodaan funktio, joka käy sen läpi. Siinä on ensin asetettava ehto, jotta elementti, joka on primitiivi, eli yksinkertaisesti listasta poimittu luku, tulostetaan konsoliin. Ja jos elementti on monimutkainen objekti, esimerkiksi sisäkkäinen lista, niin anna tässä tapauksessa funktion kutsua itseään, eli tapahtuu rekursio. Elementin tyypin tarkistamiseen käytetään funktiota isinstance. Vain meidän esimerkkiämme varten ensimmäiseen parametriin isinstance kirjoitetaan el, ja toiseen - tyyppi list:

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

Funktiota kutsuttaessa tulostuu sarja kaikkia numeroita sisäkkäisestä listasta:

func(lst) # tulostaa 1, 2, ... 8, 9

Esimerkki . Rekursio operaatioihin sisäkkäisten listojen elementeillä

Rekursiota voidaan käyttää myös erilaisiin operaatioihin sisäkkäisten listojen elementtien kanssa. Olkoon meillä seuraava lista:

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

Saadaan kaikkien sen elementtien summa. Tätä varten funktiossa ilmoitetaan muuttuja res, johon kertyy numeroiden summa. Ehdossa määritellään, että jos elementti on monimutkainen objekti, se päätyy funktion parametriin func ja lisätään summaan. Tämä tarkoittaa, että elementti on rekursiossa kunnes siitä tulee primitiivi. Ja tässä tapauksessa se yksinkertaisesti lisätään res:ään kirjoitettuun summaan:

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

Kutsutaan funktiota ja tulostetaan sen tulos konsoliin:

print(func(lst)) # tulostaa 45

Esimerkki . Rekursio keräämiseen listaan

Rekursion avulla voidaan hajottaa sisäkkäiset listat yhdeksi yksiulotteiseksi listaksi. Olkoon meillä seuraava lista:

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

Määritellään funktiossa tyhjä lista res, johon kertyvät lähdelistan elementit. Seuraavaksi käynnistetään silmukka ja asetetaan ehto - jos elementti on lista, se päätyy metodiin extend. Tämä metodi liittää yhden listan elementit toisen listan loppuun, eli sisäkkäisen listan elementit päätyvät listan res loppuun:

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

Suoritetun koodin tulos:

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

Käytännön tehtävät

Tulosta kaikki sanakkeen numeeriset elementit mielivaltaisessa sisäkkäisyystasossa:

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

Etsi edellisen tehtävän sanakkeen elementtien summa.

Hae listana edellisen tehtävän sanakkeen primitiiviset elementit.