Введение в рекурсивную функцию в 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
- Код легко написать и поддерживать.
- Лучший способ найти результаты, где требуется большое количество итераций.
Недостатки рекурсии в Java
- Рекурсивные функции используют больше памяти. Это потому, что каждый раз вызывается рекурсивная функция; выделение памяти делается заново для переменных в стеке. И соответствующее выделение памяти освобождается, как только возвращаются значения переменных.
- Этот процесс выделения памяти занимает больше времени, поэтому выполнение обычно медленное.
Вывод
Рекурсивные функции относительно проще в коде, но они также не так эффективны по сравнению с другими существующими методами. Следовательно, они в основном используются в тех случаях, когда время, отводимое на разработку, меньше, а также в тех случаях, когда в проблеме можно наблюдать значительный характер.
Рекомендуемые статьи
Это руководство по рекурсии на Java. Здесь мы обсуждаем типы рекурсии в Java вместе с различными примерами с преимуществами и недостатками. Вы также можете посмотреть следующие статьи, чтобы узнать больше
- JScrollPane в Java
- Математические функции в Java
- Математические функции в Java
- Конструктор в Java
- Рекурсивная функция в Python
- Факториал Программа в JavaScript