В языке Java поддерживается рекурсия — процесс определения чего-либо относительно самого себя.
Применительно к программированию на Java рекурсия — это средство, которое позволяет методу вызывать самого себя. Такой метод называется рекурсивным.
Классическим примером рекурсии служит вычисление факториала числа. Факториал числа N — это произведение всех целых чисел от 1 до N. Например ,факториал числа 3 равен 1 х 2 х 3, т.е. 6. Ниже показано, как вычислить факториал, используя рекурсивный метод.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// Простой пример рекурсии Java class Factorial { // это рекурсивный метод int fact(int n) { int result; if(n == 1) return 1; result = fact(n - 1) * n; return result; } } class Recursion { public static void main(String args[]) { Factorial fact = new Factorial(); System.out.println("Факториал 5 равен " + fact.fact(5)); System.out.println("Факториал 10 равен " + fact.fact(10)); System.out.println("Факториал 12 равен " + fact.fact(12)); System.out.println("Факториал 15 равен " + fact.fact(15)); } } |
Ниже приведен результат, выводимый этой программой.
|
1 2 3 4 5 6 7 |
pro-java.ru@admin:~$ javac recursion.java pro-java.ru@admin:~$ java Recursion Факториал 5 равен 120 Факториал 10 равен 3628800 Факториал 12 равен 479001600 Факториал 15 равен 2004310016 pro-java.ru@admin:~$ |
Тем, кто незнаком с рекурсивными методами, принцип действия метода 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
// Второй пример рекурсии в Java class RecursionExample { int values[]; RecursionExample(int i) { values = new int[i]; } // вывести рекурсивно элементы массива void printArray(int i) { if(i == 0) { return; } else { printArray(i - 1); System.out.println("[" + (i - 1) + "] " + values[i - 1]); } } } class RecursionMain { private static final int num = 23; public static void main(String[] args) { RecursionExample rec = new RecursionExample(num); int j; for(j = 0; j < num; j++) { rec.values[j] = j; } rec.printArray(num); } } |
Эта программа выводит следующий результат:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
pro-java.ru@admin:~$ javac recursion2.java pro-java.ru@admin:~$ java RecursionMain [0] 0 [1] 1 [2] 2 [3] 3 [4] 4 [5] 5 [6] 6 [7] 7 [8] 8 [9] 9 [10] 10 [11] 11 [12] 12 [13] 13 [14] 14 [15] 15 [16] 16 [17] 17 [18] 18 [19] 19 [20] 20 [21] 21 [22] 22 pro-java.ru@admin:~$ |
Попробуйте написать следующую строку кода выше рекурсивного вызова:
|
1 2 3 |
... System.out.println("[" + (i - 1) + "] " + values[i - 1]); ... |
Должно получатся следующим образом:
|
1 2 3 4 5 6 7 8 |
void printArray(int i) { if(i == 0) { return; } else { System.out.println("[" + (i - 1) + "] " + values[i - 1]); printArray(i - 1); } } |
Что же интересно получаем?
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
pro-java.ru@admin:~$ javac recursion2.java pro-java.ru@admin:~$ java RecursionMain [22] 22 [21] 21 [20] 20 [19] 19 [18] 18 [17] 17 [16] 16 [15] 15 [14] 14 [13] 13 [12] 12 [11] 11 [10] 10 [9] 9 [8] 8 [7] 7 [6] 6 [5] 5 [4] 4 [3] 3 [2] 2 [1] 1 [0] 0 pro-java.ru@admin:~$ |
То есть легко можно заметить как работает рекурсивный метод.
