Рекурсія у Java

Щоб зрозуміти, що таке рекурсія, необхідно зрозуміти, що таке рекурсія. Насправді, у розумінні таких функцій немає нічого складного, потрібно лише один раз добре розібратися в цьому. І попрактикуватися, якщо йдеться про програмування. Рекурсія в Java - 1

Рекурсія зустрічається у програмуванні, а й у реальному житті. Візьми в руки дзеркало і встань навпроти іншого дзеркала. Відображення відображення позначиться на відображенні і так далі. Ти побачиш нескінченну кількість відображень, що йдуть у нескінченність. Більше про “реальну” рекурсію ти можеш знайти у статті “ Дню Сурока присвячується… ” Повернімося з реального світу до буднів програміста. Просте визначення: рекурсивні функції 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));

Отримаємо очікувані значення:

Додамо гарний висновок і обчислимо фаторіал для числа більше:

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());
}

Коментарі

ЩОБ ПОДИВИТИСЯ ВСІ КОМЕНТАРІ АБО ЗАЛИШИТИ КОМЕНТАР,
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ