Рекурсия. Примеры решения задач. Преимущества и недостатки рекурсии

Содержание

Поиск на других ресурсах:

1. Что такое рекурсия? Что называется рекурсией?

Любая функция (метод) в своем теле может вызывать сама себя. Рекурсия – это такой способ определения функции, при котором результат возврата из функции для данного значения аргумента определяется на основе результата возврата из той же функции для предыдущего (меньшего или большего) значения аргумента.

Если функция (метод) вызывает сам себя, то такой вызов называется рекурсивным вызовом функции. При каждом рекурсивном вызове запоминаются предыдущие значения внутренних локальных переменных и полученных параметров функции. Чтобы следующий шаг рекурсивного вызова отличался от предыдущего, значение как-минимум одного из параметров функции должно быть изменено. Остановка процесса рекурсивных вызовов функции происходит, когда изменяемый параметр достиг некоторого конечного значения, например, обработан последний элемент в массиве.

⇑

2. Объяснения к реализации задач на рекурсию. Как правильно организовать рекурсивный вызов функции?

Рекурсивное обращение к функции может быть осуществлено, если алгоритм определен рекурсивно.

Чтобы циклический процесс преобразовать в рекурсивный, нужно уметь определить (выделить) три важных момента:

условие прекращения последовательности рекурсивных вызовов функции. Например, если счетчик или итератор с именем k изменяется от 1 до 10 в возрастающем порядке, то условие прекращения есть достижение значения k=10. Условие прекращения указывается в операторе return;
формулу следующего элемента или итератора, который используется в рекурсивном процессе. Эта формула указывается в операторе return;
список параметров, которые передаются в рекурсивную функцию. Один из параметров обязательно есть итератор (счетчик) изменяющий свое значение. Другие параметры являются дополнительными, например, ссылка на массив, над которым осуществляется обработка.

⇑

3. Поиск суммы элементов массива. Пример

По подобному примеру можно создавать собственные рекурсивные функции, которые определяют любые суммы элементов любых массивов.

Задача. Задан массив чисел A. Разработать рекурсивную функцию, которая находит сумму элементов массива:

S = A[0] + A[1] + … + A[n],

где n – количество элементов массива. Программный код функции следующий:

// сумма элементов массива
int Sum(int i, int A[], int n)
{
    if (i==n-1)
        return A[i];
    else
        return A[i]+Sum(i+1,A,n);
}

Как видно из примера, в рекурсивную функцию Sum() передается 3 параметра:

текущее значение итератора i;
массив A;
количество элементов массива n.

Выход из функции осуществляется, если будет обработан последний элемент массива. Условие прекращения рекурсивного процесса имеет вид:

if (i==n-1)
    return A[i];

Для суммирования текущего значения A[i] со следующими указывается строка:

return A[i]+Sum(i+1,A,n);

где рекурсивный вызов Sum(i+1, A, n) означает следующее значение массива A. Параметр i+1 указывает, что на следующем уровне вызова рекурсивной функции будет взят следующий после данного элемент массива.

Использование функции Sum() в другом программном коде может быть, например, таким:

int A[] = { 5, 7, 2, -1 };
int n = 4;
int sum;
sum = Sum(0,A,n); // sum = 13

⇑

4. Пример подсчета количества вхождений заданного символа в строке

В данном примере реализована рекурсивная функция Count(), которая определяет количество вхождений заданного символа c в строке s. Функция получает 3 параметра:

символ c, который нужно сравнить с каждым символом строки s;
строка s;
дополнительная переменная i, которая есть счетчиком рекурсивного цикла.

Реализация функции Count() следующая:

// подсчет символа c в строке символов s
int Count(char c, string s, int i)
{
    if (i==s.length()) // условие окончания рекурсивного процесса - вся строка пройдена
        return 0;
    else
    {
        if (c == s[i]) // если символ найден
            return Count(c,s,i+1)+1; // увеличить количество найденных символов на 1
        else
            return Count(c,s,i+1); // иначе, перейти к обработке следующего символа
    }
}

⇑

5. Пример нахождения факториала числа – n!

Вычисление факториала числа методом рекурсии есть почти в каждом учебнике. Факториал числа вычисляется по формуле

f = 1 · 2 · … · (n-1) · n

где n>=1.

Рекурсивный вызов можно организовать двумя способами:

в порядке возрастания 1, 2, …, n;
в порядке убывания n, n-1, …, 2, 1.

В данном примере разработаны две функции, которые находят факториал обоими способами. Программный код функций следующий:

// вычисление факториала - способ 1
int Fact1(int n, int i)
{
    if (i==n)
        return n; // условие завершения рекурсивного процесса
    else
        return i*Fact1(n, i+1); // переход к следующему числу i+1
}

// вычисление факториала - способ 2
int Fact2(int n)
{
    if (n==1)
        return 1; // условие завершения рекурсивного процесса
    else
        return n*Fact2(n-1); // переход к предыдущему числу n-1
}

В первую функцию Fact1() передаются 2 параметра. Первый параметр определяет максимально возможное значение n, которое может быть умножено. Второй параметр определяет текущее значение i которое умножается.

Во второй функции Fact2() передается 1 параметр – максимально возможное значение n, принимающее участие в рекурсивном умножении. Второго параметра здесь не нужно, поскольку условие прекращения рекурсивного процесса есть известно и равно 1. В функции Fact2() рекурсивный процесс завершается при n=1.

Использование функций в другом программном коде может быть следующим:

int f;

// использование функции Fact1()
f = Fact1(5,1); // f = 5! = 120
f = Fact1(7,1); // f = 7! = 5040
f = Fact1(2,1); // f = 2! = 2

// использование функции Fact2()
f = Fact2(5); // f = 5! = 120
f = Fact2(8); // f = 8! = 40320

⇑

6. Программа нахождения наибольшего общего делителя (алгоритм Евклида). Пример

В примере определяется наибольший общий делитель по формуле Евклида:

Программный код функции следующий:

// наибольший общий делитель по алгоритму Евклида
int MaxDiv(int n, int m)
{
    if (n==m)
        return n;
    else
    if (n>m)
        return MaxDiv(n-m, m);
    else
        return MaxDiv(n, m-n);
}

Использование функции MaxDiv() может быть следующим:

int md;
md = MaxDiv(8, 3); // md = 1
md = MaxDiv(24, 96); // md = 24
md = MaxDiv(9, 15); // md = 3

⇑

7. Подсчет количества элементов массива, больших заданного числа. Пример

Демонстрируется метод Count(), возвращающий количество элементов, больших заданного числа num. В метод передается 4 параметра:

число num, которое нужно сравнивать с каждым элементом массива;
массив чисел A[ ];
количество элементов массива n;
текущее значение счетчика в массиве.

// подсчет количества элементов массива, больших заданного числа
int Count(double num, double A[], int n, int i)
{
    if (i==n)
        return 0; // условие окончания рекурсивного процесса
    else
    {
        if (num<A[i])
            return Count(num, A, n, i+1) + 1; // добавить 1 к результату, и перейти далее
        else
            return Count(num, A, n, i+1); // перейти к следующему элементу массива
    }
}

Использование метода Count() в другом методе

double A[] = { 2.8, 3.5, 1.9, 2.2, 3.6 };
int k;
k = Count(2.3, A, 5, 0); // k = 3
k = Count(0.9, A, 5, 0); // k = 5

⇑

8. Преимущества использования рекурсии в программах. Пример

Рекурсию часто сравнивают с итерацией. Организация циклического процесса с помощью рекурсии имеет свои преимущества и недостатки.

Можно выделить следующие взаимосвязанные преимущества рекурсии:

естественность (натуральность) представления сложных, на первый взгляд, алгоритмов;
рекурсивный алгоритм более читабелен в сравнении с итерационным;
для многих распространенных задач рекурсию более легко реализовать чем итерацию. Рекурсия хорошо подходит для реализации алгоритмов обхода списков, деревьев, анализаторов выражений, комбинаторных задач и т.д.

Недостатки рекурсии состоят в следующем:

по сравнению с итерацией многоразовый вызов рекурсивной функции требует больше времени. Это связано с тем, что при вызове рекурсивного метода его параметры копируются в стек. При завершении вызова рекурсивной функции предыдущие значения параметров вытягиваются из стека, что приводит к лишним операциям. Итерационный алгоритм для той же задачи работает быстрее;
если рекурсивная функция содержит большие объемы локальных внутренних переменных и большое количество параметров, то использование рекурсии не является эффективным. Это связано с тем, что для каждого рекурсивного вызова нужно делать копии этих переменных и параметров. При большом количестве рекурсивных вызовов это приведет к чрезмерному использованию памяти.

⇑

Связанные темы

Примеры решения задач на рекурсию

⇑

BestProg

C++. Рекурсия. Примеры решения задач. Преимущества и недостатки рекурсии