Что такое рекурсия недостатки и преимущества java

BestProg

Рекурсия. Примеры решения задач. Преимущества и недостатки рекурсии

Содержание

Поиск на других ресурсах:

1. Что такое рекурсия? Что называется рекурсией?

В теории алгоритмов дается следующее определение рекурсии: рекурсия – это такой способ задания функции, при котором результат возврата из функции для данного значения аргумента определяется на основе результата возврата из той же функции для предыдущего (меньшего или большего) значения аргумента.

Другими словами, рекурсия – это вызов функции самой себя для перехода к следующему шагу рекурсии. Чтобы следующий шаг рекурсии отличался от предыдущего, значение как минимум одного из параметров функции должно изменяться в процессе рекурсивного вызова.

2. Объяснение к реализации задач на рекурсию. Как правильно организовать рекурсивный вызов функции?

Рекурсивное обращение к функции может быть осуществлено, если алгоритм определен рекурсивно. Использование рекурсии не всегда бывает эффективным, например, в случаях, где много переменных используются или влияют на количество итераций цикла. Однако, циклы, в которых количество изменяемых величин (итераторов) не очень велико, можно представить рекурсией.

Чтобы циклический процесс превратить в рекурсивный, нужно уметь определить (выделить) три важных момента:

3. Поиск суммы элементов массива. Пример

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

где n – количество элементов массива. Программный код функции следующий:

В вышеприведенном коде функция получает два параметра. Первый параметр i есть значением текущего индекса, который изменяет свое значение при каждом рекурсивном вызове. Второй параметр A – массив, элементы которого суммируются.

Поскольку, осуществляется сумма текущего значения A[i] со следующими, то указывается строка

Использование функции Sum() в другом программном коде может быть следующим:

В примере разработана рекурсивная функция, которая находит факториал заданного числа n

Программный код функции следующий:

При возврате на уровень выше возвращается текущее значение n и результат вычислений при следующих рекурсивных вызовах:

Использование функции в другом программном коде:

5. Программа нахождения наибольшего общего делителя по алгоритму Евклида. Пример

В примере определяется наибольший общий делитель по формуле Евклида:

Программный код функции следующий:

Использование функции MaxDivisor

Последовательность чисел Фибоначчи имеет вид:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Ниже приведен текст функции GetNFibonacci()

Использование метода GetNFibonacci() в другом программном коде:

7. Преимущества и недостатки использования рекурсии

Рекурсию часто сравнивают с итерацией. Организация циклического процесса с помощью рекурсии имеет свои преимущества и недостатки.

Можно выделить следующие взаимосвязанные преимущества рекурсии:

Недостатки рекурсии состоят в следующем:

Источник

Рекурсия В Java

Изучите основные понятия рекурсии в Java на примерах.

1. введение

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

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

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

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

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

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

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

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

2.2. Хвостовая Рекурсия По Сравнению С Головной Рекурсией

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

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

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

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

2.3. Рекурсия По Сравнению С Итерацией

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

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

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

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

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

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

3. Примеры

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

3.1. Нахождение N-й степени из десяти

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

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

К счастью, это действительно просто.

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

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

3.3. Преобразование из десятичной системы в двоичную

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

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

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

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

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

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

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

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

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

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

Источник

Рекурсия

— Привет, Амиго. Сегодня Билаабо расскажет тебе, что такое рекурсия.

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

— И как ты знаешь, внутренние переменные разных методов независимы друг от друга.

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

— Честно говоря, вижу, что метод в коде сам себя вызывает, но не понимаю, что именно при этом происходит.

— Да примерно то же, что и при вызове другого метода.

— Нет, я спрашиваю, что происходит с переменными? С их значениями? И как мы выходим из метода? Или мы выходим из всех сразу?

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

Т.е. каждый раз при вызове метода (даже самого себя) создаются новые переменные, которые хранят данные для этого метода. Никаких общих переменных нет.

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

— Ясно. А как работает выход из этих методов? Можно пример?

— Ладно. Один пример стоит тысячи слов. Вот тебе пример:

— Ок. Вроде понял. А зачем нужна рекурсия?

— Есть очень много задач, которые разбиваются на отдельные подзадачи, идентичные первоначальной задаче. Например, надо обойти все элементы XML-дерева. У каждого элемента может быть несколько дочерних элементов, а у них — свои.

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

Строка 8 – получаем список всех файлов (и директорий) в директории dir.

Источник

Блог только про Java

Учимся программировать на Java с нуля

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

в чем преимущество использования или создания рекурсивных функций в Java?

8 ответов

Иногда рекурсия помогает разработать более простой и читаемый код. Это особенно актуально для рекурсивных структур данных (например, деревьев) или рекурсивных алгоритмов.

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

Недостатком рекурсивного метода является то, что он требует больше ресурсов, а его глубина ограничена JVM.

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

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

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

Рекурсивная функция ничем не отличается от обычной функции!

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

Одним из примеров является функция чисел Фибоначчи.

ВНИМАНИЕ: нужно учитывать хорошие условия выхода, иначе неправильная рекурсия создаст исключение переполнения стека.

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

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

Если бы вы не использовали рекурсию, вам пришлось бы самостоятельно вести учет внешних структур данных (стека). В упомянутых случаях информация о состоянии хранится в стеке вызовов, и вам не нужно дополнительное администрирование. Так что в некоторых случаях они приводят к элегантным и производительным реализациям.

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

Хорошим примером является функция factorial() :

Во многих случаях, если рекурсивный вызов является последним действием, предпринятым функцией («хвостовая рекурсия»), то итеративная функция может использоваться так же легко. Вышеупомянутую функцию factorial() можно записать так:

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

Источник