recursion java tutorial with examples
Този задълбочен урок за рекурсия в Java обяснява какво е рекурсия с примери, типове и свързани понятия. Той също така обхваща Recursion Vs Iteration:
От нашите по-ранни уроци в Java видяхме итеративния подход, при който декларираме цикъл и след това преминаваме през структура на данни по итеративен начин, като вземаме по един елемент в даден момент.
Виждали сме и условния поток, където отново запазваме една променлива на цикъла и повтаряме парче код, докато променливата на цикъла отговаря на условието. Що се отнася до извикванията на функции, ние изследвахме итеративния подход и за извиквания на функции.
=> Проверете ВСИЧКИ уроци за Java тук.
В този урок ще обсъдим различен подход към програмирането, т.е. рекурсивен подход.
Какво ще научите:
- Какво представлява рекурсията в Java?
- Рекурсия срещу итерация в 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) is the base condition and when this condition is reached, the function returns 1. The else part of the function is the recursive call. But every time the recursive method is called, n is decremented by 1.
По този начин можем да заключим, че в крайна сметка стойността на n ще стане 1 или по-малка от 1 и в този момент методът ще върне стойност 1. Това основно условие ще бъде постигнато и функцията ще спре. Обърнете внимание, че стойността на n може да бъде всичко, стига да отговаря на основното условие.
Решаване на проблеми с помощта на рекурсия
Основната идея на използването на рекурсията е да се изрази по-големият проблем по отношение на по-малките проблеми. Също така трябва да добавим едно или повече базови условия, за да можем да излезем от рекурсия.
Това вече беше демонстрирано в горния факториален пример. В тази програма изразихме n факториал (n!) По отношение на по-малки стойности и имахме основно условие (n<=1) so that when n reaches 1, we can quit the recursive method.
Грешка при препълване на стека при рекурсия
Знаем, че когато се извика всеки метод или функция, състоянието на функцията се съхранява в стека и се извлича, когато функцията се върне. Стекът се използва и за рекурсивния метод.
Но в случай на рекурсия може да възникне проблем, ако не дефинираме основното състояние или когато основното състояние по някакъв начин не е достигнато или изпълнено. Ако възникне тази ситуация, може да възникне препълване на стека.
Нека разгледаме примера по-долу за факториална нотация.
Тук сме дали грешно основно условие, 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. In this case, as well the method will never execute the base condition and result in a stack overflow.
Примери за рекурсия в 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) Обратна низова рекурсия Java
Като се има предвид низ „Здравейте“, трябва да го обърнем, така че полученият низ да е „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) Двоично търсене на Java рекурсия
Двоичен алгоритъм за търсене е известен алгоритъм за търсене. В този алгоритъм, при сортиран масив от 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) Намерете минимална стойност в масива, използвайки рекурсия
Използвайки рекурсия, можем да намерим и минималната стойност в масива.
Програмата Java за намиране на минималната стойност в масива е дадена по-долу.
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) + '
'); } }Изход
Това са някои от примерите за рекурсия. Освен тези примери, много други проблеми в софтуера могат да бъдат приложени с помощта на рекурсивни техники.
Видове рекурсия
Рекурсията е от два вида въз основа на това, кога се извършва повикването към рекурсивния метод.
Те са:
# 1) Рекурсия на опашката
Когато извикването на рекурсивния метод е последният оператор, изпълнен в рекурсивния метод, той се нарича „Рекурсия на опашката“.
В рекурсията на опашката рекурсивното извикване обикновено се изпълнява заедно с оператора return на метода.
Общият синтаксис за рекурсия на опашката е даден по-долу:
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?
Отговор: При рекурсия рекурсивната функция се извиква многократно, докато се изпълни основното условие. Паметта за извиканата функция се премества в стека в горната част на паметта за извикващата функция. За всяко извикване на функция се прави отделно копие на локални променливи.
Q # 2) Защо се използва рекурсия?
Отговор: Рекурсията се използва за решаване на онези проблеми, които могат да бъдат разбити на по-малки и целият проблем може да бъде изразен като по-малък проблем.
Рекурсията се използва и за онези проблеми, които са твърде сложни, за да бъдат решени с помощта на итеративен подход. Освен проблемите, за които сложността на времето не е проблем, използвайте рекурсия.
Q # 3) Какви са ползите от рекурсията?
Отговор:
Ползите от рекурсията включват:
- Рекурсията намалява излишното извикване на функция.
- Рекурсията ни позволява лесно да решаваме проблеми в сравнение с итеративния подход.
В # 4) Коя е по-добра - рекурсия или итерация?
Отговор: Рекурсията прави повторни повиквания, докато се достигне основната функция. По този начин има допълнителна памет, тъй като паметта за всяко извикване на функция се натиска към стека.
Итерацията, от друга страна, няма много излишни памет. Изпълнението на рекурсията е по-бавно от итеративния подход. Рекурсията намалява размера на кода, докато итеративният подход прави кода голям.
Q # 5) Какви са предимствата на рекурсията пред итерацията?
Отговор:
- Рекурсията прави кода по-ясен и кратък.
- Рекурсията е по-добра от итеративния подход за проблеми като Ханойската кула, обхождане на дървета и т.н.
- Тъй като всяко извикване на функцията има памет, притисната към стека, Recursion използва повече памет.
- Изпълнението на рекурсията е по-бавно от итеративния подход.
Заключение
Рекурсията е много важно понятие в софтуера, независимо от езика за програмиране. Рекурсията се използва най-вече за решаване на проблеми със структурата на данни като кули на Ханой, обхождане на дървета, свързани списъци и др. Въпреки че отнема повече памет, рекурсията прави кода по-опростен и по-ясен.
Ние разгледахме всичко за рекурсията в този урок. Също така внедрихме множество примери за програмиране за по-добро разбиране на концепцията.
=> Прочетете серията Easy Training Training.
Препоръчително четене
- Рекурсия в C ++
- Java Iterator: Научете се да използвате итератори в Java с примери
- ListIterator интерфейс в Java с примери
- Урок за JAVA за начинаещи: 100+ практически ръководства за Java видео
- Урок за Java за цикъл с примери за програми
- Java While Loop - Урок с примери за програмиране
- Java Do While Loop - Урок с примери
- Назъбен масив в Java - урок с примери