Как видим, в main() вызывается функция A(), которая вызывает B(), а та в свою очередь вызывает снова A(). Понятно, что цепочка подпрограмм между вызовами функции A() могла быть не из одной функции B(), а из большего количества разных функции.
Рекурсия — это такая организация выполнения работы функции, при которой данная функция вызывает сама себя.
Рекурсия может быть прямой и косвенной.
В случае прямой рекурсии вызов функцией самой себя делается непосредственно в этой же функции:
void f() {
............
f();
............
}
Косвенная рекурсия создаётся за счёт вызова данной функции из какой-либо другой функции, которая сама вызывалась из данной функции. Например, схема может быть такой:
Как
видим, в main()
вызывается функция A(),
которая вызывает B(),
а та в свою очередь вызывает снова A().
Понятно, что цепочка подпрограмм между вызовами
функции A()
могла быть не из одной функции B(),
а из большего количества разных функции.
Стандартом языка C++ рекурсивно может вызываться любая функция, кроме main(), а по стандарту языка C рекурсивно можно вызвать даже main()!
Практика показывает, что функцию main() в ряде систем разработки (CodeBlocks, например) можно вызвать на любом языке (и на C, и на C++):
1)Прямая рекурсия функции main() на языке C++:
#include <iostream>
using namespace std;
int main()
{
cout << "Hello world!" << endl;
main();
return 0;
}
2)Косвенная рекурсия функции main() на языке C++:
#include <iostream>
using namespace std;
void f();
int main()
{
cout << "Hello world!" << endl;
f();
return 0;
}
void f()
{
main();
}
В обоих примерах на экране монитора достаточно долго будет выводится радостный текст
Hello world!
а затем произойдёт аварийное завершение программы из-за переполнения стека.
Не зависимо от того, какой вид рекурсии используется (прямая или косвенная), в рекурсивной функции обязательно должна выполняться проверка какого-либо условия, в зависимости от которого осуществлялся бы выход из рекурсивной функции. Причём, необходимо гарантировать, что это условие обязательно будет выполнено через конечное количество рекурсивных вызовов, и функция в конце концов закончит работу. Иначе — аварийное завершение, смотри примеры выше.
Последовательный вызов функцией самой себя называют рекурсивным спуском, последовательный выход из многократного вызова — рекурсивным подъёмом.
При каждом рекурсивном вызове функции заново выделяется память под локальные переменные.
Пример 1. Вычислить факториал n!.
Задача проста, но для понимания рекурсии вполне пригодна. По определению, n! — это произведение первых n натуральных чисел.
Если известен, к примеру, 4!, то 5! вычисляем по формуле: 5!=5·4!.
В свою очередь
4!=4·3!
3!=3·2!
2!=2·1!
а 1!=1
Воспользуемся этим фактом и получим следующую рекурсивную функцию (приведём весь текст программы):
#include <iostream>
using namespace std;
int factorial(int n);
int main()
{
int n = 5;
int y = factorial(n);
cout << n<<"! =" << y << endl;
return 0;
}
int factorial(int n)
{
int t;
if(n <=1)
t = 1;
else
t = n * factorial(n - 1);
return t;
}
При рекурсивном спуске n последовательно уменьшается на 1. Когда n=1, начинается рекурсивный подъём. Именно на подъёме начинают последовательно вычисляться 2!, 3!, 4!, …, n!.
Условие
if(n <=1)
и уменьшение n при обращении к factorial() в операторе
t = n * factorial(n - 1);
гарантируют защиту от рекурсивного зацикливания.
Пример 2. Для данного n вычислить число Фибоначчи, используя зависимость
F(0)=F(1)=1, F(N)=F(N-1)+F(N-2) при n>1.
Возможный вариант реализации:
#include <iostream>
using namespace std;
int Fib(int n);
int main()
{
int n = 5;
int y = Fib(n);
cout << "Fib(" << n << ")=" << y<< endl;
return 0;
}
int Fib(int n)
{
if(n < 1)
return 1;
else
return Fib(n-1) + Fib(n-2);
}
Если посмотреть рисунок ниже со схемой рекурсивного вызова функций Fib(), то нетрудно заметить, что мы многократно вычисляем одно и то же, например, Fib(2) вызывается трижды. Понятно, что такая расточительность будет заметно снижать скорость выполнения программы.
Пример
3. Вычислить функцию Аккермана для заданных неотрицательных целых
чисел n
и m
по формулам:
A(n,m) = m+1, если n=0;
A(n,m) = A(n-1, 1), если n>0, m=0;
A(n,m) = A(n-1, A(n,m-1)), если n>0, m>0.
Реализация получается предельно проста, а скорость работы — предельно долгой даже при небольших n и m. К тому же здесь вероятно переполнение стека из-за катастрофически огромного количества рекурсивных вызовов. Попробуйте вручную посмотреть схему вызова этой интереснейшей функции.
Возможный вариант реализации:
#include <iostream>
using namespace std;
int Ak(int n, int m);
int main()
{
int n=2, m=2, y;
y = Ak(n, m);
cout << "A(" <<n << "," << m << ")=" << y << endl;
return 0;
}
int Ak(int n, int m)
{
int a;
if(n == 0)
a = m + 1;
else if(n > 0 && m == 0)
a = Ak(n - 1, 1);
else
a = Ak(n - 1, Ak(n, m - 1));
return a;
}
Пример 4. Быстрая сортировка, изобретена в 60-х годах 20-го века. Варианты этой сортировки существуют для большинства современных языков программирования. В С++ она присутствует в STL (стандартная библиотека шаблонов).
Возможный вариант реализации:
#include <iostream>
using namespace std;
void QuickSort(int x[], int i1, int j1);
int M=0; // Количество вызовов функции QuickSort()
int NN=0;// Число перестановок
const int n = 17;
int main()
{
int i;
int x[n]={12,14,6,-6,4,11,9,54,1,15,32,6,5,8,2,21,1};
cout << "Do Sort X:" << endl;
for(i = 0; i < n; i++)
cout << x[i] << " ";
cout << endl;
QuickSort(x, 0, n-1);
cout << "Posle Sort X:" << endl;
for(i = 0; i < n; i++)
cout << x[i] << " ";
cout << "\nM="<< M << " NN=" << NN<< endl;
return 0;
}
void QuickSort(int x[], int i1, int j1)
{
int c;
M++;
// Границы (левая и правая) сортируемого участка
cout << i1 << " "<< j1 << endl;
int i = i1, j = j1, b = (x[i1]+x[j1])/2;
do
{
while(x[i] < b && i < j1)
i++;
while(x[j] > b && j > i1)
j--;
if(i < j)
{
cout << "Swap: x[" << i <<"]=" << x[i] <<" and x[" << j << "]=" << x[j] << endl;
c = x[i];
x[i] = x[j];
x[j] = c;
i++;
j--;
NN++;
}
else
if(i == j)
{
i++;
j--;
}
} while (i <= j);
// Содержимое сортируемого массива после очередных перестановок для текущего вызова QuickSort
cout << "--- x:" << endl;
for(int ii = 0; ii < n; ii++)
cout << x[ii] << " ";
cout << endl;
if(i1 < j)
QuickSort(x, i1, j);
if(i < j1)
QuickSort(x, i, j1);
}
Здесь заведены вспомогательные переменные M и NN для оценки скорости работы метода. Также при каждом рекурсивном вызове выполняется вывод на экран монитора содержимое сортируемого массива и границы обрабатываемого при данном вызове участка. Сделано это с одной целью: дать возможность лучше понять механизм работы метода быстрой сортировки.
Какие выводы можно сделать из рассмотренных примеров? Рекурсия позволяет в ряде случаев создавать очень компактный код, особенно в том случае, когда при постановке задачи определение каких-либо понятий имеет явно рекурсивный вид (смотри функцию Аккермана). Но за малый размер исходного кода приходится расплачиваться снижением производительности.
|
|
|
|
