Увод

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

Ако имате питања везана за ову област можете их поставити ОВДЕ.

Додатни извори и литература

Као прво, препоручујем да скинете pdf фајл Белешке са часова вежби једне студенткиње Математичког факултета у Београду који вам може бити од велике помоћи. Наравно, не тражи се од вас да све што је тамо написано знате и разумете, али у тим белешкама је јако лепо, кратко и разумљиво дато шта су функције, како се оне дефинишу и користе, а такође има лепих и јасних примера.

Погледајте и овај линк са Википедије.

Рекурзивне функције

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

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

На жалост, иако су рекурзивне функције најчешће врло кратке и сажете, многи имају проблем да схвате како све то ради. Разлог је то што се за рекурзивно решавање проблема мора применити и рекурзивни начин размишљања, што није увек лако.

Најчешћи пример од кога се креће са објашњавањем рекурзије је писање функције за изра­чунавање факторијела. Да се подсетимо, факторијел у математици се означава знаком узвика (!)  а његова формула је:

Делује компликовано али је врло једноставно у примеру: 5! = 5*4*3*2*1

Важно правило је да је 1! = 1. Запамтите ово!

Ево како би изгледала функција написана у C-у:

int fakt(int n) { if(n==1) return 1; else return n*fakt(n-1); }

Врло просто, само четири линије кода, али да ли разумете како ово ради?

Ако бисмо позвали ову функцију са аргументом 5, онда би се она извршила на следећи начин:

fakt(5)=5 · fakt(4)

=5 · (4 · fakt(3))             // (јер је fakt(4) = 4 · fakt(3))

=5 · (4 · (3 · fakt(2)))       // (јер је fakt(3) = 3 · fakt(2))

=5 · (4 · (3 · (2 · fakt(1)))) // (јер је fakt(2) = 2 · fakt(1))

=5 · (4 · (3 · (2 · 1)))       // (јер је fakt(1) = 1)

=5 · (4 · (3 · (2 · 1)))       // сада се множење ових вредности врши редом

= 5 · (4 · (3 · 2))             // којим се ф-је завршавају тј. уназад

= 5 · (4 · 6)

= 5 · 24

= 120

Неформална правила за писање рекурзивних функција

За писање рекурзивних функција, може вам помоћи следеће неформално упутство, односно правила. Ово нису формални принципи него више „искуства из праксе“ која могу да помогну у коришћењу рекурзије:

1. одредити услов прекида рекурзије
2. одредити „мали део посла“ који рекурзивна функција „зна“ да ради
3. одредити шта је то што се пребацује на остале рекурзивне позиве функције, да они обаве

Услов прекида рекурзије – то је тачка у извршавању рекурзивне функције у којој се престаје са поновним „позивањем саме себе“. Врло је важно да свака ре­ку­рзи­вна функција (која има неку сврху) има ову тачку прекида, јер ће у су­про­тном доћи до бесконачних позива који на крају доводе до „пуцања“ самог про­грама у коме је оваква функција. У горњем примеру то је линија if(n==1) return 1; која каже, ако је n==1, само врати 1, a не позивај више себе, односно неће се извршити else блок у коме је тај рекурзивни позив. Добра пракса је да се одмах на почетку замисли где је ова тачка прекида, односно који услов треба да је испуњен па да се рекурзија прекине.

„Мали део посла“, односно шта један позив функције ради – ово може бити очи­гле­дно, али може бити и мање видљиво, зависно од проблема. У нашем слу­чају то је просто враћање резултата множења n-а са „нечим“. То „нешто“ је у ствари позив те исте функције (односно повратна вредност тог позива), али то нас за сада не интересује. Линија кода је return n*fact(n-1); . Само ово што је подвучено је у ствари тај „мали део посла“. Значи return n*. Другим речима: врати n помножено са ...

Рекурзивни позив – овде долазимо до суштине рекурзије, односно ово је место где функција позива саму себе. У примеру је то линија return n*fact(n-1). Подвучен је рекурзивни позив. Пошто је 5! у ствари 5*4! овај позив fact(n-1) је, за n=5, управо израчунавање 4!. Замислите се мало над примером. Још нешто можемо издвојити као правило: следећем рекурзивном позиву функције никад неће бити дати потпуно исти параметри које је добила функција у којој се дешава овај позив. У нашем случају, у првом позиву, функција је добила број 5, али је поново позвала саму себе са бројем 4 (односно n-1, где је n=5). Разлог за ово правило је тај што ако би функција поново добила исте пара­метре, онда би се и понашала на исти начин стално и изнова, па рекурзија никад не би стала. То би нас опет довело до „пуцања“ програма.

Уместо закључка

Ако сте из свега овога разумели рекурзију – одлично! То значи да сте врло паметни и екстра талентовани за програмирање, на чему вам честитам :).

Ако нисте разумели – онда сте исти као и ја, ваш наставник, на чему вам не честитам! :) Мени је требало пууууно времена да ово схватим.

Али сам ипак успео, па сам сигуран да ћете и ви, када на вежбама и каснијим преда­вањима прођемо кроз још неке примере и објашњења. Пробајте мало и да „гуглате„ рекурзију на интернету, наћи ћете море корисних линкова.