Рекурсия

В C++ любая функция кроме main() может вызывать саму себя. То есть в теле функции может быть размещен вызов этой же функции. Это называется рекурсией.

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

#include <iostream>

using namespace std;

 

void recursionGoDown(int someNumber)

{

cout << "Спуск по рекурсии: " << someNumber << endl;

if (someNumber > 0)

{

recursionGoDown(someNumber - 1); // рекурсивный вызов

}

cout << "Возврат по рекурсии: " << someNumber << endl;

}

 

int main()

{

setlocale(LC_ALL, "rus");

 

recursionGoDown(9);

return 0;

}

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

Если мы передаем в такую функцию число 9, вызовов будет 10. Программа как бы углубляется на 10 уровней, выполняя рекурсию. Чтобы ей выйти из рекурсии, надо пройти эти десять уровней обратно. Так строка кода

cout << "Возврат по рекурсии: " << someNumber << endl;

будет выполняться тоже 10 раз, но значение someNumber будет меняться в обратном порядке. Сначала оно будет соответствовать тому, что передалось в функцию на 10 уровне рекурсии, потом тому что передалось на 9 уровне и т.д.

Хочу обратить внимание на важный момент. При каждом рекурсивном вызове создается новая переменная someNumber с новым значением. Эти переменные будут занимать какое-то место в оперативной памяти. Если вызовов 10, как в нашем примере, то и в памяти будет храниться 10 переменных с разными значениями. Можно дописать в программу вывод на экран адресов, по которым хранятся эти значения и убедиться в этом:

#include <iostream>

using namespace std;

 

void recursionGoDown(int someNumber)

{

cout << "Спуск по рекурсии: " << someNumber << ". &someNumber: "<< &someNumber << endl;

if (someNumber > 0)

{

recursionGoDown(someNumber - 1); // рекурсивный вызов

}

cout << "Возврат по рекурсии: " << someNumber << ". &someNumber: " << &someNumber << endl;

}

 

int main()

{

setlocale(LC_ALL, "rus");

 

recursionGoDown(2);

return 0;

}

Передаем в функцию число 2: recursionGoDown(2); Уровней рекурсии будет 3.

Как видно, каждое значение переменной someNumber хранится в отдельном отрезке памяти. Во время обратного выхода по рекурсии значения берутся из тех же адресов но в обратном порядке.

Практически каждую поставленную задачу, которую можно решить используя рекурсию, можно реализовать используя итерации циклов. Вы ведь легко можете показать на экран числа от 9 до 0 и от 0 до 9 применив циклы. Помимо этого следует знать, что рекурсия займет больше памяти и будет производить вычисления медленнее, чем итерация.

Но, как утверждают опытные программисты и многие авторы книг, это не значит, что рекурсия бесполезна. Есть задачи, решать которые, используя итерации циклов, сложно и громоздко. А рекурсивное решение выглядит лучше. Для начального уровня, пока вы изучаете только основы программирования на C++, вам достаточно просто понимать, что из себя представляет рекурсия и как она работает.