Рекурсия в C++ по своим свойствам не отличатся от аналогичных конструкций в других языках. Это функция, которая вызывает сама себя, за счет чего можно считать ее альтернативой обычному циклу. Для того, чтобы это не продолжалось вечно, обычно в рекурсию добавляют условие выхода из нее.
Существует 2 типа рекурсий: прямая и косвенная. Их отличие друг от друга в том, что прямая рекурсия просто вызывает саму себя, тогда как косвенная использует две функции, каждая из которых вызывает друг друга. Рассмотрим простой пример прямой рекурсии:
|
1 2 3 4 5 |
int sum(int a) { if (a == 1) return 1; else return sum(a - 1) + a; } |
Она подсчитывает сумму всех чисел по порядку до a. Происходит это так: подается число a, сравнивается с 1, если не равно, то вызывается эта же функция, но уже с параметром a - 1, при этом к результату добавляется a, и так пока не дойдет до 1, и тогда вернет эту самую 1. Получится многослойное выражение, которое программа начнет выполнять, поэтапно добавляя 2, 3 и так далее. В итоге получится нужная нам сумма.
Существует еще одно разделение рекурсий на нисходящую и восходящую, различаются они в том, что идет сначала выполнение действия или вызов следующей функции. В примере мы взяли нисходящую, для восходящей нам потребовалась еще одна переменная, чтобы хранить значение на каждом шаге.
