|
HOW ARE YOU
[[Datoteka:Droste.jpg|mini|Vizualni oblik rekurzije poznat kao ''[[Droste učinak]]''.]]
'''Rekurzija''' je u [[matematika|matematici]] i [[računarstvo|računarstvu]] metoda definiranja [[funkcija (matematika)|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.
== Formalne definicije rekurzije ==
U [[matematika|matematici]] i [[računarstvo|računarstvu]], rekurzija specificira (ili konstruira) klasu objekata ili metoda (ili 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 pretci (''osnovni slučaj'');
* Roditelji bilo kojeg pretka su također pretci 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 [[prirodni broj|prirodnih brojeva]] u teoriji skupova jest: 1 je prirodni broj, i svaki prirodni broj ima sljedbenika koji je također prirodni broj.<br />
Drugi poznati primjer rekurzije u matematici su [[Fibonaccijev broj|Fibonaccijevi brojevi]].
== Rekurzija u programiranju ==
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: <math>F(n) = F(n - 1) + F(n - 2)</math>
Kod u programskom jeziku [[C++]] izgleda ovako
<pre>
long fib(unsigned long n) {
if (n <= 1) {
return n;
} else {
return n+fib(n-1);
}
}
</pre>
== Vidi još ==
* [[Lijeva rekurzija]]
{{mrva-rač}}
[[Kategorija:Teorija računanja]]
| 