Увод у рекурзивне функције на Јави
Рекурзивна функција је она која себе позива један или више пута. Рекурзивна функција користи се у ситуацијама када се исти и поновни поступак морају изводити изнова и изнова док се резултат не постигне. Изводи неколико итерација и изјава проблема постаје поједностављена са сваком итерацијом.
Увек треба специфицирати основну границу док пишете рекурзивну функцију, а у супротном долази до грешке у преливању стакла. Корак је меморијско подручје резервирано за одржавање позива метода. Грешка је зато што се функција почиње извршавати у континуитету јер неће моћи пронаћи ограничавајући услов и на крају ће исцрпити додељену меморију. Да би се спречио пребацивање стака, дефинишемо одређене основне услове уз помоћ изјава „ако… друго“ (или било које друге условне изјаве) због чега се функција рекурзије зауставља чим завршено тражено рачунање.
Врсте рекурзије у Јави
Постоје две врсте рекурзије на Јави. Су:
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 функције које се зову фунцтион1 () и фунцтион2 (). Овде функција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();
)
)
Излаз:
Примери рекурзије у Јави
Ево још неколико примера за решавање проблема коришћењем методе рекурзије.
Пример # 1 - Фибонацијева секвенца
Каже се да је скуп „н“ бројева у Фибонаццијевом низу ако је број 3 = број1 + број2, тј. Сваки број је збир његових претходних два броја. Стога низ почиње увек са прве две цифре попут 0 и 1. Трећа цифра је збир 0 и 1 што резултира са 1, четврти број је сабирање 1 и 1 што резултира са 2, а низ наставља.
Погледајте следећи код у Јави да бисте генерисали Фибонаццијев низ:
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 и штампају. Променљиве „нум1“, „нум2“ и „нум3“ користе се за генерисање потребне секвенце. Променљива „нум3“ се добија додавањем „нум1“ и „нум2“, а бројеви се померају на једно лево померањем померања као што је приказано у коду. Овде се функција рекордно назива „Фибонацције“ и при свакој итерацији вредност „н“ се смањује за 1. Отуда рекурзија излази чим „н“ достигне вредност 0.
Пример бр. 2 - Ханојска кула
Ово је класичан математички проблем који има 3 пола и „н“ број дискова различите величине. Загонетка је следећа:
У почетку ће први дискови бити постављени тако да им је највећи диск на дну, а најмањи на врху стуба. Циљ је померање ових дискова са првог пола на трећи пол држећи дискове у истом положају као онај на првом. Ево неколико услова које морате имати на уму током померања ових дискова:
1. Истовремено треба преместити само један диск.
2. У току постављања већег диска на мањи није дозвољено.
3. Други (средњи) пол се може користити за посредовање током преноса дискова са првог на други пол.
Следи Јава код који се може користити за решавање слагалице:
Шифра:
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, комплетирање потребног решења.
Исти принцип примењује се за „н“ број дискова померањем (н-1) диска са штапа 1 на 2 и следањем сличних корака као горе.
Предности рекурзије у Јави
- Код се лако пише и одржава.
- Најбољи начин да се пронађу резултати тамо где је потребан велики број понављања.
Недостаци рекурзије у Јави
- Рекурзивне функције користе више меморије. То је зато што се сваки пут позива рекурзивна функција; распоређивање меморије врши се на ново за варијабле на снопу. И додељена меморија се ослобађа чим се врате променљиве вредности.
- Овај процес додељивања меморије одузима више времена, па је извршење обично споро.
Закључак
Рекурзивне функције су релативно једноставније за кодирање, али исто тако нису тако ефикасне у поређењу с другим постојећим методама. Због тога се они углавном користе у случајевима када је време за развој мање, а такође и када се у проблему може приметити значајан образац.
Препоручени чланци
Ово је водич за рекурзију на Јави. Овде смо расправљали о врстама рекурзије у Јави, заједно са њеним различитим примерима, са предностима и недостацима. Такође можете погледати следеће чланке да бисте сазнали више -
- ЈСцроллПане на Јави
- Матх функције у Јави
- Матх функције у Јави
- Конструктор на Јави
- Рекурзивна функција у Питхону
- Факторски програм у ЈаваСцрипт-у