Algoritmid ja rekursioon

Tuum

Algoritm on täpne sammude jada probleemi lahendamiseks. Rekursioon tähendab, et objekt või arvutus määratletakse eelmiste väärtuste kaudu.

Hea algoritm kirjeldab:

• sisendit: millised andmed antakse;
• samme: mida nendega tehakse;
• väljundit: mis tulemus saadakse;
• lõpetamistingimust: millal töö lõpeb.

Valemid ja tingimused

Fibonacci jada:

$$F_1=1,\qquad F_2=1,$$

$$F_n=F_{n-1}+F_{n-2}.$$

Siin on peatustingimused $F_1=1$ ja $F_2=1$. Ilma nendeta ei teaks, kust arvutamist alustada.

Rekursioonis peab iga samm liikuma lihtsama juhu poole: $F_6$ vajab $F_5$ ja $F_4$, need vajavad veel varasemaid liikmeid, kuni jõutakse väärtusteni $F_1$ ja $F_2$.

Kiirnäide

Leia $F_6$.

Alustame teadaolevatest algväärtustest:

$$F_1=1,\quad F_2=1.$$

Seejärel kasutame reeglit $F_n=F_{n-1}+F_{n-2}$:

$$F_3=F_2+F_1=1+1=2,$$

$$F_4=F_3+F_2=2+1=3,$$

$$F_5=F_4+F_3=3+2=5,$$

$$F_6=F_5+F_4=5+3=8.$$