Овој детален туторијал за рекурзија во Java објаснува што е рекурзија со примери, типови и сродни концепти. Исто така, опфаќа рекурзија против повторување:
Од нашите претходни упатства во Јава, го видовме итеративниот пристап каде што декларираме јамка и потоа поминуваме низ структурата на податоци на итеративен начин со преземање на еден елемент на време.
Го видовме и условниот тек каде повторно задржуваме една променлива за циклус и повторуваме дел од кодот додека променливата на циклусот не го исполни условот. Кога станува збор за повици на функции, го истраживме итеративниот пристап и за повиците на функции.
Во ова упатство, ќе разговараме за поинаков пристап кон програмирањето, односно за рекурзивниот пристап.
Што е рекурзија во Java?
Рекурзијата е процес со кој функцијата или методот се повикува себеси повторно и повторно. Оваа функција која се повикува постојано или повторно директно или индиректно се нарекува „рекурзивна функција“.
Ќе видиме различни примери за да ја разбереме рекурзијата. Сега да ја видиме синтаксата на рекурзијата.
Синтакса на рекурзија
Секој метод што имплементира рекурзија има два основни дела:
- Повик на метод кој може да се нарече себеси, т.е. рекурзивен
- Предуслов што ќе ја запре рекурзијата.
Забележете дека предусловот е неопходен за секој рекурзивен метод, бидејќи, ако не скрши горекурзија, тогаш таа ќе продолжи да работи бесконечно и ќе резултира со прелевање на стек.
Општата синтакса на рекурзијата е следна:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Имајте предвид дека предусловот е исто така наречен основна состојба. Ќе разговараме повеќе за основната состојба во следниот дел.
Разбирање на рекурзијата во Java
Во овој дел, ќе се обидеме да го разбереме процесот на рекурзија и да видиме како се одвива. Ќе научиме за основната состојба, преливот на стек и ќе видиме како може да се реши одреден проблем со рекурзија и други такви детали.
Основна состојба на рекурзија
Додека ја пишуваме рекурзивната програма, треба прво обезбедете го решението за основната кутија. Потоа го изразуваме поголемиот проблем во однос на помали задачи.
Како пример, можеме да земеме класичен проблем за пресметување на факторот на број. Со даден број n, мораме да најдеме фактор од n означен со n!
Сега да ја имплементираме програмата за да го пресметаме n факторот (n!) со помош на рекурзија.
public class Main{ static int fact(int n) { if (n == 1) // base condition return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } }Излез
Во оваа програма, можеме да видиме дека условот (n=1) е основната состојба и кога ќе се достигне оваа состојба, функцијата враќа 1 Другиот дел од функцијата е рекурзивниот повик. Но, секогаш кога се повикува рекурзивниот метод, n се намалува за 1.
Така можеме да заклучиме дека на крајот вредноста на n ќе стане 1 или помала од 1 и при оваточка, методот ќе ја врати вредноста 1. Оваа основна состојба ќе се достигне и функцијата ќе престане. Забележете дека вредноста на n може да биде која било се додека ја задоволува основната состојба.
Решавање проблеми со помош на рекурзија
Основната идеја зад користењето рекурзија е да се изрази поголемиот проблем во смисла на помали проблеми. Исто така, треба да додадеме еден или повеќе основни услови за да можеме да излеземе од рекурзија.
Ова веќе беше покажано во горниот факторски пример. Во оваа програма, го изразивме n факторот (n!) во однос на помали вредности и имавме основна состојба (n =1), така што кога n ќе достигне 1, можеме да го напуштиме рекурзивниот метод.
Грешка во прелевање на магацинот во рекурзија
Свесни сме дека кога ќе се повика кој било метод или функција, состојбата на функцијата се зачувува на оџакот и се враќа кога функцијата се враќа. Стакот се користи и за рекурзивниот метод.
Но, во случај на рекурзија, може да се појави проблем ако не ја дефинираме основната состојба или кога основната состојба некако не е достигната или извршена. Ако се случи оваа ситуација, тогаш може да дојде до прелевање на стекот.
Да го разгледаме долунаведениот пример за факторска нотација.
Овде дадовме погрешна основна состојба, n==100.
public class Main { static int fact(int n) { if (n == 100) // base condition resulting in stack overflow return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } }Значи, кога n > 100 методот ќе врати 1, но рекурзијата нема да запре. Вредноста на n ќе продолжи да се намалува на неодредено времене е друг услов да се запре. Ова ќе продолжи се додека стекот не се прелее.
Друг случај ќе биде кога вредноста на n 100. И во овој случај, методот никогаш нема да ја изврши основната состојба и да резултира со прелевање на стек.
Примери за рекурзија во Java
Во овој дел, ќе ги имплементираме следните примери користејќи рекурзија.
#1) Серии на Фибоначи користејќи рекурзија
Серијата Фибоначи е дадена со,
1,1,2,3,5,8,13,21, 34,55,…
Горната низа покажува дека тековниот елемент е збир од претходните два елементи. Исто така, првиот елемент во серијата Фибоначи е 1.
Значи, генерално, ако n е моменталниот број, тогаш тој е даден со збирот на (n-1) и (n-2). Бидејќи тековниот елемент е изразен во однос на претходните елементи, можеме да го изразиме овој проблем користејќи рекурзија.
Програмата за имплементација на серијата Фибоначи е дадена подолу:
public class Main { //method to calculate fibonacci series static int fibonacci(int n) { if (n = 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } public static void main(String[] args) { int number = 10; //print first 10 numbers of fibonacci series System.out.println ("Fibonacci Series: First 10 numbers:"); for (int i = 1; i = number; i++) { System.out.print(fibonacci(i) + " "); } } } Излез
#2) Проверете дали бројот е палиндром користејќи рекурзија
Палиндром е низа што е еднаква кога ние читај го од лево кон десно или од десно кон лево.
Дадејќи го бројот 121, гледаме дека кога го читаме од лево кон десно и од десно кон лево, тој е еднаков. Оттука, бројот 121 е палиндром.
Да земеме друг број, 1242. Кога го читаме од лево кон десно, тој е 1242, а кога се чита од десно кон лево, се чита како 2421. Така, ова не е палиндром.
Ниеимплементирајте ја програмата палиндром со превртување на цифрите на броевите и рекурзивно споредете го дадениот број со неговото обратно претставување.
Подолу програмата ја имплементира програмата за проверка на палиндромот.
import java.io.*; import java.util.*; public class Main { // check if num contains only one digit public static int oneDigit(int num) { if ((num >= 0) && (num 10)) return 1; else return 0; } //palindrome utility function public static int isPalindrome_util (int num, int revNum) throws Exception { // base condition; return if num=0 if (num == 0) { return revNum; } else { //call utility function recursively revNum = isPalindrome_util(num / 10, revNum); } // Check if first digit of num and revNum are equal if (num % 10 == revNum % 10) { // if yes, revNum will move with num return revNum / 10; } else { // exit throw new Exception(); } } //method to check if a given number is palindrome using palindrome utility function public static int isPalindrome(int num) throws Exception { if (num 0) num = (-num); int revNum = (num); return isPalindrome_util(num, revNum); } public static void main(String args[]) { int n = 1242; try { isPalindrome(n); System.out.println("Yes, the given number " + n + " is a palindrome."); } catch (Exception e) { System.out.println("No, the given number " + n + " is not a palindrome."); } n = 1221; try { isPalindrome(n); System.out.println("Yes, the given number " + n + " is a palindrome."); } catch (Exception e) { System.out.println("No, the given number " + n + " is not a palindrome."); } } }Излез
#3) Јава рекурзија на обратна низа
Дадена е низа „Здраво“, треба да ја превртиме така што резултантната низа е „olleH“.
Ова се прави со помош на рекурзија. Почнувајќи од последниот знак во низата, ние рекурзивно го печатиме секој знак додека не се исцрпат сите знаци во низата.
Програмата подолу користи рекурзија за да ја смени дадената низа.
class String_Reverse { //recursive method to reverse a given string void reverseString(String str) { //base condition; return if string is null or with 1 or less character if ((str==null)||(str.length() = 1)) System.out.println(str); else { //recursively print each character in the string from the end System.out.print(str.charAt(str.length()-1)); reverseString(str.substring(0,str.length()-1)); } } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("The given string: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("The reversed string: "); obj.reverseString(inputstr); } } Излез
#4) Јава рекурзија на бинарно пребарување
Алгоритам за бинарно пребарување е познат алгоритам за пребарување. Во овој алгоритам, со оглед на сортирана низа од n елементи, ја бараме оваа низа за дадениот клучен елемент. На почетокот, низата ја делиме на две половини со наоѓање на средниот елемент на низата.
Потоа, во зависност од тоа дали клучот во средината, го ограничуваме нашето пребарување во првата или втората половина од низата. На овој начин истиот процес се повторува додека не се најде локацијата на клучните елементи.
Ќе го имплементираме овој алгоритам користејќи рекурзија овде.
import java.util.*; class Binary_Search { // recursive binary search int binarySearch(int numArray[], int left, int right, int key) { if (right >= left) { //calculate mid of the array int mid = left + (right - left) / 2; // if the key is at mid, return mid if (numArray[mid] == key) return mid; // if key key) return binarySearch(numArray, left, mid - 1, key); // Else recursively search in the right subarray return binarySearch(numArray, mid + 1, right, key); } // no elements in the array, return -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //declare and print the array int numArray[] = { 4,6,12,16,22}; System.out.println("The given array : " + Arrays.toString(numArray)); int len = numArray.length; //length of the array int key = 16; //key to be searched int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Element " + key + " not present"); else System.out.println("Element " + key + " found at index " + result); } } Излез
#5) Најдете минимална вредност во низата користејќи рекурзија
Користејќи ја рекурзијата, можеме да ја најдеме и минималната вредност во низата.
0> НаЈава програмата за наоѓање на минималната вредност во низата е дадена подолу.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //return first element if only one element or minimum of the array elements return (n == 1) ? numArray[i] : Math.min(numArray[i], getMin(numArray,i + 1 , n - 1)); } public static void main(String[] args) { int numArray[] = { 7,32,64,2,10,23 }; System.out.println("Given Array : " + Arrays.toString(numArray)); int n = numArray.length; System.out.print("Minimum element of array: " + getMin(numArray, 0, n) + "\n"); } }Излез
Овие се некои од примерите на рекурзија. Освен овие примери, многу други проблеми во софтверот може да се имплементираат со помош на рекурзивни техники.
Типови на рекурзија
Рекурзијата е од два вида врз основа на тоа кога се упатува повикот до рекурзивниот метод.
Тие се:
#1) Рекурзија на опашката
Кога повикот до рекурзивниот метод е последната изјава извршена во рекурзивниот метод, таа се нарекува „Рекурзија на опашката“.
Кај рекурзијата на опашката, изјавата за рекурзивен повик обично се извршува заедно со изјавата за враќање на методот.
Општата синтакса за рекурзија на опашката е дадена подолу:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Рекурзија на глава
Рекурзија на глава е секој рекурзивен пристап кој не е рекурзија на опашката. Значи, дури и општата рекурзија е рекурзија напред.
Синтаксата на рекурзијата на главата е следнава:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Рекурзија против повторување во Java
| Рекурзија | Итерација |
|---|---|
| Рекурзија е процес каде што методот се повикува себеси постојано додека не се исполни основната состојба. | Итерацијата е процес со кој парче код постојано се извршува конечен број пати или додека не се исполни условот. |
| Дали апликацијата за функции. | Дали е применлива за јамки. |
| Добро работи запомала големина на кодот. | Добро работи за поголема големина на кодот. |
| Користи повеќе меморија бидејќи секој рекурзивен повик се турка во оџакот | Споредбено помалку меморија се користи. |
| Тешко за отстранување грешки и одржување | Полесно за отстранување грешки и одржување |
| Резултира со претекување на оџакот ако базата состојбата не е одредена или не е постигната. | Може да се извршува бесконечно, но на крајот ќе го запре извршувањето со какви било грешки во меморијата |
| Временската сложеност е многу висока. | Временската сложеност е релативно на долната страна. |
Често поставувани прашања
П #1) Како функционира рекурзијата во Java?
Одговор: При рекурзија, рекурзивната функција се повикува себеси постојано додека не се исполни основната состојба. Меморијата за повиканата функција се турка на оџакот на врвот на меморијата за функцијата за повикување. За секој повик на функција, се прави посебна копија на локални променливи.
П #2) Зошто се користи Рекурзија?
Одговор: Рекурзијата се користи за решавање на оние проблеми кои можат да се поделат на помали и целиот проблем може да се изрази во однос на помал проблем.
Рекурзијата се користи и за оние проблеми кои се премногу комплекс што треба да се реши со помош на итеративен пристап. Покрај проблемите за кои временската сложеност не е проблем, користете рекурзија.
П #3) Кои се придобивките одРекурзија?
Одговор:
Придобивките од рекурзијата вклучуваат:
- Рекурзијата го намалува непотребното повикување на функцијата.
- Рекурзијата ни овозможува лесно да ги решаваме проблемите во споредба со итеративниот пристап.
П #4) Која е подобра – Рекурзија или Итерација?
Одговор: Рекурзија прави повторени повици додека не се достигне основната функција. Така, има над глава на меморија бидејќи меморијата за секој повик на функција се турка на оџакот.
Итерацијата од друга страна нема многу надморска меморија. Извршувањето на рекурзијата е побавно од итеративниот пристап. Рекурзијата ја намалува големината на кодот додека итеративниот пристап го прави кодот голем.
П #5) Кои се предностите на рекурзијата во однос на повторувањето?
Одговор:
- Рекурзијата го прави кодот појасен и пократок.
- Рекурзијата е подобра од итеративниот пристап за проблеми како Кулата во Ханој, дрво премини, итн.
- Како што на секој функциски повик меморијата е вклучена во оџакот, рекурзијата користи повеќе меморија.
- Изведбата на рекурзија е побавна од итеративниот пристап.
Заклучок
Рекурзијата е многу важен концепт во софтверот без разлика на програмскиот јазик. Рекурзијата најчесто се користи за решавање на проблеми со структурата на податоци, како што се кули во Ханој, премини на дрвја, поврзани списоци итн. Иако е потребно повеќе меморија,рекурзијата го прави кодот поедноставен и појасен.
Испитавме сè за рекурзијата во ова упатство. Имплементиравме и бројни програмски примери за подобро разбирање на концептот.