Рекурзија
Из пројекта Википедија
Рекурзија (лат: 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(int a,int b,int cc)
{ return b>>8 ? a : a+b/f(a+2,b+cc,cc+2); }
При чему се функција увек позива са f(1,1,3). Треба приметити да је услов b>>8 узрок терминирања итерација. Он одређује да ће исте бити прекинуте при првом заузећу неког бита промењиве b који заузима место са редним бројем већим од осам. Ова променљива је изабрана јер јој је раст најбржи те је, како су вредности осталих због релативно блиских полазних вредности увек мање од ње, најпогондија за контролу прекорачења опсега вредности које се могу репрезентовати изабраним типом. У овом случају се итерације прекидају много пре прекорачења, али ипак довољно касно, да би вредност резултата била веродостојна.
