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-й степени десяти
Предположим, нам нужно вычислить 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 и продемонстрировали ее на нескольких простых примерах.
Реализацию этой статьи можно найти на Github .