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. Рекурсия По Сравнению С Итерацией
Рекурсия может помочь упростить реализацию некоторых сложных задач, сделав код более четким и читаемым.
Но, как мы уже видели, рекурсивный подход часто требует больше памяти, поскольку требуемая память стека увеличивается с каждым рекурсивным вызовом.
В качестве альтернативы, если мы можем решить проблему с помощью рекурсии, мы также можем решить ее с помощью итерации.
Например, наш метод sum может быть реализован с помощью итерации:
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 и так далее. Мы будем продолжать в том же духе, пока не дойдем до точки, где нам нужно вычислить (n-n)-ю степень 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 -й элемент Последовательности Фибоначчи . Чтобы реализовать рекурсивное решение, нам нужно выяснить условие Stop и Рекурсивный вызов .
К счастью, это действительно просто.
Назовем f(n) |/n -м значением последовательности. Тогда у нас будет f(n)(n-1) + f(n-2) (рекурсивный вызов ) .
Между тем, f(0) и f(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 .