Классы. Часть 5 – рекурсивные методы.

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

В классе Recursion определен метод обратного отсчета countdown(). В классе Classes05 создается объект класса Recursion – rcn1 и на нем вызывается метод countdown().

Вывод у этой программы следующий: 10 9 8 7 6 5 4 3 2 1 0

В рекурсивных методах необходимо позаботиться о логике, которая прерывает их выполнение, иначе они будут выполнятся "вечно", то есть пока не израсходуют всю память стека и програ вылетит по ошибке нехватки памяти (StackOverflowError).

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

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

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

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

В классе Recursion определены рекурсивные методы, а в классе Classes005 они вызываются.

Программа генерирует следующий вывод:

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

Вывод у программы следующий:

Вот мы постепенно и подошли к передаче в методы, как аргументы, объектов. В данных последних примерах – массивы. Но в методы, как аргументы, можно передавать любые объекты.