thumb|396x396px|Дрво створено коришћењем језика Лого и ослањајући се на рекурзију Рекурзија у компјутерској науци је метод где решење проблема зависи од решења мањих случајева истог проблема (за разлику од  итерација). Овај приступ се може применити на многе врсте проблема, а рекурзија је једна од централних идеја компјутерских наука."Снага рекурзије очигледно лежи у могућности дефинисања бесконачног низа објеката до коначног саопштења. На исти начин, бесконачан број израчунавања може се описати коначном рекурзијом програма, чак и ако тај програм не садржи изричита понављања."Већина рачунарских програмских језика подржавају рекурзију дозвољавајући функцији да се позове у тексту програма. Неки  функционални програмски језици  не дефинишу никакве петље конструкције, али ослањају се искључиво на рекурзије да стално зову код. Рекурзивна теорија доказује да ови строго рекурзивни језици су Тјуринг - комплетни ; они су рачунски јаки као и Тјуринг-комплетни императивни језици, што значи да они могу да реше исту врсту проблема као и императивни језици чак и без уобичајених структурних команди као што су "док" и "за".

Рекурзивне функције и алгоритми Заједничка тактика компјутерског програмирања је да поделите проблем у под-проблеме, истог типа као и оригинал, решити ове под-проблеме, и комбиновати резултате. Ово се често назива подели па владај метод; када се комбинује са лукап табелом која садржи резултате решавања под-проблема (да би се избегло њихово решавање у више наврата и стварања додатног времена израчунавања), може се назвати динамично програмирање или мемоизација.

Рекурзивног функција дефинисана је са један или више базних предмета, што значи улаз за које функција даје резултат тривијално (без понављања), и један или више рекурзивних случајева, што значи улаз за који се програм враћа (позиви се) . На пример, функција факторијел fсе може рекурзивно дефинисати једначинама  0! = 1, а за све n > 0, n! = n(n − 1)!. Ниједна једначина по себи представља потпуну дефиницију; први је основни случај, а други је рекурзивни случај. Будући да основни случај прекида ланац рекурзије, понекад се такође назива и "завршен случај".

Посао рекурзивних случајева може се посматрати као разбијање сложених улаза у једноставније. У правилно дизајнираној рекурзивној функцији, са сваким рекурзивним позивом, проблем улаза мора бити поједностављен на такав начин да на крају основног случаја мора бити постигнут. (Функције које нису намењене да доврше под нормалним околностима, на пример, неки систем и сервер процеси-су изузетак). Занемарити да се напише основни случај, или тестирати за то погрешно, може изазвати бесконачну петљу.

За неке функције (као што је она која израчунава ред за e = 1/0! + 1/1! + 1/2! + 1/3! + ...) не постоји очигледан основни случај подразумеван од стране улазних података; за ово се може додати параметар (као што је број услова који се додаје, у нашем примеру серије) да обезбеди 'заустављање критеријума' који успоставља основни случај. Такав пример је природно више третирати ко-рекурзије, где узастопни термини у излазу су парцијалне суме; ово се може конвертовати у рекурзије користећи индексирања параметара "израчунати n-ти термин (n-ти парцијални збир)".

Рекурзивни типови података Многи компјутерски програми  морају обрадити или генерисати произвољно велике количине података. Рекурзија је једина техника за представљање података чију тачну величину програмер не зна: програмер може навести ове податке са самореферентне дефиниције. Постоје две врсте самореферентних дефиниција: индуктивне и коиндуктивне дефиниције.

Индуктивно дефинисани подаци Индуктивно дефинисан рекурзивни податак је онај који одређује како изградити пример података. На пример,  повезана листа се може дефинисати индутивно (коришћењем Хаскелове синтаксе): data ListOfStrings = EmptyList | Cons String ListOfStrings Код изнад одређује листу стригова да буде празна, или структура која садржи стринг и листу стрингова. Само-референца у дефиницији дозвољава изградњу листа неког (коначниог) броја стрингова.

Други пример индуктивне дефиниције је природан број (или позитивни цео број): Природан број је 1 или n+1, где је n природан број. Слично, рекурзивне дефиниције се често користе за моделирање структуре израза и изјава у програмирамском језику. Језички дизајнери често изражавају граматику у синтакси као што је  Бакус-Наурова форма; овде је таква граматика, за једноставним језиком аритметичких израза са множењем и сабирањем: <expr> ::= <number> | (<expr> * <expr>) | (<expr> + <expr>)Ово каже да је израз или број, производ два израза, или збир два израза. Рекурзија која се односи на изразе у другој и трећој линија, граматика дозвољава произвољно сложене аритметичке изразе као што су   (5 * ((3 * 6) + 8)), са више од једног производа или збира операција у једном изражавању.

Коиндуктивно дефинисани подаци и корекурзија Коиндуктивна дефиниција података је она која одређује операције које се могу обављати на делу података; типично, самореференцијална коиндуктивна дефиниција се користи за структуре података бесконачне величине.

Коиндуктивна дефиниција безброј токова стрингова, неформално, може да изгледа овако: Ток стрингова је објекат s тако да: глава(s) је стринг, а реп(s) је ток стрингова.

Ово је веома слично индуктивној дефиницији листе стрингова; разлика је у томе што ова дефииција одређује како да приступите садржају података структуре наиме, преко аксесор функција глава и реп— и који то садржаји могу бити, док индуктивна дефиниција одређује како да креирате структуру и шта може бити креирано од.

Корекурзија односи се на коиндукцију, и може се користити за рачунање посебних случајева (евентуално) бесконачних објеката.  Као техника програмирања, користи се најчешће у контексту лењих програмских језика, и може бити боље да рекурзија када жељена величина или прецизност програма  излаз је непознат. У таквим случајевима програм захтева и дефиницију за бесконачно велики (или бесконачно прецизан) резултат, и механизам за узимање коначног дела тог резултата. Проблем израчунавања првих n простих бројева је онај који се може решити са корекурзивним програмом.

Врсте рекурзије

Једнострука и вишеструка рекурзија Рекурзија која садржи само једну референцу позната је као једнострука рекурзија, док рекурзија која садржи више само-референца је позната као вишеструка рекурзија. Стандардни примери једноструке рекурзије укључују листу ношења, као што су линеарно тражење, или рачунање факторијела, док стандардни примери вишеструке рекурзије укључују  обилазак стабла, као што у дубини првог тражења, или рачунања Фибоначијевог низа.

Једнострука рекурзија је често много ефикаснија од вишеструке рекурзије, и генерално се могу заменити итеративним рачунањем, ради у линеарном времену и захтева стални простор. Вишеструка рецурзија, с друге стране, може да захтева експоненцијално време и простор, и важније рекурзивни, не могу да буду замењени итерацијом без експлицитног стека.

Вишеструка рекурзија понекад може бити конвертована у једноструку рекурзију (и, ако се жели, одатле у итерацију). На пример, док рачунање Фибоначијевог низа је вишеструка итерација, свака вредност захтева две претходне вредности, то може да се израчуна једноструком рекурзијом коришћењем две узастопне вредности као параметре. Ово је више природно урамљено као корекурзија, изградња од почетних вредности, праћење на сваком кораку две узастопне вредносте - види корекурзија: примери. Софистицирани пример користи бинарно стабло нити, које омогућава итеративни обилазак стабла, пре него вишеструка рекурзија.

Индиректна рекурзија Већина основних примера рекурзије, и већина од примера који су овде, показују директну рекурзију, у којој се функција зове. Индиректна рекурзија настаје када се функција не зове само по себи већ другу функцију да се зове (директно или индиректно). На пример, ако  f позива f , то је директна рекурзија, али ако f позива g којом се позива f, онда је то индиректна рекурзија f . Ланци од три или више функција су могуће; на пример, функција 1 позива функцију 2, функција 2 позива функцију 3, и функција 3 позива функцију 1 поново.

Индиректна рекурзија се такође назива и  узајамна рекурзија, што је више симетрична термину, мада то је једноставно разлика нагласка, а не разликује појам. То је, ако f позива g, а затим g позива f, што заузврат опет позива g, са тачке гледишта f , f је посредно рекурзија, док са тачке гледишта  g, то је индиректна рекурзија, док са тачке гледишта оба f и g је вишеструка рекурзија једна на друге. Слично сет од три или више функција које позивају једни друге може се назвати скуп међусобно рекурзивних функција.

Анонимна рекурзија Рекурзија се обично врши позивањем функција по имену. Међутим, рекурзија може да се уради преко имплицитног позивања функција заснована на тренутном контексту, што је посебно корисно анонимне функције, и познат је као  анонимна рекурзија.

Структурна у односу на генеративне рекурзије Неки аутори класификују рекурзију као  "структурну" или "генеративну". Разлика се односи на који рекурзивни поступак добије податке на који ради, и како се обрађују те податке: [Функције које конзумирају структурирани податак] обично разлаже своје аргументе у своје непосредне структурне компоненте, а затим обрађује те компоненте. Ако један од непосредних компоненти припада истој класи података као улаз, функција је рекурзивна. Из тог разлога, говоримо о овим функцијама као (структурно) рекурзивним функцијама.Дакле, дефинисање карактеристика структурално рекурзивних функција је да аргумент за сваки рекурзивни позив је садржај поља оригиналног улаза. Структурна рекурзија обухвата скоро све обиласке стабла, укључујући XML прераде, бинарног стабла креирања и претраге, итд. Узимајући у обзир алгебарску структуру природних бројева (који је, природан број је или нула или наследник природног броја), функција као факторијел се такође може сматрати структурном рекурзијом.

Генеративна рекурзија  је алтернатива. Многи познати рекурзивни алгоритми генеришу потпуно нови податак из датих података и враћамо на њу. HtDP (Како осмислити програм) се односи на ову врсту као генеративне рекурзије. Примери генеративних рекурзија укључују Еуклидов алгоритам, квиксорт, бинарна претрага, сортирање са спајањем, Њутнова метода, фрактал, и прилагодљива интеграција.

Ова разлика је важна за доказивање престанка функције.   Све структурно рекурзивне функције на коначне (индуктивно дефинисано) структуре података се лако може показати да доврши, преко структурне индукције: интуитивно, сваки рекурзивни позив добија мањи део улазних података, док се не постигне основни случај. Генеративне рекурзивне функције, насупрот томе, не морају хранити мањи улаз својим рекурзивним позивима, тако да говорити о њиховом раскиду није нужно тако једноставно, и избегавање бесконачне петље захтева већу бригу. Ове генеративне рекурзивне функције често се могу тумачити као корекурзивне функције - сваки корак генерише нове податке, као што су сукцесивна апроксимација у Њутновој методи - и довршетак ове корекурзије захтева  да подаци на крају задовоље неке услове, није гарантовано. Што се тиче варијанти петље, структурна рекурзија је када постоји очигледна варијанта петље, односно величина или комплексност, која почиње коначано и смањује се на сваком рекурзивном кораку.  Насупрот томе, генеративна рекурзија је кад не постоји таква очигледна варијанта петље, и престанак зависи од функције, као што је  "грешка приближавања", то не мора да се смањи на нулу, и на тај начин раскид није загарантован без даљих анализа.

Рекурзивни програми

Рекурзивне процедуре

Факторијел Класичан пример рекурзивне процедуре је функција коришћена за рачунање  факторијела природног броја:

Псеукод (рекурзивно: function factorial is:

input: integer n such that n >= 0

output: [n × (n-1) × (n-2) × … × 1]

1. if n is 0, return 1 2. otherwise, return [ n × factorial(n-1) ]

end factorial Функција се може записати и као рекурзивни однос: