Щоб зрозуміти, що таке рекурсія, потрібно зрозуміти, що таке рекурсія. Насправді, у розумінні таких функцій немає нічого складного, потрібно лише один раз добре в цьому розібратись. І попрактикуватись, якщо йдеться про програмування.
Рекурсія зустрічається не лише в програмуванні, але й у реальному житті. Візьми в руки дзеркало і стань навпроти іншого дзеркала. Відображення відображення відобразиться у відображенні і так далі. Ти побачиш нескінченну кількість відображень, що йдуть у нескінченність. Більше про “реальну” рекурсію ти можеш знайти в статті “Дню бабака присвячується…”
Повернімося з реального світу до буднів програміста. Просте визначення: рекурсивні функції в Java – це функції, які викликають самі себе.
Наведу дуже простий і дуже шкідливий приклад:
public void recursionFucn() {
System.out.println("Привіт, JavaRush!");
recursionFucn();
}
Чим же він шкідливий? Пропоную перевірити самостійно! Якщо наважишся на цю авантюру (а ти, скоріш за все, наважишся, тижпрограміст!), напиши в коментарі, яку помилку видасть JVM =)
І цей приклад, і багато інших, демонструють, що до застосування рекурсії в Java потрібно підходити обережно. Треба розуміти, де, коли і навіщо виправданий такий підхід до розв'язання задачі, і слідкувати, щоб твоя функція не перетворила виконання програми на «День бабака».
Є ще два важливих для розуміння рекурсії визначення:
Базис рекурсії – умова виходу з блоку рекурсивних викликів – базове розв'язання задачі, за умов, коли немає необхідності викликати рекурсію.
Крок рекурсії – виклик функцією самої себе з зміною параметрів.
Класичний приклад застосування рекурсивної функції – обчислення факторіалу від числа. Якщо раптом забув, нагадаю: факторіал додатнього цілого числа N (позначається як N!) — це добуток чисел від 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. До речі, факторіал нуля за визначенням дорівнює 1. Тож факторіал можна знайти для будь-якого цілого додатнього числа та нуля (мовою математики — для множини невід'ємних цілих чисел або ж для множини натуральних чисел і нуля).
Думаю, ти розумієш, що запрограмувати факторіал можна за допомогою циклів. Власне, ось нерекурсивний метод розв'язання цієї задачі:
private int fact(int n) {
int result = 1;
for (int i = 1; i <= n; i++) {
result = result * i;
}
return result;
}
Додамо перевірку того, що число додатнє і ціле, та окремо перевірку для нуля.
private int fact(int n) {
if (n < 0) {
System.out.println("Навіщо тобі факторіал з від'ємного числа?");
return null;
}
int result = 1;
if (n == 0) {
return result;
}
for (int i = 1; i <= n; i++) {
result = result * i;
}
return result;
}
Тепер наведу код методу для рекурсивного розв'язання цієї задачі:
private int factorial(int n) {
int result = 1;
if (n == 1 || n == 0) {
return result;
}
result = n * factorial(n-1);
return result;
}
Додамо красивий вивід і обчислимо факторіал для числа більшого:
private int factorial(int n) {
int result = 1;
if (n == 0) {
System.out.print(" = ");
return result;
}
if (n == 1) {
System.out.print(" * 1 = ");
return result;
}
System.out.print(n);
if (n != 2) {
System.out.print(" * ");
}
result = n * factorial(n-1);
return result;
}
System.out.println(factorial(15) + "!");
Отримаємо: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000!
У цьому випадку застосування рекурсивної функції виправдано та безпечно. Ми чітко позначили умову виходу з рекурсивного блоку, і ми впевнені в тому, що він досяжний: ми вводимо ціле невід'ємне число, у випадку, якщо число дорівнює нулю або одиниці - повертаємо результат, якщо ж число більше — множимо результат на функцію від числа n-1.
На прикладі факторіалу від трьох:
factorial(3) всередині себе виконає наступне:
result = 3 * factorial(2); (рекурсивний виклик)
factorial(2) всередині себе виконає наступне:
result = 2 * factorial(1); (рекурсивний виклик)
factorial(1) поверне 1 (базис рекурсії)
factorial(2) поверне 2 * 1
factorial(3) поверне 3 * 2 * 1
З приводу обережності застосування: у чому вразливість цієї функції? Якщо дати методу як параметр від'ємне число, то перевірка
if (n == 1 || n == 0) {
return result;
}
немає сенсу і ми підемо у нескінченний цикл викликів методом самого себе.
Слід додати перевірку на невід'ємність:
І все буде добре.
У чому перевага одного методу над іншим? Здається, що великої різниці немає, але насправді багато рекурсивних викликів негативно позначаться на продуктивності та споживанні пам'яті: стек викликів – практично неконтрольований ресурс і за різних умов виклику однієї і тієї ж рекурсивної функції, ми можемо отримати або не отримати проблеми, пов'язані з цим ресурсом.
Практично всі задачі, розв'язувані за допомогою ітерацій (циклів типу for-each), можна вирішити і рекурсивно. Перевага рекурсії у читабельності та простоті написання, про недоліки ми говорили вище: можливість «вистрілити собі в ногу» неабияка.
Ще більш обережними треба бути при використанні так званої «складної рекурсії»:
Функція A() викличе функцію B(), яка викликає функцію A().Для розв'язання таких задач необхідне повне розуміння того, як працює рекурсія.
Приклад такої задачі: обчислення значення x^n/(n!). Факторіал, як ми обговорили вище, визначений на множині невід'ємних цілих чисел.
Наостанок наведу код розв'язання. Складна рекурсія буде складатись з двох методів:
private double calculate(int x, int n) {
return power(x, n) / n;
}
private double power(int x, int n) {
if (n == 1) return x;
return x * calculate(x, n - 1);
}
Для входу в рекурсію використовується метод calculate, який викликає метод power, у свою чергу викликаючий метод calculate.
Базис рекурсії ми позначили у методі power:
Рекурсія зустрічається не лише в програмуванні, але й у реальному житті. Візьми в руки дзеркало і стань навпроти іншого дзеркала. Відображення відображення відобразиться у відображенні і так далі. Ти побачиш нескінченну кількість відображень, що йдуть у нескінченність. Більше про “реальну” рекурсію ти можеш знайти в статті “Дню бабака присвячується…”
Повернімося з реального світу до буднів програміста. Просте визначення: рекурсивні функції в Java – це функції, які викликають самі себе.
Наведу дуже простий і дуже шкідливий приклад:
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ