19: Рекурзија

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

Пример:

У нашој лекцији о петљама, користили смо петљу while да добијемо следећи излаз.

5

4

3

2

1

Buuum!

Ево програма који користи рекурзију, са истим резултатом:

За следећи пример ћемо имати неке реченице за штампање да бисмо лакше разумели како програм ради. Ова верзија програма учитава временски лимит из улаза.

Сада ћемо видети како ово функционише корак по корак. Када је улаз 5, програм прво позива копију функције odbrojavanje са n=5, која штампа 5 и позива odbrojavanje(4). Ово се наставља до odbrojavanje(0), која штампа "Buuum" и више не позива одбројавање. Када Python заврши са позивањем odbrojavanje функције када је n=0, Python се враћа на функцију која ју је позвала, што је odbrojavanje са n=1. Онда се враћамо на позивање са n=2 и тако даље.

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

Сада је време да ви напишете код. Подесите функцију одбројавање тако да броји унапред уместо уназад.

Вежба кодирања: Буууууум!

Напишите рекурзивну функцију brojanje(n) која врши одбројавање од 1 до n.

Морате креирати налог и бити логовани да бисте могли да поставите питање.

# обришите овај коментар и унесите Ваш код овде

Унесите код за тестирање као што је print(myfunction("test argument")) испод.

Хајде сада да подесимо наш програм brojanje, тако да броји у размацима од 2. Излаз би требало да буде 5, 3, 1, Buuum! Променићемо аргумент функције n-1 у n-2. Шта мислите, треба ли још нешто да променимо у следећем примеру?

Видимо да овај програм не ради као што смо намеравали. Одштампао је 5, 3, 1, као што смо желели, али, уместо да стане, наставио је са -1, -3, -5 до бесконачности.

Када правимо рекурзивне функције, морамо да пазимо да оне не оду у бесконачност! Исправите програм odbrojavanjePo2, тако да се заустави на 1 (или 2, ако је n парно) и одштампа 'Buuum!'

Вежба кодирања: Дупло време

Подесите овај рекурзивни програм тако да исправно одбројава у размацима од 2.

Морате креирати налог и бити логовани да бисте могли да поставите питање.

def odbrojavanjePo2(n): if n == 0: print('Buuum!') else: print(n) odbrojavanjePo2 (n - 2) # обришите овај коментар и унесите Ваш код овде

Унесите код за тестирање као што је print(myfunction("test argument")) испод.

Дизајнирање рекурзивних функција

Рекурзивна функција је функција која позива саму себе. Али мора постоји ситуација у којој функција неће позивати себе, или ће програм ићи до бесконачности, као што смо видели у примеру изнад. Део рекурзивне функције где она не позива саму себе се назива основни случај. У горњем примеру је основни случај био n<=0. Дизајнирање рекурзивне функције тражи да се пажљиво одабере основни случај и да свака секвенца позива функције на крају стигне до основног случаја.

У следећој вежби већ имате испрограмиран основни случај, али ћете сами написати остатак рекурзивне функције.

Вежба кодирања: Дигитална сума

Дигитална сума броја n је сума његових цифара. Напишите рекурзивну функцију digitalnaSuma(n) која узима позитиван цео број n и враћа његову дигиталну суму. На пример, digitalnaSuma(2019) би требало да врати 12 јер је 2+0+1+9=12.

Морате креирати налог и бити логовани да бисте могли да поставите питање.

# обришите овај коментар и унесите Ваш код овде

Унесите код за тестирање као што је print(myfunction("test argument")) испод.

Вежба кратког одговроа: Енигма

Који је излаз наредног рекурзивног програма?
def enigma(a, b): if b == 0: return a return enigma (b, a % b)   print(enigma (20, 12))
Ваш одговор:

Тачно!

Вежба кодирања: Низ

Рекурзија низ, која почиње са позитивним целим бројем, генерисана је наредним, једноставним правилима. Ако је n парно, следећи број у секвенци (низy) је n/2. Ako je n непарно, следећи број у секвенци је 3*n+1. Понављањем овог процеса, генеришемо рекурзију низ. Напишите рекурзивну функцију niz(n) која штампа секвенцу низа са почетком y n. Станите када секвенца дође до броја 1 (јер бисмо иначе добили бесконачну петљу 1, 4, 2, 1, 4, 2, ...) На пример, када je n=5, ваш програм би требало да избаци следећу секвенцу:

5
16
8
4
2
1

Морате креирати налог и бити логовани да бисте могли да поставите питање.

# обришите овај коментар и унесите Ваш код овде

Унесите код за тестирање као што је print(myfunction("test argument")) испод.