Рэкурсія ў Python

У праграмаванні ёсць такое паняцце, як рэкурсія - калі функцыя выклікае сама сябе.

Прыклад . Простая рэкурсія са лічільнікам

Давайце выведзем з дапамогай рэкурсіі лікі ад 1 да 10:

pythoni = 1

def func():
  global i
  print(i)
  i += 1
  
  if i <= 10:
    func() # тут функцыя выклікае сама сябе
    
  func()

Давайце абмяркуем, як працуе гэты код.

У нас ёсць глабальная зменная i і функцыя func, унутры якой у кансоль выводзіцца змесціва зменнай i, а затым да яе дадаецца адзінка.

Калі наша зменная i меншая або роўная 10, то функцыя выклікаецца зноў. Паколькі зменная i - глабальная, то пры кожным новым выкліку функцыі ў ёй будзе зададзенае пры папярэднім выкліку значэнне зменнай i.

Атрымаецца, што функцыя будзе выклікаць сама сябе да таго часу, пакуль i не стане больш за 10.

Улічвайце, што ў нашым выпадку нельга функцыю запусціць без if - калі гэта зрабіць, то атрымаецца бясконцы выклік функцый.

Прыклад . Рэкурсія для вываду элементаў укладзеных спісаў

Найчасцей рэкурсіі ўжываюцца для перабору спісаў рознай ступені ўкладзенасці. Хай у нас ёсць наступны спіс:

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

Давайце створым функцыю, якая перабярэ яго. У ёй спачатку трэба задаць умову, каб элемент, які з'яўляецца прымітывам, г.зн. проста вынятым са спісу лікам, выводзіўся ў кансоль. А калі элемент з'яўляецца аб'ектам, напрыклад, укладзеным спісам, то хай у гэтым выпадку функцыя выкліча сама сябе, г.зн. адбудзецца рэкурсія. Для праверкі тыпу элемента ўжыем функцыю isinstance. Toлькі для нашага прыкладу ў першы параметр isinstance пропишем el, а другім - тып list:

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

Пры выкліку функцыі выйдзе шэраг усіх лікаў з укладзенага спісу:

pythonfunc(lst) # выведе 1, 2, ... 8, 9

Прыклад . Рэкурсія для аперацый з элементамі ўкладзеных спісаў

Рэкурсіі можна ўжываць і для розных аперацый з элементамі ўкладзеных спісаў. Хай у нас ёсць наступны спіс:

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

Давайце атрымаем суму ўсіх яго элементаў. Для гэтага ў функцыі аб'явім зменную res, у якую будзе назапашвацца сума лікаў. У умове пропишем, што калі элемент з'яўляецца складаным аб'ектам, то ён трапляе ў параметры функцыі func і дадаецца да сумы. Гэта значыць, што элемент будзе знаходзіцца ў рэкурсіі пакуль не стане прымітывам. І ў гэтым выпадку ён проста дадасца да сумы, запісанай у res:

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

Давайце выклічам функцыю і выведзем яе вынік у кансоль:

pythonprint(func(lst)) # выведе 45

Прыклад . Рэкурсія для назапашвання ў спіс

З дапамогай рэкурсіі можна разкласці ўкладзеныя спісы ў адзін аднамерны спіс. Хай у нас ёсць наступны спіс:

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

Давайце пропишем у функцыі пусты спіс res, у які будуць назапашвацца элементы зыходнага спісу. Далей запусцім цыкл і зададзім умову - калі элемент з'яўляецца спісам, то ён трапляе ў метад extend. Гэты метад далучае элементы аднаго спісу ў канец другога спісу, г.зн. элементы ўкладзенага спісу трапляюць у канец спісу 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))

Вынік выкананага кода:

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

Практычныя задачы

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