$$ \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} \newcommand{\mod}{\,\mathrm{mod}\,} \renewcommand{\div}{\,\mathrm{div}\,} \newcommand{\metar}{\,\mathrm{m}} \newcommand{\cm}{\,\mathrm{cm}} \newcommand{\dm}{\,\mathrm{dm}} \newcommand{\litar}{\,\mathrm{l}} \newcommand{\km}{\,\mathrm{km}} \newcommand{\s}{\,\mathrm{s}} \newcommand{\h}{\,\mathrm{h}} \newcommand{\minut}{\,\mathrm{min}} \newcommand{\kmh}{\,\mathrm{\frac{km}{h}}} \newcommand{\ms}{\,\mathrm{\frac{m}{s}}} \newcommand{\mmin}{\,\mathrm{\frac{m}{min}}} \newcommand{\smin}{\,\mathrm{\frac{s}{min}}} $$
Uvod u algoritme / Rekurzija

Rekurzija

  • Dozvoljeno polaganje
  • Osnovni
  • Nema
  • Andreja Ilić
  • 2/3/2013

Rekurzija predstavlja metod u kome rešenje polaznog problema nalazimo koristeci rešenja podproblema iste strukture - jednostavnije instance istog problema. Jednostavnije instance problema se rešavaju istim principom, sve dok se ne dobije trivijalna instanca cije rešenje poznajemo. Da bi pristupili rešavanju problema rekurzijom, potrebno je da definišemo bazni slucaj (rešenje trivijalnih instanci) i rekurzivnu vezu (kako složeniju instancu problema rešiti koristeci jednostavnije instance). Ovaj pristup se može primeniti na veliku klasu problema i predstavlja jednu od centralnih ideja u racunarskim nauka.
 
Ideja rekurzije je bazirana je na matematickoj indukciji, samo obrnutog smera. Naime, vaš program prvo testira da li je zadata instanca trivijalana, primera radi da li je n=1 ili 2. Ukoliko jeste rešenje nalazite direktno (bez rekurzije). U suportnom, vi rešavate problem za dati parametar tako što pozivate tu istu funkciju sa manjim parametrom. Jednostavno, a deluje neverovatno.
 
Medutim, metod rekurzije je mac sa dve oštrice. Pored niza prednosti za ovaj metod, postoji i niz razloga zašto izbegavati isti. U samoj lekciji pokricemo sve ove osobine. Gore navedena definicija rekurzije zvuci dosta komplikovano, ali je zapravo zaista jednostavana i mocna.  Analizom primera rekurzije videcete šta je zapravo rekurzija, kako i kada se ona koristi, i možda najvažnije od svega - kako da rekurzivno razmišljate.