Рекурсия без ветвления

Рекурсия

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

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

 

Стек вызовов

 

Чтобы понять, как работает рекурсивный метод, нужно знать, как распределяется память во время исполнения программы. В текущий момент времени может исполняться только один единственный метод из всей программы. Это значит, что, если метод а() вызывает в своем теле метод b(), а сам а() вызывается в main(), то при запуске программы управление сначала будет передано методу main(), затем методу а(), затем методу b(). Метод b() вернёт результат и управление в а(), а()вернет результат и управление в main(), и только потом будут выполняться команды, указанные в методе main()в строках, записанных после строки с вызовом a().

Вся иерархия вызовов хранится в специальной области памяти, называемой стеком вызовов. Элементы в этот участок памяти добавляются по принципу LIFO: последний добавленный элемент должен быть извлечён первым. Когда метод вызывает сам себя, новым локальным переменным и параметрам выделяется место в стеке и код метода выполняется с этими новыми начальными значениями. При каждом возврате из рекурсивного вызова старые локальные переменные и параметры удаляются из стека, и выполнение продолжается с момента вызова внутри метода.

 

 

Рекурсия без ветвления

 

Напишем рекурсивную программу, вычисляющую факториал введенного натурального числа. Напомним, что факториал n! целого неотрицательного числа n задается следующим рекуррентным соотношением:

0! = 1,

n! = n · (n − 1)! для n > 0.

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

import java.util.Scanner;

class FactR {

static long fact(int n) {

return (n == 0)?1:n*fact(n-1);

}

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

System.out.println("Введите n:");

System.out.printf("n!=%d",fact(scan.nextInt()));

}

}

В приведенной программе метод fact() получает на вход целое число n и рекурсивно вычисляет его факториал. Рассмотрим процесс выполнения данной программы для n=3 более подробно (рис.6.1).

Так как число 3 отлично от нуля, метод попытается умножить число 3 на fact(2), но последняя величина для ее вычисления требует вызова метода fact() с аргументом 2. В результате чего выполнение метода fact() с аргументом 3 приостановится, и программа приступит к выполнению этого же метода с меньшим на единицу значением аргумента. Вычисление fact(2) потребует нахождения fact(1), что вызовет появление еще одного – третьего экземпляра метода fact(). Он, в свою очередь, вызовет fact(0). К этому моменту стек вызовов метода накопит уже четыре вызова экземпляров метода с разными аргументами. При этом вычисления во всех вызванных ранее экземплярах метода приостановлены до завершения работы с последним.

Метод fact(), вызванный с нулевым аргументом, самостоятельно вычислит и вернет с помощью оператора return результат – число 1. Верхний элемент из стека вызовов методов после этого удалится, и возобновятся вычисления величины fact(1). Этот процесс продолжится до тех пор, пока стек вызовов не станет пустым, что произойдет по завершению вычисления значения fact(3). В итоге в метод main()будет возвращено значение 6. Описанный процесс хорошо иллюстрирует диаграмма, представленная на рис. 5.1. На ней наглядно видно, что при выполнении рекурсивного метода сначала происходит так называемое «рекурсивное погружение», а затем «возврат вычисленных результатов».

 

Рис.6.1 – Диаграмма стека вызовов рекурсивного метода fact(3)

 

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

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

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

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

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

Объяснение: напишем рекурсивный метод. Условием завершения рекурсивного метода будет условие ввода отрицательного числа. Диаграмма вызовов рекурсивного метода revers() при вводе последовательности из трех положительных чисел приведена на рис. 6.2. При рекурсивном вызове переменные вызывающего метода остаются в памяти и их значения становятся доступными после завершения рекурсивного вызова. Поэтому если в теле метода после строки с рекурсивным вызовом записать строку с оператором вывода на экран, то введенные значения будут выведены в обратном порядке.

 

 

Рис.6.2 – Диаграмма вызовов рекурсивного метода revers()

import java.util.Scanner;

class Ex_6_1

{

static void revers(){

int a = new Scanner(System.in).nextInt();

if (a<0) return;

revers();

System.out.printf("%d ",a);

}

public static void main (String[] args)

{revers();}

}

Результат:

-5

12 9 8 6 4

 

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

return (n==0)?1:n*fact(n-1);

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