6.2. Понятие рекурсии
В то же время повторение последовательности действий можно осуществить и другим методом, основанным на принципе возможности явного включения в конструкции языка программирования конструкции того же вида. В частности, в языке программирования C++ всякая функция может вызывать сама себя. Такой вызов называется рекурсией. Функция, вызывающая саму себя, называется рекурсивной.
Вообще алгоритм решения задачи называется рекурсивным, если он выражается в терминах решения более простой версии той же задачи и, кроме того, в нем предусмотрено решение самого простого варианта задачи.
При рекурсивном вызове функций в С++ используется стековая организация хранения локальных параметров.
Стек является простейшей динамической структурой организации данных. Добавление элементов в стек и выборка из него выполняются из одного конца, называемого вершиной стека. Говорят, что стек реализует принцип обслуживания LIFO (last in — first out, последним пришел - первым ушел (обслужен)).
Стеки широко применяются в системном программном обеспечении, компиляторах, в различных рекурсивных алгоритмах.
Различия между итерацией и рекурсией:
итерации необходим цикл и вспомогательные величины, в то время как рекурсия обходится без вспомогательных величин и обычно проще для понимания, короче и нагляднее итерации;
итерация требует меньше места в оперативной памяти и меньших затрат машинного времени, чем рекурсия, которой необходимы затраты на управление стеком;
при реализации рекурсии велика вероятность переполнения стека.
Поэтому при выборе способа описания функции следует вначале решить, чему отдать предпочтение – эффективности программы или ее компактности. Однако следует избегать рекурсий там, где есть очевидное итерационное решение. Вместе с тем существует много хороших примеров применения рекурсии (построение графических образов разнообразных узоров, работа с двоичными деревьями).
При рекурсивном описании функции последняя всегда должна содержать, по крайней мере, одну альтернативную нерекурсивную ветвь алгоритма с условием окончания вычислений, заканчивающуюся оператором возврата результата.
Различают две формы рекурсивных подпрограмм:
- прямая рекурсия;
- косвенная рекурсия.
В первом случае функция содержит вызов этой же функции.
Косвенная рекурсия возникает в том случае, когда две или более функций вызывают друг друга. В случае двух функций: некоторая функция обращается к другой функции, а та в свою очередь вызывает первоначальную функцию. Для предотвращения зацикливания одна или обе функции должны проверять условие завершения.
Пример: Составить рекурсивную функцию, вычисляющую факториал числа n по формуле (учесть, что 0! = 1):
long fact (long n)
{
if (n==0 || n == 1) return 1;
return (n*fact(n-l));
}
То же самое можно записать короче:
long fact (long n)
{
return (n > 1) ? n*fact(n-l) : 1;
}
Пример: Распечатать последовательность, состоящую из n букв А и n букв В.
void abn (int n){
cout<<”A”;
if (n > 1) abn(n-l);
cout<<”B”;
return
}