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

Рекурсия в 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.

Эта программа выводит следующий результат:

Попробуйте написать следующую строку кода выше рекурсивного вызова:

Должно получатся следующим образом:

Что же интересно получаем?

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

Интересное видео про рекурсию в Java: