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

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

Содержание

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

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

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

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

⇑

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

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

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

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

⇑

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

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

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

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

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

// рекурсия - сумма элементов массива
static int Sum(int i, int[] A) {
    if (i==(A.length-1))
        return A[i];
    return A[i] + Sum(i+1,A);
}

В вышеприведенном коде функция получает два параметра. Первый параметр i есть значением текущего индекса, который изменяет свое значение при каждом рекурсивном вызове. Второй параметр A – массив, элементы которого суммируются.

Последний элемент массива имеет индекс A.length-1. Достижение функцией последнего элемента массива есть выходом из нее. Поэтому, в тексте функции Sum() указывается условие прекращения рекурсивного процесса:

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

В языке Java массив есть экземпляром (объектом) класса, поэтому количество элементов в массиве определяется свойством length. Это есть удобным, поскольку не нужно передавать размерность массива в виде параметра (в отличие от некоторых других языков программирования).

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

// A[i] - текущее значение, Sum(i+1,A) – следующее значение в массиве
return A[i] + Sum(i+1,A);

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

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

int[] A = { 3, 12, 10, 11 };
int sum;
sum = Sum(0,A); // sum = 36

⇑

4. Вычисление факториала числа – n!. Пример

В примере разработана рекурсивная функция, которая находит факториал заданного числа n

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

где n>=1.

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

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

В данной функции происходит рекурсивный вызов функции Fact() с параметром n, который изменяется от n до 1 в порядке убывания. Рекурсивный процесс завершается при n = 1.

При возврате на уровень выше возвращается текущее значение n и результат вычислений при следующих рекурсивных вызовах:

return n*Fact(n-1);

Использование функции в другом программном коде:

int fact;
fact = Fact(7); // fact = 5040

⇑

5. Программа нахождения наибольшего общего делителя по алгоритму Евклида. Пример

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

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

// НОД - Алгоритм Евклида
int MaxDivisor(int n, int m) {
    if (n==m) return n;
    else
        if (n>m) return MaxDivisor(n-m, m);
        else
            return MaxDivisor(n, m-n); // n<m
}

Использование функции MaxDivisor

int md;
md = MaxDivisor(28,20); // md = 4

⇑

6. Вычислить n-й член последовательности чисел Фибоначчи. Пример

Последовательность чисел Фибоначчи имеет вид:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

В последовательности чисел Фибоначчи каждое следующее число n определяется как сумма двух предшествующих чисел: (n-1) + (n-2). Поэтому, в формуле рекурсивного процесса может быть вызов суммы двух функций а не одной. Прекращение рекурсивного процесса достигается, если значение n=0.

Ниже приведен текст функции GetNFibonacci()

// Определение n-го числа Фибоначчи
static int GetNFibonacci(int n) {
    if (n>1)
        return GetNFibonacci(n-2)+GetNFibonacci(n-1); // формула Фибоначчи
    else
        if (n==1)
            return 1;
        else
            return 0; // если n==0
}

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

int n;
n = GetNFibonacci(10); // n = 55

⇑

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

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

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

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

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

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

⇑

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

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

⇑

BestProg