Рекурсия — процесс повторения элементов самоподобным образом. Например, если два зеркала установить одно напротив другого, то возникающие в них вложенные отражения - это одна из форм бесконечной рекурсии.

Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике. В математике и информатике рекурсия имеет отношение к методу определения функций: рекурсивно заданная функция в своём определении содержит саму себя, в частности, рекурсивной является функция, заданная рекуррентной формулой. Таким образом, можно одним выражением дать бесконечный набор способов вычисления функции, определить множество объектов через самого себя с использованием ранее заданных частных определений.

С рекурсией тесно связана математическая индукция: она является естественным способом доказательства свойств функций на натуральных числах, рекурсивно заданных через свои меньшие значения.

В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.

Реализация рекурсивных вызовов функций в практически применяемых языках и средах программирования, как правило, опирается на механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно. Оборотной стороной этого довольно простого по структуре механизма является то, что на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вследствие этого, обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии.

• Рекурсией называется вызов функции из самой себя.
  
• Рекурсия бывает прямой и косвенной.
  
• Прямая рекурсия – это если функция содержит в своем теле вызов самой себя
  
• Косвенная рекурсия – это если первая функция вызывают вторую функцию, но при этом в теле второй функции прописан вызов первой.
  
• Рекурсия позволяет без видимых повторяющихся функций
  

Например функция, которая считает сумму всех чисел от 0 до "n":



Многие скажут, что это бред и легче сделать цикл ( с чем я согласен ), но в некоторых случаях рекурсия здорово выручает.
Например при решении задач на рекурентные формулы ( http://ru.wikipedia.org/wiki/Рекуррентная_формула ) и для много ещё чего

Основная проблема - это создание бесконечной рекурсии. Это когда функция начинает вызывать сама себя бесконечно, что приводит к аварийному завершению программы.
Что бы избежать таких ситуаций нужно всегда ставить точку выхода из рекурсивной функции.

Вернёмся к функции, описанной выше. И подробно рассмотрим строку:


Если бы не было этой проверки то при n=1, функция бесконечно складывала бы 1+0=1. Это вызывало бы бесконечную рекурсию.

Рекурсия очень полезная вещь, которая помогает в решении сложных задач. Но в простых функциях, типа нахождения факториала, суммы n чисел и т.д., использовать не стоит, потому что есть опасность появления бесконечной рекурсии, к тому же рекурсия значительно проигрывает циклам в скорости.