Когда функция вызывает сама себя, в системном стеке выделяется память для новых локальных переменных и параметров, и код функции с самого начала выполняется с этими новыми переменными. Рекурсивный вызов не создает новой копии функции. Новыми являются только аргументы. При возвращении каждого рекурсивного вызова из стека извлекаются старые локальные переменные и параметры, и выполнение функции возобновляется с "внутренней" точки ее вызова. О рекурсивных функциях можно сказать, что они "выдвигаются" и "задвигаются".
Следует иметь в виду, что в большинстве случаев использование рекурсивных функций не дает значительного сокращения объема кода. Кроме того, рекурсивные версии многих процедур выполняются медленнее, чем их итеративные эквиваленты, из-за дополнительных затрат системных ресурсов, связанных с многократными вызовами функций. Слишком большое количество рекурсивных обращений к функции может вызвать переполнение стека. Поскольку локальные переменные и параметры сохраняются в системном стеке и каждый новый вызов создает новую копию этих переменных, может настать момент, когда память стека будет исчерпана. В этом случае могут быть разрушены другие ("ни в чем не повинные") данные. Но если рекурсия построена корректно, об этом вряд ли стоит волноваться.
Основное достоинство рекурсии состоит в том, что некоторые типы алгоритмов рекурсивно реализуются проще, чем их итеративные эквиваленты. Например, алгоритм сортировки Quicksort довольно трудно реализовать итеративным способом. Кроме того, некоторые задачи (особенно те, которые связаны с искусственным интеллектом) просто созданы для рекурсивных решений. Наконец, у некоторых программистов процесс мышления организован так, что им проще думать рекурсивно, чем итеративно.
При написании рекурсивной функции необходимо включить в нее инструкцию проверки условия (например, if-инструкцию), которая бы обеспечивала выход из функции без выполнения рекурсивного вызова. Если этого не сделать, то, вызвав однажды такую функцию, из нее уже нельзя будет вернуться. При работе с рекурсией это самый распространенный тип ошибки. Поэтому при разработке программ с рекурсивными функциями не стоит скупиться на инструкции cout, чтобы быть в курсе того, что происходит в конкретной функции, и иметь возможность прервать ее работу в случае обнаружения ошибки.
Рассмотрим еще один пример рекурсивной функции. Функция reverse() использует рекурсию для отображения своего строкового аргумента в обратном порядке.
// Отображение строки в обратном порядке с помощью рекурсии.
#include <iostream>
using namespace std;
void reverse(char *s);
int main()
{
char str[] = "Это тест";
reverse(str);
return 0;
}
// Вывод строки в обратном порядке.
void reverse(char *s)
{
if(*s)reverse(s+1);
else return;
cout << *s;
}
Функция reverse() проверяет, не передан ли ей в качестве параметра указатель на нуль, которым завершается строка. Если нет, то функция reverse() вызывает саму себя с указателем на следующий символ в строке. Этот "закручивающийся" процесс повторяется до тех пор, пока той же функции не будет передан указатель на нуль. Когда, наконец, обнаружится символ конца строки, пойдет процесс "раскручивания", т.е. вызванные ранее функции начнут возвращать значения, и каждый возврат будет сопровождаться "довыполнением" метода, т.е. отображением символа s. В результате исходная строка посимвольно отобразится в обратном порядке.
Создание рекурсивных функций часто вызывает трудности у начинающих программистов. Но с приходом опыта использование рекурсии становится для многих обычной практикой.