Java руководство для начинающих - Шилдт Герберт (2012)

Действия нерекурсивного метода fact I () не требуют особых пояснений. В нем используется цикл, в котором числа, начиная с 1, последовательно умножаются друг на друга, постепенно образуя произведение, дающее факториал.

Рекурсивный метод f actR () действует несколько сложнее. Когда метод factR() вызывается с аргументом, равным 1, он возвращает 1, а иначе —произведение, определяемое из выражения factR(n-l)*n. Для вычисления этого выражения вызывается метод factR () с аргументом п-1. Этот процесс повторяется до тех пор, пока значение переменной п не окажется равным 1, после чего из предыдущих вызовов данного метода начнут возвращаться полученные значения. Например, при вычислении факториала 2 первый вызов метода factR () повлечет за собой второй вызов того же самого метода, но с аргументом 1. В результате метод возвратит значение 1, которое затем умножается на 2 (т.е. исходное значение переменной п). В результате всех этих вычислений будет получен факториал, равный 2. По желанию в тело метода factR () можно ввести операторы println (), чтобы сообщать, на каком именно уровне осуществляется очередной вызов, а также отображать промежуточные результаты вычислений.

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

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

Главное преимущество рекурсии заключается в том, что она позволяет реализовать некоторые алгоритмы яснее и проще, чем итерационным способом. Например, алгоритм быстрой сортировки довольно трудно реализовать итерационным способом. А некоторые задачи, например искусственного интеллекта, очевидно, требуют именно рекурсивного решения. При написании рекурсивных методов следует непременно указать в соответствующем месте условный оператор, например if, чтобы организовать возврат из метода без рекурсии. В противном случае возврат из вызванного однажды рекурсивного метода может вообще не произойти. Подобного рода ошибка весьма характерна для реализации рекурсии в практике программирования. Поэтому рекомендуется пользоваться операторами, содержащими вызовы метода println (), чтобы следить за происходящим в рекурсивном методе и прервать его выполнение, если в нем обнаружится ошибка.

Применение ключевого слова static