Рекурсия — бұл көмекші алгоритмді (ішкі программаны) ұймдастырудың әдісі. Мұнда сол ішкі программа (процедура немесе функция) операторлары орындалуы кезінде өз-өзін шақырады (обращаться). Рекурсиялы деп өзі арқылы анықталатын кез келген объектіні атауға болады. Мысалы:
<екілік код> ::= <екілік цифр> | <екілік код><екілік цифр>
<екілік цифр> ::= 0 | 1
Мұнда ұғымдарды сипаттау үшіінн Бэкус-Наурдың металингвистикалық формулалары қолданылды: "::=" таңбасы "анықтама бойынша бар", ал "|" — "немесе" дегенді білдіреді. Рекурсивті анықтамада шектеу болуы керек. Басқа да мысалдарды қарастырайық:
Мысал. Рекурсияны айтқанда айтпау кетуге болмайтын классикалық мысал факториалды қарастырайық. Ол былай анықталады:
n!=1*2*3*...*n. Ал тағы бір жағынан алып қарасақ, шектік шарт n<=1.
Рекурсиялы ішкі программаны шақыру басқа да ішкі программаларды шақырудан ерекшелігі жоқ. Алайда рекурсиялы ішкі программаны шақырғанда жадыда сол ішкі программаның барлық жергілікті айнымалыларымен бірге көшірмесі пайда болады. Мұндай көшірмелер шектік шартқа жеткеше қайталана береді. Ал шектік шарт болмаса ол стек толып, программаның дұрыс аяқталмауына әкеледі. Рекурсиялы ішкі программалардың шектік шартқа жеткенге дейінгі көшірмелерінің пайда болуы рекурсивті түсу (рекурсивный спуск) деп аталады. Көшірмелердің компьютер жадысында орналасқан максималды саны рекурсия тереңдігі (глубина рекурсии) деп аталады. Ал көшірмелер алудың аяқталуы рекурсивті көтеріліс (рекурсивный подъем) ддеп аталады.
