Rekurzija
Rekurzija je u matematici i računarstvu metoda definiranja funkcija u kojima se definirajuća funkcija primjenjuje unutar definicije. Naziv se općenitije rabi za opis procesa ponavljanja objekata na samosličan način. Primjerice, kada su površine dvaju zrcala gotovo uzajamno paralelne, ugniježđene slike koje se pojavljuju su oblik rekurzije.
U matematici i računarstvu, rekurzija specificira (ili konstruira) klasu objekata ili metoda (objekata iz određene klase) definiranjem nekoliko jednostavnih osnovnih slučajeva ili metoda (često samo jednu), i potom definiranjem pravila za razbijanje složenih slučajeva u jednostavnije.
Na primjer, sljedeće je rekurzivna definicija predaka osobe:
- Nečiji roditelji su njegovi predci
- Roditelji bilo kojeg pretka su također predci osobe koju promatramo (korak rekurzije).
Zgodno je zamisliti da rekurzivna definicija definira objekte u terminima "prethodno definiranih" objekata definirajuće klase.
Definicije poput ove su česte u matematici. Primjerice, formalna definicija prirodnih brojeva u teoriji skupova jest: 1 je prirodni broj, i svaki prirodni broj ima sljedbenika koji je također prirodni broj.
Drugi poznati primjer rekurzije u matematici su Fibonaccijevi brojevi.
Fibonačijevi brojevi su brojevi koji se sastoje od zbroja 2 prethodna. Tu definiciju možemo iskoristiti kako bismo si lakše predočili rekurziju.
Rekurzivna formula za izračunavanje n-tog fibonačijevog broja glasi:
Kod u programskom jeziku C++ izgleda ovako
long fib(unsigned long n) {
if (n <= 1) {
return n;
} else {
return fib(n-1)+fib(n-2);
}
}
| ||||||||||||||||||||||||||||||||||||||||||||||||||