Rekurzija

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: ${\displaystyle F(n)=F(n-1)+F(n-2)}$ 

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);     } } 

• Lijeva rekurzija

 

Nedovršeni članak Rekurzija koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima Wikipedije.