Definicija rekurzije

V Slovarju slovenskega knjižnega jezika SSKJ ni besede rekurzija, pojavlja pa se beseda rekurz -a m ( Beseda rekurzívno (latinsko recurrere, kar pomeni teči nazaj) pomeni nanašajoče na samega sebe.

Na področju matematike rekurzija predstavlja zaporedje, katerega n-ti člen je določen z enim ali več predhodnimi členi.

Z vidika informatike pa rekurzija predstavlja definiranje funkcije ali postopka s samim seboj.

Ali - rešitev problema, podanega s samim problemom le nad manjšim obsegom podatkov. Torej v opisu postopka rešitve uporabimo kar ta postopek.

Rekurzivni klic gre skozi druge funkcije, ki so med med seboj rekurzivne.

Rekurzivna funkcija, ko jo pokličemo, se po definiciji nikoli ne konča. Če želimo priti do rešitve, postopka ne moremo nadaljevati v nedogled. Torej je potreben ustavitveni pogoj. Kdaj v postopku ne uporabimo istega postopka? Običajno takrat, ko je problem dovolj majhen (enostaven).

Algoritem rekurzije

Rekurzivni algoritem vsebuje naslednja pravila:

1. Definiran mora biti najmanjši ali najbolj enostaven problem, ki se ga da preprosto rešiti. Če je problem majhen, funkcija vrne kar to rešitev. V nasprotnem primeru funkcija razdeli problem na manjše podprobleme iste vrste.
2. Funkcija mora klicati samo sebe.
3. Funkcija mora prehajati preko vseh manjših podproblemov k enostavnemu problemu, s katerim se funkcija konča. To je tudi ustavitveni pogoj.

Kako bi napisali rekurzivno funkcijo za izpis števil do n?

Zaslonska slika Rekurzija

Denimo, da bi radi izračunali vsoto števil v seznamu: sez = [1,5,2,6,4]

Z zanko bi se problema lotili tako:

Algoritem za rekurzijo bi v tem primeru lahko nastavljali na ta način:

Vsoto danih števil lahko dobimo tako, da najprej seštejemo sosednji števili z enega konca seznama, nato pa tej vsoti na isti način dodajamo naslednje število v seznamu. S ponavljanjem tega vzorca gre torej po dolžini celotnega seznama za prištevanje dveh sosednjih števil na isti način, kot v začetku. Torej, kakor je za rekurzijo značilno, najprej rešimo problem na najmanjšem delu (seštejemo dve števili), nato pa rekurzivno zankamo na preostanku števil.

Rešitev lahko ponazorimo z vrivanjem seštevkov v oklepaje:

((((1+3)+5)+7)+9)

ali pa z duge strani seznama;

(1+(3+(5+(7+9))))

Vidimo, da je najglobji oklepajen seštevek v slednjem primeru (7+9) rešljiv brez zanke ali kakršnegakoli konstrukta. To prvotno rešitev problema ponavljamo vse do konca seznama, dokler ne pridemo do zaustavitvenega pogoja (en sam element v seznamu).

• vsota = (1+(3+(5+(7+9))))
• vsota = (1+(3+(5+16)))
• vsota = (1+(3+21))
• vsota = (1+24)
• vsota = 25

Kako bi na osnovi tega algoritma izpisali kodo?

Preprosto lahko rečemo tako: Vsota števil v seznamu je vsota prvega števila in vsote števil v preostanku seznama. Rekurzivno gledano gre torej za:

vsotaSeznam(seznam) = prvoStevilo(seznam) + vsotaSez(preostanek(seznam))

Program:

Še pogled celotnega postopka rekurzivne funkcije:

Na spodnji sliki vidimo serijo rekurzivnih klicev za vsoto števil v seznamu.

Pri vsakem rekurzivnem klicu v bistvu rešujemo vedno manjši problem vse dokler ne pridemo do točke, ko problem ne more biti več manjši.

Zaslonska slika - Rekurzivni klici

Naslednja faza rekurzije - return

Sedaj sledi postopno vračanje. Ustavitveni pogoj nam vrne vrednost 9, tej vrednosti prištejemo 7, … itd. Ko se vrnemo nazaj k prvotnemu problemu, dobimo rešitev našega problema, ki je 25.

Zaslonska slika - vračanje pri rekurziji

Kaj vrne rekurzivna funkcija ob klicu vsotaSez([2,3,4,5]) ?

Preveri

Koliko rekurzivnih klicev se izvede pri že nam znani kodi, ko imamo v seznamu naslednja števila:

[2,4,6,8,10]

Preveri