Щоб зрозуміти, що таке рекурсія, необхідно зрозуміти, що таке рекурсія. Насправді, у розумінні таких функцій немає нічого складного, потрібно лише один раз добре розібратися в цьому. І попрактикуватися, якщо йдеться про програмування. Рекурсія зустрічається у програмуванні, а й у реальному житті. Візьми в руки дзеркало і встань навпроти іншого дзеркала. Відображення відображення позначиться на відображенні і так далі. Ти побачиш нескінченну кількість відображень, що йдуть у нескінченність. Більше про “реальну” рекурсію ти можеш знайти у статті “ Дню Сурока присвячується… ” Повернімося з реального світу до буднів програміста. Просте визначення: рекурсивні функції 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;
}
Подивимося результати виводу для дзвінків:
System.out.println(factorial(0));
System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(3));
System.out.println(factorial(4));
System.out.println(factorial(5));
System.out.println(factorial(6));
Отримаємо очікувані значення:
1
1
2
6
24
120
720
Додамо гарний висновок і обчислимо фаторіал для числа більше:
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;
}
немає сенсу і ми підемо в нескінченний цикл викликів методом себе. Варто додати перевірку на невід'ємність:
if (n < 0) {
System.out.println(«Зачем тебе факториал отрицательного числа?»);
return null;
}
І все буде добре.
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:
if (n == 1) return x;
Там же визначено і крок рекурсії:
return x * calculate(x, n - 1);
Залишилось додати перевірку валідності вхідних даних:
- Будь-яке число, крім нуля, в нульовому ступені дорівнює
1
. Якщоn = 0
, тоn! = 1
. Потрібно повернути1
. - Нуль будь-якою мірою дорівнює нулю.
- Невизначеність типу
0^0
не розглядатимемо і приймемо такі вхідні дані за невалідні.
private double calculate(int x, int n) throws ArithmeticException {
if (x == 0 && n == 0) {
throw new ArithmeticException("Невалидные входные данные: Неопределенность типа 0^0");
}
if (n < 0) {
throw new ArithmeticException("Невалидные входные данные: Факториал из отрицательного числа!");
}
if (n == 0) {
return 1;
}
if (x == 0) {
return 0;
}
if (x == 0) {
return 0;
}
return power(x, n) / n;
}
private double power(int x, int n) {
if (n == 1) return x;
return x * calculate(x, n - 1);
}
Ну, і при виклику функції потрібно не забути зловити помилку:
try {
System.out.println(calculate(x, n));
} catch (ArithmeticException e) {
System.out.println(e.getMessage());
}
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ