Java Language
Рекурсия

Вступление

замечания

Основная идея рекурсии

Что такое рекурсия:

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

// This method calls itself "infinitely"
public void useless() {
    useless();  // method calls itself (directly)
}

Условия применения рекурсии к задаче:

Существуют две предпосылки для использования рекурсивных функций для решения конкретной проблемы:

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

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

В Java есть третье предварительное условие: не нужно слишком глубоко задумываться о решении проблемы; см. Глубокая рекурсия проблематична в Java

пример

Следующая функция вычисляет факториалы с использованием рекурсии. Обратите внимание, как метод factorial вызывает себя внутри функции. Каждый раз, когда он называет себя, он уменьшает параметр n на 1. Когда n достигает 1 (базовое условие), функция не будет углубляться.

public int factorial(int n) {
    if (n <= 1) { // the base condition 
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

^{Это не практический способ вычисления факториалов в Java, поскольку он не учитывает переполнение целого числа или переполнение стека вызовов (например, исключения StackOverflowError ) при больших значениях n .}

Вычисление N-го числа Фибоначчи

Следующий метод вычисляет N-й номер Фибоначчи с использованием рекурсии.

public int fib(final int n) {
    if (n > 2) {
        return fib(n - 2) + fib(n - 1);
    }
    return 1;
}

Метод реализует базовый случай (n <= 2) и рекурсивный случай (n> 2). Это иллюстрирует использование рекурсии для вычисления рекурсивного отношения.

Однако, хотя этот пример является иллюстративным, он также неэффективен: каждый отдельный экземпляр метода дважды вызовет эту функцию, что приведет к экспоненциальному росту числа раз, когда функция называется ростом N. Вышеуказанная функция O (2 ^N ), но эквивалентное итерационное решение имеет сложность O (N). Кроме того, существует выражение «закрытая форма», которое может быть оценено с помощью умножения с плавающей запятой O (N).

Вычисление суммы целых чисел от 1 до N

Следующий метод вычисляет сумму целых чисел от 0 до N, используя рекурсию.

public int sum(final int n) {
    if (n > 0) {
        return n + sum(n - 1);
    } else {
        return n;
    }
}

Этот метод O (N) и может быть сведен к простому циклу с использованием оптимизации хвостового вызова. На самом деле существует замкнутое выражение формы, которое вычисляет сумму в операциях O(1) .

Вычисление N-й степени числа

Следующий метод вычисляет значение num увеличенное до степени exp используя рекурсию:

public long power(final int num, final int exp) {
    if (exp == 0) {
        return 1;
    }
    if (exp == 1) {
        return num;
    }
    return num * power(num, exp - 1);
}

Это иллюстрирует принципы, упомянутые выше: рекурсивный метод реализует базовый случай (два случая, n = 0 и n = 1), который завершает рекурсию, и рекурсивный случай, который вызывает метод снова. Этот метод O (N) и может быть сведен к простому циклу с использованием оптимизации хвостового вызова.

Обратить строку с помощью рекурсии

Ниже приведен рекурсивный код для изменения строки

/**
 * Just a snippet to explain the idea of recursion
 *
 **/

public class Reverse {
    public static void main (String args[]) {
        String string = "hello world";
        System.out.println(reverse(string)); //prints dlrow olleh
    }

    public static String reverse(String s) {
        if (s.length() == 1) {
            return s;
        }
    
        return reverse(s.substring(1)) + s.charAt(0);
    }
}

Перемещение структуры данных дерева с рекурсией

Рассмотрим класс Node, содержащий 3 элемента данных, левый указатель на ребенка и правый дочерний указатель, как показано ниже.

public class Node {
    public int data;
    public Node left;
    public Node right;
    
    public Node(int data){
        this.data = data;
    }
}

Мы можем пересечь дерево, построенное путем соединения нескольких объектов класса Node, как показано ниже, обход называется обходным деревом в порядке.

public static void inOrderTraversal(Node root) {
        if (root != null) {          
            inOrderTraversal(root.left); // traverse left sub tree
            System.out.print(root.data + " "); // traverse current node
            inOrderTraversal(root.right); // traverse right sub tree
        }
    }

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

Типы рекурсии

Рекурсия может быть классифицирована как Head Recursion или Tail Recursion , в зависимости от места размещения рекурсивного метода.

При рекурсии головы рекурсивный вызов, когда это происходит, предшествует другой обработке в функции (думайте, что это происходит сверху или в голове функции).

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

Функция с путём с единственным рекурсивным вызовом в начале пути использует так называемую рекурсию головы. Факториальная функция предыдущего экспоната использует рекурсию головы. Первое, что он делает, когда оно определяет, что требуется рекурсия, - это вызвать себя с декрементированным параметром. Функция с единственным рекурсивным вызовом в конце пути использует хвостовую рекурсию.

public void tail(int n)              public void head(int n)
{                                       {
   if(n == 1)                             if(n == 0)
      return;                                return;
   else                                   else
      System.out.println(n);                 head(n-1);

   tail(n-1);                              System.out.println(n);
}                                        }

Если рекурсивный вызов встречается в конце метода, он называется tail recursion . Рекурсия хвоста similar to a loop . method executes all the statements before jumping into the next recursive call .

Если рекурсивный вызов происходит в beginning of a method, it is called a head recursion . method saves the state before jumping into the next recursive call .

Ссылка: Разница между рекурсией головы и хвоста

StackOverflowError & recursion to loop

Если рекурсивный вызов «слишком глубокий», это приводит к возникновению StackOverflowError . Java выделяет новый кадр для каждого вызова метода в стеке потока. Однако пространство стека каждого потока ограничено. Слишком много кадров в стеке приводит к переполнению стека (SO).

пример

public static void recursion(int depth) {
    if (depth > 0) {
        recursion(depth-1);
    }
}

Вызов этого метода с большими параметрами (например, recursion(50000) вероятно, приведет к переполнению стека. Точное значение зависит от размера стека потоков, что, в свою очередь, зависит от конструкции потока, параметров командной строки, таких как -Xss или размер по умолчанию для JVM.

Временное решение

Рекурсия может быть преобразована в цикл путем хранения данных для каждого рекурсивного вызова в структуре данных. Эта структура данных может храниться в куче, а не в стеке потоков.

В общем случае данные, необходимые для восстановления состояния вызова метода, могут храниться в стеке, а цикл while может использоваться для «имитации» рекурсивных вызовов. Данные, которые могут потребоваться, включают:

• объект, к которому был вызван метод (только методы экземпляра)
• параметры метода
• локальные переменные
• текущая позиция в исполнении или метод

пример

Следующий класс позволяет рекурсивно печатать древовидную структуру с заданной глубиной.

public class Node {

    public int data;
    public Node left;
    public Node right;

    public Node(int data) {
        this(data, null, null);
    }

    public Node(int data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public void print(final int maxDepth) {
        if (maxDepth <= 0) {
            System.out.print("(...)");
        } else {
            System.out.print("(");
            if (left != null) {
                left.print(maxDepth-1);
            }
            System.out.print(data);
            if (right != null) {
                right.print(maxDepth-1);
            }
            System.out.print(")");
        }
    }

}

например

Node n = new Node(10, new Node(20, new Node(50), new Node(1)), new Node(30, new Node(42), null));
n.print(2);
System.out.println();

Печать

(((...)20(...))10((...)30))

Это можно преобразовать в следующий цикл:

public class Frame {

    public final Node node;

    // 0: before printing anything
    // 1: before printing data
    // 2: before printing ")"
    public int state = 0;
    public final int maxDepth;

    public Frame(Node node, int maxDepth) {
        this.node = node;
        this.maxDepth = maxDepth;
    }

}

List<Frame> stack = new ArrayList<>();
stack.add(new Frame(n, 2)); // first frame = initial call

while (!stack.isEmpty()) {
    // get topmost stack element
    int index = stack.size() - 1;
    Frame frame = stack.get(index); // get topmost frame
    if (frame.maxDepth <= 0) {
        // termial case (too deep)
        System.out.print("(...)");
        stack.remove(index); // drop frame
    } else {
        switch (frame.state) {
            case 0:
                frame.state++;

                // do everything done before the first recursive call
                System.out.print("(");
                if (frame.node.left != null) {
                    // add new frame (recursive call to left and stop)
                    stack.add(new Frame(frame.node.left, frame.maxDepth - 1));
                    break;
                }
            case 1:
                frame.state++;

                // do everything done before the second recursive call
                System.out.print(frame.node.data);
                if (frame.node.right != null) {
                    // add new frame (recursive call to right and stop)
                    stack.add(new Frame(frame.node.right, frame.maxDepth - 1));
                    break;
                }
            case 2:
                // do everything after the second recursive call & drop frame
                System.out.print(")");
                stack.remove(index);
        }
    }
}
System.out.println();

Примечание. Это всего лишь пример общего подхода. Часто вы можете найти гораздо лучший способ представления кадра и / или хранения данных кадра.

Глубокая рекурсия проблематична в Java

Рассмотрим следующий наивный метод для добавления двух положительных чисел с помощью рекурсии:

public static int add(int a, int b) {
    if (a == 0) {
        return b;
    } else {
        return add(a - 1, b + 1);  // TAIL CALL
    }
}

Это алгоритмически правильно, но это имеет серьезную проблему. Если вы вызовете add с большим a , он выйдет из строя с помощью StackOverflowError на любой версии Java до (по крайней мере) Java 9.

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

Однако компиляторы Java поколения текущего поколения не выполняют исключение хвостового вызова. (Это не простой надзор. Для этого существуют существенные технические причины, см. Ниже.) Вместо этого каждый рекурсивный вызов add вызывает выделение нового кадра в стеке потока. Например, если вы вызываете add(1000, 1) , для ответа 1001 потребуется 1000 рекурсивных вызовов.

Проблема в том, что размер потока потоков Java фиксируется при создании потока. (Сюда входит «основной» поток в однопоточной программе.) Если слишком много кадров стека распределены, стек будет переполняться. JVM обнаружит это и выбросит StackOverflowError .

Один из способов борьбы с этим - просто использовать больший стек. Есть JVM варианты , которые контролируют по умолчанию размера стека, и вы можете также указать размер стека в качестве Thread параметра конструктора. К сожалению, это только «отбрасывает» переполнение стека. Если вам нужно выполнить вычисления, для которых требуется еще больший стек, возвращается StackOverflowError .

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

public static int add(int a, int b) {
    while (a != 0) {
       a = a - 1;
       b = b + 1;
    }
    return b;
}

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

Почему исключение хвостового вызова не реализовано на Java (пока)

Существует ряд причин, по которым добавление исключения хвоста в Java нелегко. Например:

• Некоторый код может полагаться на StackOverflowError для (например) размещения привязки по размеру вычислительной проблемы.
• Менеджеры безопасности Sandbox часто полагаются на анализ стека вызовов при принятии решения о том, разрешать ли непривилегированный код выполнять привилегированное действие.

Как объясняет Джон Роуз в «Хвостах звонков на ВМ» :

«Эффекты удаления фрейма стека вызывающего абонента видны некоторым API-интерфейсам, особенно проверкам контроля доступа и трассировке стека. Как будто вызывающий вызывающий вызывал непосредственно вызываемый вызывающий. Любые привилегии, которыми обладает вызывающий, отбрасываются после того, как управление передано в Однако связь и доступность метода вызываемого метода вычисляются до передачи управления и учитывают вызывающего звонка вызывающего абонента ».

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