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

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

В языке Java поддерживается рекурсия  - процесс определения чего-либо отно­сительно самого себя.

Применительно к программированию на Java рекурсия - это средство, которое позволяет методу вызывать самого себя. Такой метод назы­вается рекурсивным.

Классическим примером рекурсии служит вычисление факториала числа. Факториал числа N - это произведение всех целых чисел от 1 до N. Например ,факториал числа 3 равен 1 х 2 х 3, т.е. 6. Ниже показано, как вычислить факториал, используя рекурсивный метод.

//    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));

    }

}

Ниже приведен результат, выводимый этой программой.

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.

//     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);
    }

}

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

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:~$

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

...
System.out.println("[" + (i - 1) + "] " + values[i - 1]);
...

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

void printArray(int i) {
    if(i == 0) {
        return;
    } else {
        System.out.println("[" + (i - 1) + "] " + values[i - 1]);
        printArray(i - 1);
    }
}

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

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:~$

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

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

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

  1. Факториал 15 равен 2004310016
    серьезно?
    типа данных integer в данному случае не хватит

    • Нет, не хватит. Любой объект ограничен памятью. Цифры – нет. При желании можно всю память забить простыми числами.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *