Цей поглиблений підручник з рекурсії в Java пояснює, що таке рекурсія, з прикладами, типами та пов'язаними з нею поняттями. Він також розглядає рекурсію в порівнянні з ітераціями:
З наших попередніх уроків Java ми бачили ітераційний підхід, коли ми оголошуємо цикл, а потім ітераційно проходимо по структурі даних, беручи по одному елементу за раз.
Ми також розглянули умовний потік, де знову ж таки зберігаємо одну змінну циклу і повторюємо фрагмент коду, доки змінна циклу не задовольнить умову. Що стосується викликів функцій, то ми також дослідили ітераційний підхід до викликів функцій.
У цьому уроці ми обговоримо інший підхід до програмування, а саме рекурсивний підхід.
Що таке рекурсія в Java?
Рекурсія - це процес, за допомогою якого функція або метод викликає себе знову і знову. Функція, яка викликається знову і знову прямо або опосередковано, називається "рекурсивною функцією".
Ми розглянемо різні приклади для розуміння рекурсії. Тепер давайте розглянемо синтаксис рекурсії.
Синтаксис рекурсії
Будь-який метод, що реалізує рекурсію, складається з двох основних частин:
- Виклик методу, який може викликати сам себе, тобто рекурсивний
- Умова, яка зупинить рекурсію.
Зверніть увагу, що передумова необхідна для будь-якого рекурсивного методу, оскільки, якщо ми не перервемо рекурсію, то вона продовжуватиметься нескінченно і призведе до переповнення стеку.
Загальний синтаксис рекурсії наступний:
methodName (T параметрів...) { if (передумова == true) //передумова або базова умова { return result; } return methodName (T параметрів...); //рекурсивний виклик } Зверніть увагу, що передумову також називають базовою умовою. Ми поговоримо про базову умову в наступному розділі.
Розуміння рекурсії в Java
У цьому розділі ми спробуємо зрозуміти процес рекурсії і побачити, як він відбувається. Ми дізнаємося про базову умову, переповнення стеку, побачимо, як можна вирішити конкретну проблему за допомогою рекурсії та інші подібні деталі.
Базова умова рекурсії
При написанні рекурсивної програми ми повинні спочатку надати розв'язок для базового випадку. Потім ми виражаємо більшу проблему в термінах менших проблем.
В якості наприклад, візьмемо класичну задачу на обчислення факторіалу числа. За заданим числом n потрібно знайти факторіал від n, позначений через n!
Тепер реалізуємо програму для обчислення n факторіалів (n!) з використанням рекурсії.
public class Main{ static int fact(int n) { if (n == 1) // базова умова 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) // базова умова, що призводить до переповнення стеку 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 { //метод обчислення ряду Фібоначчі 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; //вивести перші 10 чисел ряду Фібоначчі System.out.println ("Ряд Фібоначчі: перші 10 чисел:"); 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 { // перевірка, чи число num містить тільки одну цифру public static int oneDigit(int num) { if ((num>= 0) && (num <10)) return 1; else return 0; } //паліндромна утиліта public static int isPalindrome_util (int num, int revNum) throws Exception { // базова умова; повертаємо якщо num=0 if (num == 0) { return revNum; } else { //викликутиліта revNum = isPalindrome_util(num / 10, revNum); } // Перевірити, чи перша цифра num та revNum рівні if (num % 10 == revNum % 10) { // якщо так, то revNum буде рухатись разом з num return revNum / 10; } else { // вихід throw new Exception(); } } //метод перевірки, чи задане число є паліндромом з використанням паліндромної утиліти public static int isPalindrome(int num) throwsException { 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("Так, задане число " + n + " є паліндромом."); } catch (Exception e) { System.out.println("Ні, задане число " + n + " не є паліндромом."); } n = 1221; try { isPalindrome(n);System.out.println("Так, задане число " + n + " є паліндромом."); } catch (Exception e) { System.out.println("Ні, задане число " + n + " не є паліндромом."); } } } Вихідні дані
#3) Зворотна рекурсія рядків Java
За заданим рядком "Hello" ми повинні обернути його так, щоб отриманий рядок був "olleH".
Починаючи з останнього символу в рядку, ми рекурсивно виводимо кожен символ, поки не вичерпаємо всі символи в рядку.
У наведеній нижче програмі використовується рекурсія для реверсування заданого рядка.
class String_Reverse { //рекурсивний метод реверсування заданого рядка void reverseString(String str) { //базова умова; повернути, якщо рядок нульовий або містить 1 або менше символів if ((str==null)} } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("Заданий рядок: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("Зворотний рядок: "); obj.reverseString(inputstr); } } Вихідні дані
#4) Рекурсія двійкового пошуку на Java
Алгоритм бінарного пошуку є відомим алгоритмом пошуку. У цьому алгоритмі, маючи відсортований масив з n елементів, ми шукаємо в цьому масиві заданий ключовий елемент. На початку ми ділимо масив на дві половини, знаходячи середній елемент масиву.
Потім, залежно від того, чи є ключ посередині, ми обмежуємо пошук в першій або другій половині масиву. Таким чином той самий процес повторюється до тих пір, поки не буде знайдено розташування ключових елементів.
Тут ми реалізуємо цей алгоритм за допомогою рекурсії.
import java.util.*; class Binary_Search { // рекурсивний бінарний пошук int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { //обчислюємо середину масиву int mid = left + (right - left) / 2; // якщо ключ знаходиться в середині, повертаємо mid if (numArray[mid] == key) return mid; // якщо ключ key) return binarySearch(numArray, left, mid - 1, key); // В іншому випадку рекурсивно шукаємо вправий підмасив return binarySearch(numArray, mid + 1, right, key); } // немає елементів у масиві, повернути -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //оголошуємо та виводимо масив int numArray[] = { 4,6,12,16,22}; System.out.println("Заданий масив : " + Arrays.toString(numArray)); int len = numArray.length; //довжина масивуint key = 16; //ключ для пошуку int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Елемент " + key + "відсутній"); else System.out.println("Елемент " + key + "знайдено за індексом " + result); } } Вихідні дані
#5) Пошук мінімального значення в масиві з допомогою рекурсії
Використовуючи рекурсію, ми також можемо знайти мінімальне значення в масиві.
Нижче наведено програму на Java для знаходження мінімального значення у масиві.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //повернути перший елемент, якщо тільки один елемент або мінімум з елементів масиву (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("Дано масив : " + Arrays.toString(numArray)); int n =numArray.length; System.out.print("Мінімальний елемент масиву: " + getMin(numArray, 0, n) + "\n"); } } Вихідні дані
Це лише деякі з прикладів рекурсії. Окрім цих прикладів, багато інших проблем у програмному забезпеченні можуть бути реалізовані за допомогою рекурсивних методів.
Типи рекурсії
Рекурсія буває двох типів, залежно від того, коли здійснюється виклик рекурсивного методу.
Так і є:
#1) Хвостова рекурсія
Коли виклик рекурсивного методу є останнім оператором, що виконується всередині рекурсивного методу, це називається "Хвостова рекурсія".
У хвостовій рекурсії рекурсивний оператор виклику зазвичай виконується разом з оператором повернення методу.
Загальний синтаксис хвостової рекурсії наведено нижче:
methodName ( T параметрів ...){ { if (base_condition == true) { return result; } return methodName (T параметрів ...) //хвостова рекурсія } #2) Рекурсія голови
Головна рекурсія - це будь-який рекурсивний підхід, який не є хвостовою рекурсією. Отже, навіть загальна рекурсія є головною рекурсією.
Синтаксис рекурсії заголовків наступний:
methodName (T параметрів...){ if (some_condition == true) { return methodName (T параметрів...); } return result; } Рекурсія та ітерація в Java
| Рекурсія | Ітерація |
|---|---|
| Рекурсія - це процес, в якому метод викликає сам себе багаторазово, поки не буде виконано базову умову. | Ітерація - це процес, за допомогою якого фрагмент коду повторюється скінченну кількість разів або до тих пір, поки не буде виконано певну умову. |
| Це заявка на функції. | Застосовується для циклів. |
| Добре працює для меншого розміру коду. | Добре працює для більшого розміру коду. |
| Використовує більше пам'яті, оскільки кожен рекурсивний виклик виштовхується до стеку | Використовується порівняно менше пам'яті. |
| Складно налагоджувати та підтримувати | Легше налагоджувати та обслуговувати |
| Призводить до переповнення стеку, якщо базова умова не вказана або не досягнута. | Може виконуватися нескінченно, але врешті-решт зупинить виконання при виникненні помилок у пам'яті |
| Складність часу дуже висока. | Часова складність є відносно нижчою. |
Поширені запитання
Питання #1) Як працює рекурсія в Java?
Відповідай: У рекурсії рекурсивна функція викликає сама себе багаторазово, поки не буде виконано базову умову. Пам'ять для викликаної функції переміщується в стек на вершину пам'яті для викликаючої функції. Для кожного виклику функції створюється окрема копія локальних змінних.
Q #2) Для чого використовується рекурсія?
Відповідай: Рекурсія використовується для вирішення тих проблем, які можна розбити на менші, і всю проблему можна виразити через меншу проблему.
Рекурсія також використовується для тих задач, які є надто складними для розв'язання за допомогою ітеративного підходу. Окрім задач, для яких часова складність не є проблемою, використовуйте рекурсію.
Q #3) Які переваги рекурсії?
Відповідай:
Переваги рекурсії полягають у наступному:
- Рекурсія зменшує надлишковий виклик функції.
- Рекурсія дозволяє нам вирішувати проблеми простіше, якщо порівнювати з ітеративним підходом.
Q #4) Що краще - рекурсія чи ітерація?
Відповідай: Рекурсія виконує повторні виклики до тих пір, поки не буде досягнута базова функція. Таким чином, виникає перевитрата пам'яті, оскільки пам'ять для кожного виклику функції виштовхується в стек.
З іншого боку, ітерація не має великих витрат пам'яті. Рекурсія виконується повільніше, ніж ітераційний підхід. Рекурсія зменшує розмір коду, в той час як ітераційний підхід робить код великим.
Q #5) Які переваги рекурсії над ітерацією?
Відповідай:
- Рекурсія робить код зрозумілішим і коротшим.
- Рекурсія краща за ітераційний підхід для задач на кшталт Ханойської вежі, обходу дерев тощо.
- Оскільки кожен виклик функції витісняє пам'ять у стек, рекурсія використовує більше пам'яті.
- Рекурсія працює повільніше, ніж ітеративний підхід.
Висновок
Рекурсія є дуже важливою концепцією в програмному забезпеченні, незалежно від мови програмування. Рекурсія найчастіше використовується для вирішення проблем зі структурою даних, таких як ханойські вежі, обхід дерев, зв'язані списки і т.д. Хоча вона займає більше пам'яті, рекурсія робить код простішим і зрозумілішим.
У цьому підручнику ми розглянули все про рекурсію, а також реалізували численні програмні приклади для кращого розуміння цієї концепції.