recursion java tutorial with examples
Цей поглиблений посібник з рекурсії на Java пояснює, що таке рекурсія з прикладами, типами та супутніми поняттями. Він також охоплює рекурсію проти ітерації:
найкращий засіб для чищення комп'ютерів для Windows 10 -
З наших попередніх підручників з 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 елементів, ми шукаємо в цьому масиві даний ключовий елемент. На початку ми ділимо масив на дві половини, знаходячи середній елемент масиву.
Потім, залежно від того, клавіша mid, ми обмежуємо пошук у першій або другій половині масиву. Таким чином той самий процес повторюється, поки не буде знайдено розташування ключових елементів.
Ми реалізуємо цей алгоритм, використовуючи тут рекурсію.
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
| Рекурсія | Ітерація |
|---|---|
| Складність часу дуже висока. | Складність часу відносно нижча. |
| Рекурсія - це процес, коли метод неодноразово викликає себе, доки не буде дотримано базову умову. | Ітерація - це процес, за допомогою якого шматок коду неодноразово виконується протягом кінцевої кількості разів або до виконання умови. |
| Є додатком для функцій. | Застосовується для петель. |
| Добре працює для менших розмірів коду. | Добре працює для великих розмірів коду. |
| Використовує більше пам'яті, коли кожен рекурсивний виклик надходить у стек | Використовується порівняно менше пам'яті. |
| Важко налагоджувати та підтримувати | Простіше налагоджувати та підтримувати |
| Результати переповнення стека, якщо базовий стан не вказано або не досягнуто. | Може виконуватися нескінченно, але врешті-решт зупинить виконання з будь-якими помилками в пам'яті |
Часті запитання
Q # 1) Як рекурсія працює на Java?
Відповідь: У рекурсії рекурсивна функція викликає себе неодноразово, доки не буде виконано базову умову. Пам'ять для викликаної функції надходить у стек у верхній частині пам'яті для викликає функції. Для кожного виклику функції робиться окрема копія локальних змінних.
Q # 2) Чому використовується рекурсія?
Відповідь: Рекурсія використовується для вирішення тих проблем, які можна розбити на менші, і всю проблему можна виразити через меншу проблему.
Рекурсія також використовується для тих проблем, які занадто складні, щоб їх можна було вирішити за допомогою ітераційного підходу. Окрім проблем, для яких складність часу не є проблемою, використовуйте рекурсію.
Q # 3) Які переваги рекурсії?
Відповідь:
Переваги рекурсії включають:
- Рекурсія зменшує зайвий виклик функції.
- Рекурсія дозволяє нам легко вирішувати проблеми порівняно з ітераційним підходом.
Q # 4) Який з них краще - рекурсія чи ітерація?
найкращий безкоштовний прибиральник ПК 7
Відповідь: Рекурсія робить повторні виклики, доки не буде досягнуто базової функції. Таким чином, є запас пам'яті, оскільки пам'ять для кожного виклику функції надсилається в стек.
Ітерація, з іншого боку, не має великих витрат пам’яті. Виконання рекурсії відбувається повільніше, ніж ітераційний підхід. Рекурсія зменшує розмір коду, тоді як ітераційний підхід робить код великим.
Q # 5) Які переваги рекурсії перед ітерацією?
Відповідь:
- Рекурсія робить код чіткішим і коротшим.
- Рекурсія краща за ітераційний підхід для таких проблем, як Ханойська вежа, обхід дерев тощо.
- Оскільки кожен виклик функції має пам'ять, що надходить у стек, Recursion використовує більше пам'яті.
- Ефективність рекурсії повільніша за ітераційний підхід.
Висновок
Рекурсія - дуже важливе поняття в програмному забезпеченні, незалежно від мови програмування. Рекурсія в основному використовується для вирішення проблем структури даних, таких як вежі Ханоя, обхід дерев, пов'язані списки тощо. Хоча рекурсія і вимагає більше пам'яті, рекурсія робить код простішим та зрозумілішим.
У цьому посібнику ми вивчили все про рекурсію. Ми також застосували численні приклади програмування для кращого розуміння концепції.
=> Прочитайте серію Easy Java Training.
Рекомендована література
- Рекурсія в C ++
- Java Iterator: Навчіться використовувати ітератори в Java на прикладах
- Інтерфейс ListIterator в Java з прикладами
- Підручник JAVA для початківців: 100+ практичних навчальних посібників Java
- Підручник з Java для циклу з прикладами програм
- Java While Loop - Підручник із прикладами програмування
- Java Do While Loop - Підручник із прикладами
- Нерівний масив у Java - Підручник із прикладами