Рекурсия в С++ - Урок 11
Рекурсия это повторение элемента, подобного самому себе.
Рассмотрим на примере вычисления факториала.
Факториал - произведение чисел от 1 до n, включая n.
| 1 , n = 0;
n = |
| n * (n - 1), n > 0;
Пример:
6! = 1 * 1 * 2 * 3 * 4 * 5 * 6 = 720;
Напишем итеративный алгоритм для вычисления факториала:
Код:
int factorial_iterative (int n)
{
if (n == 0) // Если 0!
return 1; // то факториал = 1, возвращаем ее
for (int i = n-1; i > 0; --i) // Декрименирующий цикл от (n - 1) до 0, не включая ноль
n *= i; // Производим умножение n и (n-1) членов последовательности
return n; // Возвращаем значение факториала
}
Функция целочисленного типа. В качестве входного аргумента принимается целое число, возвращается значение факториала.
Вычисление факториала идет с декриминацией множителя: 6! = 6 * 5 * 4 * 3 * 2 * 1;
Данную функцию можно написать рекурсивно заменив цикл на рекурсию:
Код:
int factorial_recursive (int n)
{
if (n == 0) // Условие выхода: если n равно 0
return 1;
return n * factorial_recursive (n-1); // Возвращаем значение факториала
}
Рекурсивная функция вызывает сама себя, пока условие выхода из нее не будет истинным.
В данном случае, функция в 5-ой строке будет вызывать сама себя с декрименацией аргумента, пока последний не станет нулем.
Рассмотрим работу алгоритма на примере 6!:
Код:
factorial_recursive (6):
{
if (6 == 0)
return 1;
return 6 * factorial_recursive (6-1)
{
if (5 == 0)
return 1;
return 5 * factorial_recursive (5-1)
{
if (4 == 0)
return 1;
return 4 * factorial_recursive (4-1)
{
if (3 == 0)
return 1;
return 3 * factorial_recursive (3-1)
{
if (2 == 0)
return 1;
return 2 * factorial_recursive (2-1)
{
if (1 == 0)
return 1;
return 1 * factorial_recursive (1-1)
{
if (0 == 0)
return 1; // выход
}
}
}
}
}
}
}
При написании рекурсивных функций сначала пишем условие выхода, а потом уже основной алгоритм.
Любой рекурсивный алгоритм можно реализовать итеративно.
Глубина рекурсии - количество вложеных вызовов самой себя в глубину. В нашем примере глубина рекурсии равна 5.
Рекурсивные алгоритмы короче, красивее, удобнее своих итерационных аналогов. Рекурсия не дает выиграша вы быстродействии
и даже дает небольшой проигрыш в использовании памяти. Для огромных объемов данных все же применяют итеративные алгоритмы.
Особо удачно использование рекурсии и рекурсивно-ориентироваными структурам, к примеру - деревья. Также удачно рекурсия
ложится на быструю сортировку методом Ч.Хоара (о ней будет статья в цикле "сортировки").
Код:
#include <iostream>
using namespace std;
long long int factorial_recursive (long long int n)
{
if (n == 0)
return 1;
return n * factorial_recursive (n-1);
}
long long int factorial_iterative (long long int n)
{
if (n == 0)
return 1;
for (long long int i = n-1; i > 0; --i)
n *= i;
return n;
}
int main ()
{
long long int x;
cout<<"Enter x: ";
cin>>x;
if (x < 0) {
cout<<endl<<"Error! x must be non-negative!";
return 0;
}
if (x > 16) {
cout<<endl<<"Error! n overflow!";
return 0;
cout<<endl<<"recursive factorial "<<x<<" = "<<factorial_recursive (x);
cout<<endl<<"iterative factorial "<<x<<" = "<<factorial_iterative (x);
return 0;
}
Примечание: В данном варианте максимальное значение x = 16, в противном случае - переполнение переменной n. Если изменить тип на long int предел x = 19, при long long int - 25. Дальнейшее увеличение верхней границы x требует использования длинной арифметики.
Компилятор: g++