Рекурсия – это прием программирования, при котором программа вызывает саму себя либо непосредственно, либо косвенно. Функция называется прямо рекурсивной, если содержит в своем теле вызов самой себя. Если же функция вызывает другую функцию, которая в свою очередь вызывает первую, то такая функция называется косвенно рекурсивной.

Как правило, неопытный программист, узнав про рекурсию, испытывает легкое недоумение. Первая мысль – это бессмысленно!!! Такой ряд вызовов превратиться в вечный цикл, похожий на змею, которая съела сама себя, или приведет к ошибке на этапе выполнения, когда программа поглотит все ресурсы памяти. Однако рекурсия – это превосходный инструмент, который при умелом и правильном использовании поможет программисту решить множество сложных задач.

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

Прямой (непосредственной) рекурсией является вызов функции внутри тела этой функции.

int a()
{.....a().....}

Косвенной рекурсией является рекурсия, осуществляющая рекурсивный вызов функции посредством цепочки вызова других функций. Все функции, входящие в цепочку, тоже считаются рекурсивными.

Например:

a(){.....b().....}
b(){.....c().....}
c(){.....a().....}

Все функции a,b,c являются рекурсивными, так как при вызове одной из них, осуществляется вызов других и самой себя.

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

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

Значит ли это, что рекурсия бесполезна? Ни в коем случае!!! Существует ряд задач, для которых рекурсивное решение тонко и красиво, а итеративное – сложно, громоздко и неестественно.

Когда применять рекурсию?

• для решения задач, для которых свойственна следующая черта: решение задачи сводится к решению таких же задач, но меньшей размерности и, следовательно, гораздо легче разрешаемых.

• Задачи Олимпиады для языка C
• Типовые задачи и решения языка CPP
• Динамические структуры данных
• Бинарное дерево С++