Rekurzija je postopek pri programiranju, pri katerem definiramo tako funkcijo, da se nanjo sklicujemo ob njenem izvajanju. To pomeni, da funkcijo definiramo samo s seboj. V opisu postopka izvajanja funcije, zapišemo kar to funkcijo, vendar jo vršimo nad drugačnim (manjšim) obsegom podatkov.

Postopek rekurzivnega zapisa funkcije, si najlažje predstavljamo s FRAKTALI.

Kaj so fraktali? Fraktali so objekti, ki zagotavljajo enako raven podrobnosti, ne glede na resolucijo, ki jo uporabljamo.

Če se osredotočimo na delček fraktala, zopet dobimo enako obliko kot jo ima celoten fraktal. Delčke lahko neskončno povečujemo, vendar vedno dobimo isto(začetno) obliko.

Domišljisko drevo:

vir: http://www.kokcanlandirma.com

Kot vidimo, je vsaka od vej na drevesu enaka celotnemu drevesu.

Brokoli:

vir: www.wired.com

vir: www.wired.com

Če brokolijo odrežemo delček, je ta po izgledu enak celemu brokoliju.

Več o fraktalih v naravi najdeš na spletni strani: Fraktali v naravi

Tako kot pri fraktalih, lahko tudi pri rekurzivnem zapisu funkcije, celoten problem razrežemo na manjše delčke in na vsakem od manjših delčkov delujemo s funkcijo. Nato pa vse skupaj spet sestavimo v celoto. Vendar pa se mora rekurzija nekje tudi končati. V nasprotnem primeru se izvajanje funkcije ne bi nikoli končalo. Ko problem razbijamo na vedno manjše probleme, moramo priti do problema, ki ima enostavno rešitev. Rečemo, da smo 'prišli' do ustavitvenega pogoja. V tem trenutku se rekurzivno izvajanje funcije konča, in se začne sestavljanje rešitev posameznih problemov v skupno rešitev.

Primer fraktalov je Kochova snežinka.

Kochove snežinke različnih stopenj dobimo tako, da stranice enakostraničnega trikotnika razdelimo na tretjine ter nad srednjo tretjino dodamo ustrezen trikotnik - dobimo nekakšne prirastke. V naslednji stopnji ponovno vsem stranicam narišemo prirastke.

Primeri Kochovih snežink stopnje 0, 1, 2, 3 in 4 in 5:

Posvetimo le delčku Kochove snežinke - Kochovi črti.(Eni stranici enakostraničnega trikotnika).

Kot vidimo na spodnji sliki, se z večanjem stopnje na vseh ravnih črtah pojavljajo izbokline-prirastki. Le-te se pojavijo na srednji tretjini. Črta stopnje n vsebuje 4 črte, ki so podobne črti stopnje n-1, vendar so trikrat krajše. To pomeni, da lahko tudi tukaj govorimo o fraktalih.

Kochova črta stopnje 1, 2, 3, 4 in 5

Dolžino Kochove črte poljubne stopnje bomo s pomočjo rekurzije izračunali v nadaljevanju, najprej pa si poglejmo enostavnejši primer, pri katerem lahko uporabimo rekurzijo.

Naloga:

S pomočjo rekurzije izračunaj vsoto naravnih števil na intervalu [a,b]:

Python datoteka

Podrobneje poglejmo kaj se dogaja, ko se izvaja prej napisana rekurzivna funkcija.

Za primer vzemimo, da naj funkcija sešteje vsa števila na intervalu [1,4].

To pomeni, da je na začetku vrednost parametra  a = 1  , vrednost parametra  b = 4  .

Ko zaženemo funkcijo:

Ker je vrednost parametra b večja od vrednosti parametra a, je izpolnjen prvi pogoj, v katerem se nahaja rekurzivni klic iste funkcije s parametroma  a=1  in  b-1=3  . Zato se funkcija še enkrat izvede z novimi parametri:

Izvede se rekurzivni klic funkcije  vsotaŠtevil(1,2)  :

Nato pa se izvede rekurzivni klic funkcije s parametroma  a = 1  in  b = 1  . Tokrat je zadoščeno drugemu pogoju, ki nam kot rezltat vrne kar vrednost parametra  a  , ki je v našem primeru enak 1. Prišli smo do ustavitvenega pogoja in klici rekurzije v globino se končajo.

Sedaj moramo vse skupaj sešteti skupaj. To storimo tako, da gremo od konca proti začetku:

 vsota = 4 + vsotaŠtevil(1,3)

            vsotaŠtevil(1,3) = 3 + vsotaŠtevil(1,2)

                                   vsotaŠtevil(1,2)=2 + vsotaŠtevil(1,1)

                                                        vsotaŠtevil(1,1)= 1 

Prišli smo do ustavitvenega pogoja - rekurzija se ustavi. Sedaj lahko v obratni smeri pridemo do končne rešitve:

                                                                    vsotaŠtevil(1,1)= 1

                                   vsotaŠtevil(1,2) = 2 + 1 = 3

            vsotaŠtevil(1,3) = 3 + 3 = 6

vsota = 4 + 6

vsota = 10
 

Pa poglejmo kako bi zapisali funkcijo, s katero bi izračunali dolžino Kochove črte poljubne stopnje.

Python datoteka

Poglejmo primer izračuna dolžine Kochove črte z osnovno dolžino 9, stopnje 2.

Funkcija dobi za parametra števili 9 in 2:

Prednost pri zapisu z rekurzijo je v tem, da lahko nek postopek ali formulo za izračun zapišemo le enkrat, nato pa jo v eni sami funkciji večkrat uporabimo.