Java рекурсия недостатки и преимущества

Рекурсия на Яве — Различные типы и примеры рекурсии в Java

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

При написании рекурсивной функции всегда необходимо указывать базовый предел, иначе это приведет к ошибке переполнения стека. Стек — это область памяти, зарезервированная для поддержки вызовов методов. Ошибка в том, что функция начинает выполняться непрерывно, так как не сможет найти условие ограничения и, следовательно, в конечном итоге исчерпает выделенную память. Поэтому, чтобы предотвратить переполнение стека, мы определяем определенные базовые условия с помощью операторов «if… else» (или любых других условных операторов), которые заставляют функцию рекурсии останавливаться, как только требуемые вычисления завершаются.

Типы рекурсии в Java

В Java есть 2 типа рекурсии. Они есть:

1. Прямая рекурсия

Здесь функция 1 вызывает себя непрерывно, следовательно, является рекурсивной функцией.

public static void main(String() args)(
//few lines of code
function();
//few lines of code
)
function() (
//few lines of code
function();
//few lines of code
)

Факториал числа является примером прямой рекурсии. Основной принцип рекурсии — решить сложную проблему, разбив ее на более мелкие. Например, в случае факториала числа мы вычисляем факториал «i», если мы знаем его факториал «i-1».

public class Factorial (
static int fact(int i)(
if (i == 1)
return 1;
else
return(i * fact(i-1));
)
public static void main(String() args) (
System.out.println(«The factorial of given number 6 is: «+fact(6));
)
)

2. Косвенная / Взаимная рекурсия

Функция 1, которая вызывает другую функцию 2, которая, в свою очередь, вызывает функцию 1 прямо или косвенно, называется косвенной рекурсивной функцией.

Рассмотрим 2 функции, называемые function1 () и function2 (). Здесь function1 вызывает function2, а function2 вызывает function1.

function1()(
//few lines of code
function2();
//few lines of code
)
function2()(
//few lines of code
function1();
//few lines of code
)

Чтобы показать косвенную рекурсию, мы берем следующую программу, используемую, чтобы узнать, является ли данное число четным или нечетным из заданного ввода.

import java.util.Scanner;
public class IndirectRecursion (
public static boolean oddNum(int i) (
if (i<0) throw new IllegalArgumentException("Number is negative");
if(i == 0)(
return false;
) else (
return evenNum(i-1);
)
)
public static boolean evenNum(int i) (
if (i<0) throw new IllegalArgumentException("Number is negative");
if(i == 0)(
return true;
) else (
return oddNum(i-1);
)
)
public static void main(String() args) (
Scanner inputNum = new Scanner(System.in);
System.out.print(«Give a number: «);
int n = inputNum.nextInt();
if (evenNum(n)) System.out.println(n + » is even»);
else System.out.println(n + » is odd»);
inputNum.close();
)
)

Примеры рекурсии в Java

Вот еще несколько примеров решения проблем с помощью метода рекурсии.

Пример № 1 — последовательность Фибоначчи

Говорят, что набор из «n» чисел находится в последовательности Фибоначчи, если число 3 = число 1 + число 2, то есть каждое число является суммой двух предыдущих чисел. Следовательно, последовательность всегда начинается с первых двух цифр, таких как 0 и 1. Третья цифра представляет собой сумму 0 и 1, что приводит к 1, четвертое число — это сложение 1 и 1, что приводит к 2, и последовательность продолжается.

Проверьте следующий код в Java для генерации последовательности Фибоначчи:

public class FibonacciSeries(
static int num1=0, num2=1, num3=0;
static void fibonacci(int n)(
if(n>0)(
num3 = num1 + num2;
num1 = num2;
num2 = num3;
System.out.print(» «+num3);
fibonacci(n-1);
)
)
public static void main(String args())(
int n=10;
System.out.print(num1+» «+num2);//printing constant first two digits 0 and 1
fibonacci(n-2);//Since first two numbers are already done
)
)

Здесь первые два числа инициализируются 0 и 1 и печатаются. Переменные «num1», «num2» и «num3» используются для генерации требуемой последовательности. Переменная «num3» получается путем добавления «num1» и «num2», а числа сдвигаются на одну позицию влево путем тасования, как показано в коде. Функция «Фибоначчи» вызывается здесь рекурсивно, и на каждой итерации значение «n» уменьшается на 1. Следовательно, рекурсия завершается, как только «n» достигает значения 0.

Пример № 2 — Ханойская башня

Это классическая математическая задача, которая состоит из 3 полюсов и «n» дисков разных размеров. Головоломка выглядит следующим образом:

В начале, первый полюс будет иметь диски, расположенные так, что самый большой диск из всех находится внизу, а самый маленький — в верхней части полюса. Задача состоит в том, чтобы переместить эти диски с первого полюса на третий, удерживая диски в том же положении, что и на первом. Ниже приведены несколько условий, которые следует учитывать при перемещении этих дисков:

1. За один раз должен быть перемещен только один диск.
2. При этом размещение большего диска поверх меньшего не допускается.
3. Второй (средний) полюс может использоваться как посредник при переносе дисков с первого на второй полюс.

Ниже приведен код Java, который можно использовать для решения головоломки:

public class TowerOfHanoi (
public static void main(String() args) (
int count = 3;
tower(count, ‘A’, ‘B’, ‘C’);
)
public static void tower(int first, char disk1, char temp, char disk2) (
if (first == 1) (
System.out.println(«Disk 1 from » + disk1 + » to » + disk2);
) else (
tower(first — 1, disk1, disk2, temp);
System.out.println(«Disk » + first + » from » + disk1 + » to » + disk2);
tower(first — 1, temp, disk1, disk2);
)
)
)

Здесь переменная «количество» представляет количество дисков, которые будут использоваться. Функция «башня» — это рекурсивная функция, используемая для перемещения дисков от стержня 1 к стержню 3. Простое решение этой проблемы может быть обеспечено, если сначала рассмотреть 2 диска.

• Сначала мы начнем с перемещения диска 1 от стержня 1 к стержню 2.
• Далее мы перемещаем диск 2 в стержень 3.
• Наконец, мы заканчиваем, перемещая диск 1 к стержню 3, завершая требуемое решение.

Этот же принцип применяется для числа дисков «n» путем перемещения (n-1) диска от стержня 1 к 2 и выполнения действий, аналогичных описанным выше.

Преимущества рекурсии в Java

1. Код легко написать и поддерживать.
2. Лучший способ найти результаты, где требуется большое количество итераций.

Недостатки рекурсии в Java

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

Вывод

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

Рекомендуемые статьи

Это руководство по рекурсии на Java. Здесь мы обсуждаем типы рекурсии в Java вместе с различными примерами с преимуществами и недостатками. Вы также можете посмотреть следующие статьи, чтобы узнать больше

1. JScrollPane в Java
2. Математические функции в Java
3. Математические функции в Java
4. Конструктор в Java
5. Рекурсивная функция в Python
6. Факториал Программа в JavaScript

Источник

Рекурсия Java: рекурсивные методы (с примерами)

В этом руководстве вы узнаете о рекурсивной функции Java, ее преимуществах и недостатках.

В Java метод, который вызывает сам себя, известен как рекурсивный метод. И этот процесс известен как рекурсия.

В качестве примера физического мира можно поместить два параллельных зеркала, обращенных друг к другу. Любой объект между ними будет отражаться рекурсивно.

Как работает рекурсия?

Работа рекурсии Java

В приведенном выше примере мы вызвали recurse() метод изнутри main метода. (обычный вызов метода). И внутри метода recurse () мы снова вызываем тот же метод рекурсии. Это рекурсивный вызов.

Чтобы остановить рекурсивный вызов, нам нужно предоставить некоторые условия внутри метода. В противном случае метод будет вызываться бесконечно.

Следовательно, мы используем оператор if… else (или аналогичный подход) для завершения рекурсивного вызова внутри метода.

Пример: факториал числа с использованием рекурсии

class Factorial ( static int factorial( int n ) ( if (n != 0) // termination condition return n * factorial(n-1); // recursive call else return 1; ) public static void main(String() args) ( int number = 4, result; result = factorial(number); System.out.println(number + " factorial no"> 4 факториал = 24

В приведенном выше примере у нас есть метод с именем factorial() . factorial() Вызывается из main() метода. с числовой переменной, переданной в качестве аргумента.

Здесь обратите внимание на утверждение,

factorial() Метод вызывает себя. Изначально значение n внутри равно 4 factorial() . Во время следующего рекурсивного вызова factorial() методу передается 3 . Этот процесс продолжается до тех пор, пока n не станет равным 0.

Когда n равно 0, if оператор возвращает false, следовательно, возвращается 1. Наконец, накопленный результат передается в main() метод.

Работа факторной программы

Изображение ниже даст вам лучшее представление о том, как выполняется факториальная программа с использованием рекурсии.

Факториальная программа с использованием рекурсии

Преимущества и недостатки рекурсии

Когда выполняется рекурсивный вызов, в стеке выделяются новые места для хранения переменных. Когда каждый рекурсивный вызов возвращается, старые переменные и параметры удаляются из стека. Следовательно, рекурсия обычно использует больше памяти и обычно выполняется медленно.

С другой стороны, рекурсивное решение намного проще и требует меньше времени на написание, отладку и поддержку.

Рекомендуемая литература: каковы преимущества и недостатки рекурсии?

Источник