«Рекурсия в Java» - Spring на русском

«1. Введение

В этой статье мы сосредоточимся на основной концепции любого языка программирования — рекурсии.

Мы объясним характеристики рекурсивной функции и покажем, как использовать рекурсию для решения различных задач в Java.

2. Понимание рекурсии

2.1. Определение

В Java механизм вызова функций поддерживает возможность вызова самого метода. Эта функциональность известна как рекурсия.

Например, предположим, что мы хотим суммировать целые числа от 0 до некоторого значения n:

public int sum(int n) {
    if (n >= 1) {
        return sum(n - 1) + n;
    }
    return n;
}

Существуют два основных требования к рекурсивной функции:

Условие остановки — функция возвращает значение когда определенное условие выполнено, без дальнейшего рекурсивного вызова Рекурсивный вызов — функция вызывает себя с вводом, который на шаг ближе к условию остановки

Каждый рекурсивный вызов будет добавлять новый кадр в память стека JVM. Таким образом, если мы не будем обращать внимание на то, насколько глубоко может погрузиться наш рекурсивный вызов, может возникнуть исключение нехватки памяти.

Эту потенциальную проблему можно предотвратить, используя оптимизацию хвостовой рекурсии.

2.2. Хвостовая рекурсия против головной рекурсии

Мы называем рекурсивную функцию хвостовой рекурсией, когда рекурсивный вызов является последним, что функция выполняет. В противном случае это называется головной рекурсией.

Наша вышеприведенная реализация функции sum() является примером головной рекурсии и может быть изменена на хвостовую рекурсию:

public int tailSum(int currentSum, int n) {
    if (n <= 1) {
        return currentSum + n;
    }
    return tailSum(currentSum + n, n - 1);
}

При хвостовой рекурсии рекурсивный вызов — это последнее, что делает метод, поэтому ничего не осталось для выполнения в текущей функции.

Таким образом, логически нет необходимости хранить кадр стека текущей функции.

Хотя компилятор может использовать эту точку для оптимизации памяти, следует отметить, что компилятор Java пока не оптимизирует хвостовую рекурсию.

2.3. Рекурсия против итерации

Рекурсия может помочь упростить реализацию некоторых сложных задач, делая код более ясным и читабельным.

Но, как мы уже видели, рекурсивный подход часто требует больше памяти, так как требуемая память стека увеличивается с каждым рекурсивным вызовом.

В качестве альтернативы, если мы можем решить проблему с помощью рекурсии, мы также можем решить ее с помощью итерации.

Например, наш метод суммирования может быть реализован с использованием итерации:

public int iterativeSum(int n) {
    int sum = 0;
    if(n < 0) {
        return -1;
    }
    for(int i=0; i<=n; i++) {
        sum += i;
    }
    return sum;
}

По сравнению с рекурсией итеративный подход потенциально может дать более высокую производительность. При этом итерация будет более сложной и трудной для понимания по сравнению с рекурсией, например: обход бинарного дерева.

Правильный выбор между головной рекурсией, хвостовой рекурсией и итеративным подходом зависит от конкретной проблемы и ситуации.

3. Примеры

Теперь попробуем решить некоторые задачи рекурсивным способом.

3.1. Нахождение N-й степени числа 10

Предположим, нам нужно вычислить n-ю степень числа 10. Здесь наш вход равен n. Думая рекурсивно, мы можем сначала вычислить (n-1)-ю степень числа 10 и умножить результат на 10.

Затем для вычисления (n-1)-й степени числа 10 будет ( n-2)-я степень числа 10 и умножить результат на 10 и так далее. Мы будем продолжать в том же духе, пока не дойдем до точки, где нам нужно вычислить (nn)-ю степень числа 10, которая равна 1.

Если бы мы хотели реализовать это на Java, мы бы написали: ~~ ~

public int powerOf10(int n) {
    if (n == 0) {
        return 1;
    }
    return powerOf10(n-1) * 10;
}

3.2. Нахождение N-го элемента последовательности Фибоначчи

Начиная с 0 и 1, последовательность Фибоначчи представляет собой последовательность чисел, где каждое число определяется как сумма двух предшествующих ему чисел: 0 1 1 2 3 5 8 13 21 34 55 …

Итак, по заданному числу n наша задача состоит в том, чтобы найти n-й элемент последовательности Фибоначчи. Чтобы реализовать рекурсивное решение, нам нужно выяснить условие остановки и рекурсивный вызов.

К счастью, это очень просто.

Назовем f(n) n-м значением последовательности. Тогда у нас будет f(n) = f(n-1) + f(n-2) (рекурсивный вызов).

Между тем, f(0) = 0 и f(1) = 1 (условие остановки).

Тогда для нас действительно очевидно определить рекурсивный метод для решения проблемы:

public int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n-1) + fibonacci(n-2);
}

«

«3.3. Преобразование десятичного числа в двоичное

Теперь давайте рассмотрим задачу преобразования десятичного числа в двоичное. Требование состоит в том, чтобы реализовать метод, который получает положительное целое значение n и возвращает двоичное строковое представление.

Один из подходов к преобразованию десятичного числа в двоичное состоит в том, чтобы разделить значение на 2, записать остаток и продолжить делить частное на 2.

Мы продолжаем делить таким образом, пока не получим частное 0. Затем записывая все остатки в резервном порядке, мы получаем двоичную строку.

public String toBinary(int n) {
    if (n <= 1 ) {
        return String.valueOf(n);
    }
    return toBinary(n / 2) + String.valueOf(n % 2);
}

Следовательно, наша задача состоит в том, чтобы написать метод, возвращающий эти остатки в резервном порядке:

3.4. Высота бинарного дерева

Высота бинарного дерева определяется как количество ребер от корня до самого глубокого листа. Теперь наша задача состоит в том, чтобы вычислить это значение для заданного бинарного дерева.

Одним из простых подходов было бы найти самый глубокий лист, а затем подсчитать ребра между корнем и этим листом.

Но пытаясь придумать рекурсивное решение, мы можем переформулировать определение высоты бинарного дерева как максимальную высоту левой ветви корня и правой ветви корня плюс 1.

Если у корня нет левая ветвь и правая ветвь, его высота равна нулю.

public int calculateTreeHeight(BinaryNode root){
    if (root!= null) {
        if (root.getLeft() != null || root.getRight() != null) {
            return 1 + 
              max(calculateTreeHeight(root.left), 
                calculateTreeHeight(root.right));
        }
    }
    return 0;
}

Вот наша реализация:

Таким образом, мы видим, что некоторые проблемы могут быть решены с помощью рекурсии очень простым способом.

4. Заключение

В этом уроке мы представили концепцию рекурсии в Java и продемонстрировали ее на нескольких простых примерах.

«Рекурсия в Java»