Вступ до рекурсивної функції на 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
)
Приклад
Фактор числа є прикладом прямої рекурсії. Основний принцип рекурсії - вирішити складну задачу шляхом розщеплення на більш дрібні. Наприклад, у випадку факториалу числа ми обчислюємо факторіал «я», якщо знаємо його факторіал «я-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 (). Тут функція1 викликає функцію2 та функцію2 виклику функцію1.
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);
)
)
)
Вихід:
Тут змінна “count” відображає кількість використаних дисків. Функція «вежа» - це рекурсивна функція, яка використовується для переміщення дисків зі стрижня 1 на стрижень 3. Просте рішення цієї проблеми можна надати, розглядаючи спочатку 2 диски.
- Спочатку почнемо з переміщення диска1 від стрижня 1 до стрижня 2.
- Далі переміщуємо disk2 на стрижень 3.
- Нарешті, ми закінчимо переміщенням disc1 до стрижня 3, доповнивши потрібне рішення.
Цей самий принцип застосовується і для “n” кількості дисків, переміщаючи (n-1) диск із стрижня 1 на 2 та виконуючи подібні дії, як описано вище.
Переваги рекурсії на Java
- Код легко записати та підтримувати.
- Найкращий спосіб знайти результати, коли потрібна велика кількість ітерацій.
Недоліки рекурсії на Java
- Рекурсивні функції використовують більше пам'яті. Це тому, що кожного разу викликається рекурсивна функція; розподіл пам'яті здійснюється заново для змінних на стеку. І відповідний розподіл пам'яті звільняється, як тільки повертаються змінні значення.
- Цей процес розподілу пам’яті займає більше часу, тому виконання, як правило, повільне.
Висновок
Рекурсивні функції відносно простіші для кодування, але вони також не настільки ефективні в порівнянні з іншими існуючими методами. Отже, вони в основному використовуються у тих випадках, коли часу на розвиток менше, а також, коли в проблемі може спостерігатися значна картина.
Рекомендовані статті
Це посібник з рекурсії на Java. Тут ми обговорюємо типи рекурсії на Java разом з її різними прикладами з перевагами та недоліками. Ви також можете переглянути наступні статті, щоб дізнатися більше -
- JScrollPane на Java
- Математичні функції на Java
- Математичні функції на Java
- Конструктор на Java
- Рекурсивна функція в Python
- Факторна програма в JavaScript