Rekurzija u Pythonu

U programiranju postoji pojam, rekurzija - kada funkcija poziva samu sebe.

Primer . Jednostavna rekurzija sa brojačem

Hajde da ispišemo pomoću rekurzije brojeve od 1 do 10:

pythoni = 1

def func():
  global i
  print(i)
  i += 1
  
  if i <= 10:
    func() # ovde funkcija poziva samu sebe
    
func()

Hajde da razmotrimo kako ovaj kod radi.

Imamo globalnu promenljivu i i funkciju func, unutar koje se u konzolu ispisuje sadržaj promenljive i, a zatim joj se dodaje jedinica.

Ako je naša promenljiva i manja ili jednaka 10, onda se funkcija poziva ponovo. Pošto je promenljiva i globalna, tada će pri svakom novom pozivu funkcije u njoj biti postavljena vrednost promenljive i iz prethodnog poziva.

Ispostavlja se da će funkcija pozivati samu sebe sve dok i ne postane veća od 10.

Imajte u vidu da u našem slučaju ne možemo funkciju pokrenuti bez if - ako se to uradi, dobićemo beskonačno pozivanje funkcija.

Primer . Rekurzija za ispis elemenata ugnježdenih listi

Najače se rekurzije primenjuju za prolazak kroz liste različitog stepena ugnježdenosti. Neka imamo sledeću listu:

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

Hajde da napravimo funkciju koja će proći kroz nju. U njoj prvo treba postaviti uslov, da element, koji je primitivan, tj. prosto izvučen broj iz liste, bude ispisan u konzolu. A ako je element objekat, na primer, ugnježdena lista, onda neka u tom slučaju funkcija pozove samu sebe, tj. desiće se rekurzija. Za proveru tipa elementa primenimo funkciju isinstance. Samo za naš primer u prvi parametar isinstance upisaćemo el, a drugim - tip list:

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

Pri pozivu funkcije ispisaće se niz svih brojeva iz ugnježdene liste:

pythonfunc(lst) # ispisaće 1, 2, ... 8, 9

Primer . Rekurzija za operacije sa elementima ugnježdenih listi

Rekurzije se mogu primeniti i za različite operacije sa elementima ugnježdenih listi. Neka imamo sledeću listu:

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

Hajde da dobijemo zbir svih njenih elemenata. Za ovo u funkciji deklarišimo promenljivu res, u koju će se nakupiti zbir brojeva. U uslovu upisaćemo da ako je element složen objekat, onda on pada u parametru funkcije func i dodaje se zbiru. Ovo znači da će element biti u rekurziji sve dok ne postane primitivan. I u tom slučaju će se prosto dodati zbiru, zapisanom u res:

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

Hajde da pozovemo funkciju i ispišemo njen rezultat u konzolu:

pythonprint(func(lst)) # ispisaće 45

Primer . Rekurzija za nakupijanje u listu

Pomoću rekurzije možemo raščlaniti ugnježdene liste u jednu jednodimenzionalnu listu. Neka imamo sledeću listu:

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

Hajde da upišemo u funkciji praznu listu res, u koju će se nakupiti elementi početne liste. Zatim pokrenimo ciklus i postavimo uslov - ako element je lista, onda će da upadne u metod extend. Ovaj metod pridružuje elemente jedne liste na kraj druge liste, tj. elementi ugnježdene liste upašće na kraj liste res:

pythondef func(lst):
  res = []
  for el in lst:
    if isinstance(el, list):
      res.extend(func(el))
    else:
      res.append(el)
  return res
  
print(func(lst))

Rezultat izvršenog koda:

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

Praktični zadaci

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