Что такое рекурсия в java
Рекурсия В 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 и продемонстрировали ее на нескольких простых примерах.
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 с нуля
Рекурсия в Java: пример программы + детальный обзор
Ниже приведен результат, выводимый этой программой.
Тем, кто незнаком с рекурсивными методами, принцип действия метода fact() может быть не совсем понятным.
Для того чтобы стал понятнее принцип действия рекурсивного метода fact(), обратимся к небольшому примеру.
Для расчета факториала числа З вслед за первым вызовом метода fact() происходит второй вызов этого метода со значением 2 его аргумента.
Это, в свою очередь, приводит к третьему вызову метода fact() со значением 1 его аргумента. Возвращаемое из этого вызова значение 1 затем умножается на 2 (т.е. значение n при втором вызове метода).
В конечном итоге получается искомый результат, равный 6. В метод fact() можно было бы ввести вызовы метода println(), чтобы отображать уровень каждого вызова и промежуточные результаты вычисления факториала заданного числа.
Когда рекурсивный метод вызывает самого себя, новым локальным переменными параметрам выделяется место в стеке и код метода выполняется с этими новыми исходными значениями.
При каждом возврате из вызова рекурсивного методапрежние локальные переменные и параметры удаляются из стека, а выполнение продолжается с точки вызова в самом методе.
Рекурсивные методы выполняют действия, которые можно сравнить с раскладыванием и складыванием телескопа.
Вследствие издержек на дополнительные вызовы рекурсивные варианты многих процедур могут выполняться медленнее их итерационных аналогов.
Слишком большое количество вызовов рекурсивного метода может привести к переполнению стека, поскольку параметры и локальные переменные сохраняются в стеке, а при каждом новом вызове создаются новые копии этих значений.
В таком случаев исполняющей системе Jаvа возникнет исключение. Но подобная ситуация не возникнет, если не выпустить рекурсивный метод из-под контроля.
Главное преимущество рекурсивных методов заключается в том, что их можно применять для реализации более простых и понятных вариантов некоторых алгоритмов, чем их итерационные аналоги.
Например, алгоритм быстрой сортировки очень трудно реализовать итерационным способом. А некоторые виды алгоритмов, связанных с искусственным интеллектом, легче всего реализовать с помощью рекурсивных решений.
При написании рекурсивных методов следует позаботиться о том, чтобы в каком нибудь другом месте программы присутствовал условный оператор if, осуществляющий возврат из метода без его рекурсивного вызова.
В противном случае возврата из рекурсивно вызываемого метода так и не произойдет. Подобная ошибка очень часто встречается при организации рекурсии.
Поэтому на стадии разработки рекурсивных методов рекомендуется как можно чаще делать вызовы метода println(), чтобы следить за происходящим и прерывать выполнение при обнаружении ошибки.
Рассмотрим еще один пример организации рекурсии. В данном примере рекурсивный метод рrintArrау() выводит первые i элементов из массива values.
Рекурсия. Занимательные задачки
В этой статье речь пойдет о задачах на рекурсию и о том как их решать. 
Кратко о рекурсии
Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Один из вариантов увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.
В программировании рекурсия тесно связана с функциями, точнее именно благодаря функциям в программировании существует такое понятие как рекурсия или рекурсивная функция. Простыми словами, рекурсия – определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию).
Задачи
При изучении рекурсии наиболее эффективным для понимания рекурсии является решение задач.
Любой алгоритм, реализованный в рекурсивной форме, может быть переписан в итерационном виде и наоборот. Останется вопрос, надо ли это, и насколько это будет это эффективно.
Для обоснования можно привести такие доводы.
Для начала можно вспомнить определение рекурсии и итерации. Рекурсия — это такой способ организации обработки данных, при котором программа вызывает сама себя непосредственно, либо с помощью других программ. Итерация — это способ организации обработки данных, при котором определенные действия повторяются многократно, не приводя при этом к рекурсивным вызовам программ.
После чего можно сделать вывод, что они взаимно заменимы, но не всегда с одинаковыми затратами по ресурсам и скорости. Для обоснования можно привести такой пример: имеется функция, в которой для организации некого алгоритма имеется цикл, выполняющий последовательность действий в зависимости от текущего значения счетчика (может от него и не зависеть). Раз имеется цикл, значит, в теле повторяется последовательность действий — итерации цикла. Можно вынести операции в отдельную подпрограмму и передавать ей значение счетчика, если таковое есть. По завершению выполнения подпрограммы мы проверяем условия выполнения цикла, и если оно верно, переходим к новому вызову подпрограммы, если ложно — завершаем выполнение. Т.к. все содержание цикла мы поместили в подпрограмму, значит, условие на выполнение цикла помещено также в подпрограмму, и получить его можно через возвращающее значение функции, параметры передающееся по ссылке или указателю в подпрограмму, а также глобальные переменные. Далее легко показать, что вызов данной подпрограммы из цикла легко переделать на вызов, или не вызов (возврата значения или просто завершения работы) подпрограммы из нее самой, руководствуясь какими-либо условиями (теми, что раньше были в условии цикла). Теперь, если посмотреть на нашу абстрактную программу, она примерно выглядит как передача значений подпрограмме и их использование, которые изменит подпрограмма по завершению, т.е. мы заменили итеративный цикл на рекурсивный вызов подпрограммы для решения данного алгоритма.
Задача по приведению рекурсии к итеративному подходу симметрична.
Подводя итог, можно выразить такие мысли: для каждого подхода существует свой класс задач, который определяется по конкретным требованиям к конкретной задаче.
Более подробно с этим можно познакомиться тут
Так же как и у перебора (цикла) у рекурсии должно быть условие остановки — Базовый случай (иначе также как и цикл рекурсия будет работать вечно — infinite). Это условие и является тем случаем к которому рекурсия идет (шаг рекурсии). При каждом шаге вызывается рекурсивная функция до тех пор пока при следующем вызове не сработает базовое условие и произойдет остановка рекурсии(а точнее возврат к последнему вызову функции). Всё решение сводится к решению базового случая. В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение.
Тут Базовым условием является условие когда n=1. Так как мы знаем что 1!=1 и для вычисления 1! нам ни чего не нужно. Чтобы вычислить 2! мы можем использовать 1!, т.е. 2!=1!*2. Чтобы вычислить 3! нам нужно 2!*3… Чтобы вычислить n! нам нужно (n-1)!*n. Это и является шагом рекурсии. Иными словами, чтобы получить значение факториала от числа n, достаточно умножить на n значение факториала от предыдущего числа.
В сети при обьяснении рекурсии также даются задачи нахождения чисел Фибоначчи и Ханойская башня
Рассмотрим же теперь задачи с различным уровнем сложности.
Попробуйте их решить самостоятельно используя метод описанный выше. При решении попробуйте думать рекурсивно. Какой базовый случай в задаче? Какой Шаг рекурсии или рекурсивное условие?
Поехали! Решения задач предоставлены на языке Java.
A: От 1 до n
Дано натуральное число n. Выведите все числа от 1 до n.
Рекурсия Java
В этом руководстве вы узнаете о рекурсивной функции Java, ее преимуществах и недостатках.
В Java метод, который вызывает сам себя, известен как рекурсивный метод. И этот процесс известен как рекурсия.
В качестве примера физического мира можно поместить два параллельных зеркала, обращенных друг к другу. Любой объект между ними будет отражаться рекурсивно.
Как работает рекурсия?
В приведенном выше примере мы вызвали recurse() метод изнутри main метода. (обычный вызов метода). И внутри метода recurse () мы снова вызываем тот же метод рекурсии. Это рекурсивный вызов.
Чтобы остановить рекурсивный вызов, нам нужно предоставить некоторые условия внутри метода. В противном случае метод будет вызываться бесконечно.
Следовательно, мы используем оператор if… else (или аналогичный подход) для завершения рекурсивного вызова внутри метода.
Пример: факториал числа с использованием рекурсии
Выход :
Здесь обратите внимание на утверждение,
Когда n равно 0, if оператор возвращает false, следовательно, возвращается 1. Наконец, накопленный результат передается в main() метод.
Работа факторной программы
Изображение ниже даст вам лучшее представление о том, как выполняется факториальная программа с использованием рекурсии.
Факториальная программа с использованием рекурсии
Преимущества и недостатки рекурсии
Когда выполняется рекурсивный вызов, в стеке выделяются новые места для хранения переменных. Когда каждый рекурсивный вызов возвращается, старые переменные и параметры удаляются из стека. Следовательно, рекурсия обычно использует больше памяти и обычно выполняется медленно.
С другой стороны, рекурсивное решение намного проще и требует меньше времени на написание, отладку и поддержку.
Рекомендуемая литература: каковы преимущества и недостатки рекурсии?