Пример использования рекурсии при обработке данных java

Рекурсия в Java

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

Мы объясним характеристики рекурсивной функции и покажем, как использовать рекурсию для решения различных задач в 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; in; 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 .

Источник

Рекурсия в Java: пример программы + детальный обзор

В языке Java поддерживается рекурсия — процесс определения чего-либо отно­сительно самого себя.

Применительно к программированию на Java рекурсия — это средство, которое позволяет методу вызывать самого себя. Такой метод назы­вается рекурсивным.

Классическим примером рекурсии служит вычисление факториала числа. Факториал числа N — это произведение всех целых чисел от 1 до N. Например ,факториал числа 3 равен 1 х 2 х 3, т.е. 6. Ниже показано, как вычислить факториал, используя рекурсивный метод.

Ниже приведен результат, выводимый этой программой.

Тем, кто незнаком с рекурсивными методами, принцип действия метода fact() может быть не совсем понятным.

Метод fact() действует следующим образом. Когда этот метод вызывается со значением 1 своего аргумента, возвращается зна­чение 1. В противном случае возвращается произведение fact(n — 1) * n .

Для вычисления этого выражения метод fact() вызывается со значением n — 1 своего аргумента. Этот процесс повторяется до тех пор, пока n не станет равным 1, после чего начнется возврат из последовательных вызовов метода fact().

Для того чтобы стал понятнее принцип действия рекурсивного метода fact(), обратимся к небольшому примеру.

Для расчета факториала числа З вслед за пер­вым вызовом метода fact() происходит второй вызов этого метода со значением 2 его аргумента.

Это, в свою очередь, приводит к третьему вызову метода fact() со значением 1 его аргумента. Возвращаемое из этого вызова значение 1 затем ум­ножается на 2 (т.е. значение n при втором вызове метода).

Полученный результат ,равный 2 , возвращается далее исходному вызову метода fact() и умножается на 3 (исходное значение n).

В конечном итоге получается искомый результат, равный 6. В метод fact() можно было бы ввести вызовы метода println(), чтобы отобра­жать уровень каждого вызова и промежуточные результаты вычисления фактори­ала заданного числа.

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

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

Рекурсивные методы выполняют дей­ствия, которые можно сравнить с раскладыванием и складыванием телескопа.

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

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

В таком случаев исполняющей системе Jаvа возникнет исключение. Но подобная ситуация не воз­никнет, если не выпустить рекурсивный метод из-под контроля.

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

Например, алгоритм быстрой сортировки очень трудно реализовать итерационным способом. А некоторые виды алгорит­мов, связанных с искусственным интеллектом, легче всего реализовать с помо­щью рекурсивных решений.

При написании рекурсивных методов следует позаботиться о том, чтобы в каком ­нибудь другом месте программы присутствовал условный оператор if, осуществляю­щий возврат из метода без его рекурсивного вызова.

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

Поэтому на стадии разработки рекурсивных методов рекомендуется как можно чаще делать вызовы метода println(), чтобы сле­дить за происходящим и прерывать выполнение при обнаружении ошибки.

Рассмотрим еще один пример организации рекурсии. В данном примере рекур­сивный метод рrintArrау() выводит первые i элементов из массива values.

Источник