Рекурзија
Из пројекта Википедија
Рекурзија (лат: recursio, recursion од recurrere: враћање) у математици и информатици означава функцију или процедуру која у својој дефиницији користи саму себе. Једноставније речено, уколико у току обраде неких података по поступку, чији су кораци тачно одређени, бива потребно да се цео тај поступак обави и за неке друге податке пре него што је тренутни завршен, поступак је рекурзиван. Рекурзија се не користи само за описивање алгоритама и функција, него и приликом дефинисања. Неки поступак или дефиниција описани коришћењем рекурзије се називају рекурзивним.
Садржај |
[уреди] Примери
Следе примери примене рекурзије, подељено по областима примене.
[уреди] Рекурзивне дефиниције
Природни бројеви:
- 1 је природни број
- Ако је n природни број, онда је то и n+1.
[уреди] Рекурзивни алгоритми
Значајна одлика рекурзивних алгоритама је да је њихово извршавање у пракси скоро увек ограничено фактором рачунара. Не може се очекивати да ће срачунавање неке бесконачне суме заиста бити спроведено до бесконачности, јер у пракси није ни могуће остварити бесконачно дуге или прецизна израчунавања, што због временских, што због техничких ограничења. Следи неколико имплементација.
[уреди] Вредност факторијела
Факторијел је једна од стандардних ф-ја модерне математике. Ако је неки број означен са a, његов факторијел би био означен са a!. Над скупом природних бројева се дефинише као:

Како је
, једна његова једноставна имплементација би гласила:
int fakt(int n)
{ return n<2 ? 1: n*fakt(n-1); }
Проблем код овакве имплементације би био то што тип int није у стању да прими неограничено велике бројеве.
[уреди] Сума низа који се завршава нулом
Дакле дефинисан је један низ бројева који се завршава са нулом. Треба добити његову суму помоћу рекурзије. Рецимо да низ садржи само целе бројеве. Функција ће гласити овако:
int asumm(int *p)
{ return *p ? *p+asumm(p+1) : 0; }
У обзир се мора, наравно, узети да тип int има своја ограничења, тј. не може да представља неограничено велике бројеве.
[уреди] Верижни разломци
Један од верижних разломака, који се везује за вредност броја пи.

Он се у програмском језику C може имплементирати на следећи начин:
double f(double a,double b)
{ return b > 1000 ? a : a + b/f(a+2,b+a+2); }
При чему се функција увек позива са f(1,1). Треба приметити да је услов b > 1000 узрок терминирања рекурзије. Он одређује да ће иста бити прекинута када вредност аргумента b, који брже расте, пређе хиљаду. Ова вредност се може поставити на доста више, но неће одати много значаја при одређивању вредности самог израза.

