Java → Рекурсия

Рекурсия - это когда что-то находится внутри себя или является частью самого себя. 

Например вот:

Рекурсия в Java

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

 

Рекурсия используется когда нужно реализовать повторяющийся алгоритм, следующая итерация которого зависит от предыдущей. Например: вычисления Факториала. Чтобы вычислисть факториал числа 10, мы должны вычислить факториал числа 9 и умножить его на 10. А чтобы вычислить факториал числа 9, мы должны вычислить факториал числа 8 и умножить его на 9. И т.д.  И в конце факториал числа 1 уже можно не вычислять, он равен 1. 

Надо обзятельно предусмотреть конец повторений. В случае факториала, повторения заканчивается, когда мы доходит до 1. Если повторений будет слишком много, то Стек вызовов функций заполнится и программа вылетит. 

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

Создаем класс Recursion, с точкой входа. 

public class Recursion {
    public static void main(String[] args) {
       
    }
}

 Будем использовать этот же класс для реализации нашего алгоритма. 

Создадим метод, который принимает начальное натуральное число и конечное. Этот метод будет печатать сначала начальное число:

public class Recursion {
    public static void main(String[] args) {
       
    }

    private void printNaturalNumbers(int min, int max){
        System.out.println(min);
    }
}

После печати начального числа, мы увелечим это число на 1, чтобы получить следующее натуральное число. И следующее число мы передадим этому же методу как начальное число, чтобы он его распечатал. Ведь он пока печатает только начальное число.

public class Recursion {
    public static void main(String[] args) {

    }

    private void printNaturalNumbers(int min, int max){
        System.out.println(min);
        printNaturalNumbers(min+1, max);
    }
}

Теперь, давайте подумаем как будет работать наш метод, если мы его вызовем так:

printNaturalNumbers(2, 10);

Смотрим на наш код, и видим что он сначала напечатает 2, потом прибавляет к двойке 1 и снова вызывает самого себя с параметрами (2+1, 10) т.е. (3, 10) и соответственно теперь функция запускается еще раз и печатает 3, потом к тройке прибавляет 1 и снова вызывает себя с параметрами (4, 10). и так будет до бесконечности. Метод напечаете все натуральные числа начиная с 2, пока не заполнится стек программы и программа не вылетет с ошибкой  StackOverflowError. 

Когда метод вызывает другой метод внутри, то внешний метод не закончится, пока внутренний метод не завершит свое выполнение. И так же с рекурсией, когда метод вызывает себя, то внешний метод не закончится, пока внутренний метод не завершится. 

Чтобы этот код запустить мы должны создать объект класса Recursion в метода main() и вызвать у него метод printNaturalNumbers(2, 10);

public class Recursion {
    public static void main(String[] args) {
        Recursion recursion = new Recursion();
        recursion.printNaturalNumbers(2, 10);
    }

    private void printNaturalNumbers(int min, int max){
        System.out.println(min);
        printNaturalNumbers(min+1, max);
    }
}

Чтобы метод перестал вызывать самого себя бесконечно, мы должны добавить условие конца. Метод будет вызывать самого себя, пока начальное число(min) меньше конечного(max). Как только начальное число станет равным конечному, вызовы закончатся и все вызванные методы завершатся в обратном порядке.

Добавляем условие:

public class Recursion {
    public static void main(String[] args) {
        Recursion recursion = new Recursion();
        recursion.printNaturalNumbers(2, 10);
    }

    private void printNaturalNumbers(int min, int max){
        System.out.println(min);

        if(min < max){
            printNaturalNumbers(min+1, max);
        }
    }
}

Теперь, при запуске программа напечает все натуральные числа от 2 до 10. 

 

Вот, что такое рекурсия.

522 12
Alisher Alikulov