Что такое рекурсия в С++

Рекурсия в С++ иногда называемая циклическим определением, представляет собой процесс определения чего-либо на собственной основе. В программирование это процесс вызова функцией самой себя. Функция которая вызывает саму себя называют рекурсивной.

Рассмотрим процесс рекурсии при вычислении факториала числа 3. Он равен 6 = 1х2х3

Сначала нерекурсивная версия программы:

int fact (int n);
int main ( )
{
    cout<<"fact 5 = " << fact(5);
    return 0;
}
int fact (int x){
    int answer=1;
    for (int i=1; i<=x; i++) answer=answer*i;
    return answer;
}

Тут используется цикл, в котором перемножаются последовательно числа от 1 и заканчивая числом заданным в качестве параметра.

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

А теперь тоже самое но с рекурсией:

int factr (int n);
int main ( )
{
    cout<<"fact 5 with recursion = " << factr(5);
    return 0;
}
int factr (int n){
    int answer;
    if (n==1) return 1;
    answer = factr (n-1)*n;
    cout << answer << '\n'; // 2 6 24 120 fact 4 with recursion = 120
    return answer;
}

Рекурсивная функция factr() несколько сложнее. Если она вызывается с аргументом, равным 1, то сразу возвращает значение 1. В противном случае она возвращает произведение factr(n-1)*n. Для вычисления этого выражения вызывается метод factr() с аргументом n-1. Этот процесс повторяется до тех пор, пока аргумент не станет равным 1, после чего вызванные ранее методы начнут возвращать значения. Например, при вычислении факториала числа 2 первое обращение к методу factr() приведет ко второму обращению к тому же методу, но с аргументом, равным 1. Второй вызов метода factr() возвратит значение 1, которое будет умножено на 2 (исходное значение параметра n). Возможно, вам будет интересно вставить в функцию factr() инструкции cout, чтобы показать уровень каждого вызова и промежуточные результаты и мы можем увидеть, что рекурсия начинает выполнятся с конца, то есть сначала 1*2 и так далее.

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

Следует иметь в виду, что в большинстве случаев использование рекурсивных функций не дает значительного сокращения объема кода. Кроме того, рекурсивные версии многих процедур выполняются медленнее, чем их итеративные эквиваленты, из-за дополнительных затрат системных ресурсов, связанных с многократными вызовами функций. Слишком большое количество рекурсивных обращений к функции может вызвать переполнение стека. Поскольку локальные переменные и параметры сохраняются в системном стеке и каждый новый вызов создает новую копию этих переменных, может настать момент, когда память стека будет исчерпана. В этом случае могут быть разрушены другие (“ни в чем не повинные”) данные. Но если рекурсия построена корректно, об этом вряд ли стоит волноваться.

Основное достоинство рекурсии состоит в том, что некоторые типы алгоритмов рекурсивно реализуются проще, чем их итеративные эквиваленты. Например, алгоритм сортировки Quicksort довольно трудно реализовать итеративным способом. Кроме того, некоторые задачи (особенно те, которые связаны с искусственным интеллектом) просто созданы для рекурсивных решений. Наконец, у некоторых программистов процесс мышления организован так, что им проще думать рекурсивно, чем итеративно.

При написании рекурсивной функции необходимо включить в нее инструкцию проверки условия (например, if-инструкцию), которая бы обеспечивала выход из функции без выполнения рекурсивного вызова. Если этого не сделать, то, вызвав однажды такую функцию, из нее уже нельзя будет вернуться. При работе с рекурсией это самый распространенный тип ошибки. Поэтому при разработке программ с рекурсивными функциями не стоит скупиться на инструкции cout, чтобы быть в курсе того, что происходит в конфетной функции, и иметь возможность прервать ее работу в случае обнаружения ошибки.

Еще один пример рекурсии, который выводит строку в обратном порядке:

void revers (char *s);
int main ( )
{
    char str[] = "Hello";
    revers (str);
    return 0;
}
void revers (char *s){
    if (*s) {revers (s+1);}
    else return;
    cout << *s;
}

Здесь с помощью указателей и рекурсии заносим каждую букву строки в память, а когда дойдем до конца строки \0 (условие if (*s) )  то рекурсия закончится и начнутся выводится символы *s.

Функция reverse () проверяет, не передан ли ей в качестве параметра указатель на нуль, которым завершается строка. Если нет, то функция reverse () вызывает саму себя с указателем на следующий символ в строке. Этот “закручивающийся” процесс повторяется до тех пор, пока той же функции не будет передан указатель на нуль. Когда наконец, обнаружится символ конца строки, пойдет процесс “раскручивания”, т.е. вызванные ранее функции начнут возвращать значения, и каждый возврат будет сопровождаться “довыполнением” метода, т.е. отображением символа s. В результате исходна строка посимвольно отобразится в обратном порядке.