Питхон рекурзија (рекурзивна функција)

У овом упутству научићете да креирате рекурзивну функцију (функцију која се сама позива).

Шта је рекурзија?

Рекурзија је процес дефинисања нечега у смислу самог себе.

Пример физичког света био би постављање два паралелна огледала окренута једно према другом. Било који предмет између њих рефлектовао би се рекурзивно.

Питхон рекурзивна функција

У Питхону знамо да функција може позивати друге функције. Могуће је чак и да се функција сама позове. Ове врсте конструкција називају се рекурзивним функцијама.

Следећа слика приказује рад рекурзивне функције тзв recurse.

Рекурзивна функција у Питхону

Следи пример рекурзивне функције за проналажење фактора целог броја.

Факторијал броја је умножак свих целих бројева од 1 до тог броја. На пример, фактор од 6 (означен као 6!) Је 1 * 2 * 3 * 4 * 5 * 6 = 720.

Пример рекурзивне функције

 def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1)) num = 3 print("The factorial of", num, "is", factorial(num))

Оутпут

 Фактор од 3 је 6

У горњем примеру factorial()је рекурзивна функција како се сама назива.

Када ову функцију позовемо са позитивним целим бројем, она ће се рекурзивно позвати смањењем броја.

Свака функција множи број фактором броја испод себе док не буде једнака јединици. Овај рекурзивни позив може се објаснити у следећим корацима.

 факторијел (3) # 1. позив са 3 3 * факторијем (2) # 2. позив са 2 3 * 2 * фактором (1) # 3. позив са 1 3 * 2 * 1 # повратак са 3. позива као број = 1 3 * 2 # повратак из другог позива 6 # повратак из првог позива

Погледајмо слику која приказује корак по корак процеса онога што се догађа:

Рад рекурзивне факторијелне функције

Наша рекурзија се завршава када се број смањи на 1. То се назива основни услов.

Свака рекурзивна функција мора имати основни услов који зауставља рекурзију, или се функција сама бесконачно позива.

Питхон тумач ограничава дубину рекурзије како би избегао бесконачне рекурзије, што резултира преливањем стека.

Подразумевано је максимална дубина рекурзије 1000. Ако се граница пређе, то резултира RecursionError. Погледајмо један такав услов.

 def recursor(): recursor() recursor()

Оутпут

 Трацебацк (најновији последњи позив): Датотека "", ред 3, у датотеци "", ред 2, у датотеци "", ред 2, у датотеци "", ред 2, у (Претходни ред поновљен још 996 пута ) РецурсионЕррор: премашена је максимална дубина рекурзије

Предности рекурзије

  1. Рекурзивне функције чине да код изгледа чисто и елегантно.
  2. Сложени задатак се може разбити на једноставније под-проблеме помоћу рекурзије.
  3. Генерисање секвенце је лакше са рекурзијом него коришћење неке угнежђене итерације.

Мане рекурзије

  1. Понекад је тешко следити логику иза рекурзије.
  2. Рекурзивни позиви су скупи (неефикасни) јер заузимају пуно меморије и времена.
  3. Тешко је отклонити грешке у рекурзивним функцијама.

Занимљиви Чланци...