Въведение в рекурсивната функция в Java
Рекурсивна функция е тази, която се обажда един или много пъти. Рекурсивна функция се използва в ситуации, когато е необходимо да се извършват един и същ набор от операции отново и отново, докато се постигне резултатът. Той изпълнява няколко итерации, а постановката на проблема продължава да става по-проста с всяка итерация.
Винаги трябва да се посочва базов лимит, докато пишете рекурсивна функция, в противен случай това води до грешка в преливането на стека. Стека е област от паметта, запазена за поддържане на извиквания на метод. Грешката е, защото функцията започва да се изпълнява непрекъснато, тъй като няма да може да намери ограничаващото условие и следователно окончателно изчерпва разпределената памет. За да се предотврати препълването на стека, ние дефинираме определени базови условия с помощта на изрази „if… else“ (или всякакви други условни оператори), което кара рекурсионната функция да спре веднага след приключване на изискваното изчисление.
Видове рекурсия в Java
Има два типа рекурсия в Java. Те са:
1. Пряка рекурсия
Синтаксис:
Тук function1 се обажда непрекъснато, следователно е рекурсивна функция.
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-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 обажда функция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.
- Накрая завършваме, като преместваме диск1 към пръчка 3, завършвайки необходимото решение.
Същият този принцип се прилага за "n" броя дискове чрез преместване (n-1) на диска от прът 1 на 2 и следване на подобни стъпки, както по-горе.
Предимства на рекурсия в Java
- Кодът е лесен за писане и поддържане.
- Най-добрият метод за намиране на резултатите, когато се изисква голям брой повторения.
Недостатъци на рекурсия в Java
- Рекурсивните функции използват повече памет. Това е така, защото всеки път се извиква рекурсивна функция; разпределението на паметта се извършва наскоро за променливите в стека. И съответното разпределение на паметта се освобождава веднага след връщането на променливите стойности.
- Този процес на разпределение на паметта отнема повече време, поради което изпълнението обикновено е бавно.
заключение
Рекурсивните функции са сравнително по-прости за кодиране, но също така не са толкова ефективни в сравнение с другите съществуващи методи. Следователно те се използват главно в случаите, когато времето за развитие е по-малко и също така, когато в проблема може да се наблюдава значителен модел.
Препоръчителни статии
Това е ръководство за рекурсия в Java. Тук обсъждаме видовете рекурсия в Java заедно с различните нейни примери с предимствата и недостатъците. Можете също да разгледате следните статии, за да научите повече-
- JScrollPane на Java
- Математически функции в Java
- Математически функции в Java
- Конструктор в Java
- Рекурсивна функция в Python
- Факторна програма в JavaScript