Java Language
Rekurencja

Wprowadzenie

Uwagi

Podstawowa idea rekurencji

Co to jest rekurencja:

Zasadniczo rekurencja ma miejsce, gdy funkcja wywołuje się bezpośrednio lub pośrednio. Na przykład:

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

Warunki zastosowania rekurencji do problemu:

Istnieją dwa warunki wstępne użycia funkcji rekurencyjnych do rozwiązania konkretnego problemu:

1. Musi istnieć podstawowy warunek dla problemu, który będzie punktem końcowym rekurencji. Kiedy funkcja rekurencyjna osiągnie warunek podstawowy, nie wykonuje dalszych (głębszych) wywołań rekurencyjnych.

2. Każdy poziom rekurencji powinien podejmować mniejszy problem. Funkcja rekurencyjna dzieli zatem problem na coraz mniejsze części. Zakładając, że problem jest skończony, zapewni to zakończenie rekursji.

W Javie istnieje trzeci warunek wstępny: zbyt głębokie powtórzenie nie powinno być konieczne, aby rozwiązać problem; zobacz Głęboka rekurencja jest problematyczna w Javie

Przykład

Poniższa funkcja oblicza silnię za pomocą rekurencji. Zauważ, jak metoda factorial wywołuje się w funkcji. Za każdym razem, gdy się wywołuje, zmniejsza parametr n o 1. Gdy n osiągnie 1 (warunek podstawowy), funkcja nie powtórzy się głębiej.

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

^{To nie jest praktyczny sposób obliczania silni w Javie, ponieważ nie uwzględnia przepełnienia liczb całkowitych lub przepełnienia stosu wywołań (tj. StackOverflowError ) dla dużych wartości n .}

Obliczanie N-tej liczby Fibonacciego

Poniższa metoda oblicza N-tą liczbę Fibonacciego za pomocą rekurencji.

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

Metoda implementuje przypadek podstawowy (n <= 2) i przypadek rekurencyjny (n> 2). To ilustruje użycie rekurencji do obliczenia relacji rekurencyjnej.

Jednakże, chociaż ten przykład jest ilustracyjny, jest również nieefektywny: każda pojedyncza instancja metody wywoła samą funkcję dwukrotnie, co prowadzi do wykładniczego wzrostu liczby wywołań funkcji wraz ze wzrostem N. Powyższą funkcją jest O (2 ^N ), ale równoważne iteracyjne rozwiązanie ma złożoność O (N). Ponadto istnieje wyrażenie „forma zamknięta”, które można oceniać w mnożnikach zmiennoprzecinkowych O (N).

Obliczanie sumy liczb całkowitych od 1 do N

Poniższa metoda oblicza sumę liczb całkowitych od 0 do N za pomocą rekurencji.

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

Ta metoda to O (N) i można ją zredukować do prostej pętli za pomocą optymalizacji wywołania ogonowego. W rzeczywistości istnieje wyrażenie w formie zamkniętej, które oblicza sumę w operacjach O(1) .

Obliczanie n-tej potęgi liczby

Poniższa metoda oblicza wartość num podniesioną do potęgi exp za pomocą rekurencji:

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

Ilustruje to zasady wspomniane powyżej: metoda rekurencyjna implementuje przypadek podstawowy (dwa przypadki, n = 0 i n = 1), który kończy rekurencję, oraz przypadek rekurencyjny, który ponownie wywołuje metodę. Ta metoda to O (N) i można ją zredukować do prostej pętli za pomocą optymalizacji wywołania ogonowego.

Odwróć ciąg za pomocą rekurencji

Poniżej znajduje się kod rekurencyjny do odwrócenia łańcucha

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

Przemierzanie struktury danych drzewa z rekurencją

Rozważ klasę Node zawierającą 3 elementy danych, lewy wskaźnik potomny i prawy wskaźnik potomny, jak poniżej.

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

Możemy przemierzać drzewo zbudowane przez połączenie wielu obiektów klasy Node, jak poniżej, przejście nazywane jest przejściem drzewa w kolejności.

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
        }
    }

Jak wykazano powyżej, za pomocą rekurencji możemy przechodzić przez strukturę danych drzewa bez użycia jakiejkolwiek innej struktury danych, co nie jest możliwe przy podejściu iteracyjnym .

Rodzaje rekurencji

Rekurencję można zaklasyfikować jako Rekurencję Głowy lub Rekurencję Ogona , w zależności od tego, gdzie znajduje się wywołanie metody rekurencyjnej.

W rekursji głowicy wywołanie rekurencyjne, gdy się zdarza, następuje przed innym przetwarzaniem w funkcji (pomyśl o tym, że dzieje się na górze lub na górze funkcji).

W rekursji ogona jest odwrotnie - przetwarzanie odbywa się przed wywołaniem rekurencyjnym. Wybór między dwoma stylami rekurencyjnymi może wydawać się arbitralny, ale wybór może mieć znaczenie.

Funkcja ze ścieżką z pojedynczym wywołaniem rekurencyjnym na początku ścieżki wykorzystuje tak zwaną rekurencję głowicy. Funkcja silnia z poprzedniego eksponatu wykorzystuje rekurencję głowy. Pierwszą rzeczą, którą robi, gdy stwierdzi, że rekurencja jest potrzebna, jest wywołanie się z obniżonym parametrem. Funkcja z pojedynczym wywołaniem rekurencyjnym na końcu ścieżki używa rekurencji ogona.

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

Jeśli wywołanie rekurencyjne nastąpi na końcu metody, nazywa się to tail recursion . Rekurencja ogona jest similar to a loop . method executes all the statements before jumping into the next recursive call .

Jeśli wywołanie rekurencyjne występuje na beginning of a method, it is called a head recursion . method saves the state before jumping into the next recursive call .

Odniesienie: Różnica między rekurencją głowy i ogona

StackOverflowError & recursion to loop

Jeśli wywołanie rekurencyjne przechodzi „zbyt głęboko”, powoduje to StackOverflowError . Java przydziela nową ramkę dla każdego wywołania metody na stosie swojego wątku. Jednak przestrzeń stosu każdego wątku jest ograniczona. Zbyt wiele ramek na stosie prowadzi do przepełnienia stosu (SO).

Przykład

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

Wywołanie tej metody z dużymi parametrami (np. recursion(50000) prawdopodobnie spowoduje przepełnienie stosu. Dokładna wartość zależy od rozmiaru stosu wątku, co z kolei zależy od budowy wątku, parametrów wiersza poleceń, takich jak -Xss lub domyślny rozmiar JVM.

Obejście

Rekurencję można przekształcić w pętlę, przechowując dane dla każdego wywołania rekurencyjnego w strukturze danych. Ta struktura danych może być przechowywana na stercie, a nie na stosie wątków.

Zasadniczo dane wymagane do przywrócenia stanu wywołania metody mogą być przechowywane na stosie, a pętla while może być użyta do „symulacji” wywołań rekurencyjnych. Dane, które mogą być wymagane, obejmują:

• obiekt, do którego wywołano metodę (tylko metody instancji)
• parametry metody
• zmienne lokalne
• aktualna pozycja w wykonaniu lub metodzie

Przykład

Poniższa klasa pozwala na rekursywne drukowanie struktury drzewa do określonej głębokości.

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(")");
        }
    }

}

na przykład

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

Wydruki

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

Można to przekonwertować na następującą pętlę:

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

Uwaga: to tylko przykład ogólnego podejścia. Często można wymyślić znacznie lepszy sposób reprezentowania ramki i / lub przechowywania danych ramki.

Głęboka rekurencja jest problematyczna w Javie

Rozważ następującą naiwną metodę dodawania dwóch liczb dodatnich za pomocą rekurencji:

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

Jest to poprawne algorytmicznie, ale ma poważny problem. Jeśli wywołasz add z dużym a , spowoduje awarię z StackOverflowError na dowolnej wersji Javy do (przynajmniej) Java 9.

W typowym funkcjonalnym języku programowania (i wielu innych językach) kompilator optymalizuje rekurencję ogona . Kompilator zauważyłby, że wywołanie add (w oznaczonej linii) jest wywołaniem ogonowym i skutecznie przepisałoby rekurencję jako pętlę. Ta transformacja nazywa się eliminacją ogona.

Jednak kompilatory Java obecnej generacji nie wykonują eliminacji wywołania ogonowego. (Nie jest to zwykły nadzór. Są ku temu istotne powody techniczne; patrz poniżej.) Zamiast tego każde rekurencyjne wywołanie add powoduje przydzielenie nowej ramki na stosie wątku. Na przykład, jeśli wywołasz add(1000, 1) , zajmie 1000 rekurencyjnych połączeń, aby dotrzeć do odpowiedzi 1001 .

Problem polega na tym, że rozmiar stosu wątków Java jest ustalany podczas tworzenia wątku. (Obejmuje to „główny” wątek w programie jednowątkowym.) Jeśli przydzielonych zostanie zbyt wiele ramek stosu, stos się przepełni. JVM wykryje to i wyrzuci błąd StackOverflowError .

Jednym ze sposobów radzenia sobie z tym jest po prostu użycie większego stosu. Istnieją opcje JVM, które kontrolują domyślny rozmiar stosu, a także można określić rozmiar stosu jako parametr konstruktora Thread . Niestety, to tylko „odkłada” przepełnienie stosu. Jeśli potrzebujesz wykonać obliczenia, które wymagają jeszcze większego stosu, wówczas wraca StackOverflowError .

Prawdziwym rozwiązaniem jest identyfikacja algorytmów rekurencyjnych, w których prawdopodobna jest głęboka rekurencja, i ręczne wykonanie optymalizacji wywołania ogonowego na poziomie kodu źródłowego. Na przykład naszą metodę add można przepisać w następujący sposób:

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

(Oczywiście są lepsze sposoby dodania dwóch liczb całkowitych. Powyższe ma po prostu zilustrować efekt ręcznej eliminacji ogona.)

Dlaczego eliminacja wywołania ogona nie jest zaimplementowana w Javie (jeszcze)

Istnieje wiele powodów, dla których dodanie eliminacji wywołania ogona do Javy nie jest łatwe. Na przykład:

• Niektóre kody mogą polegać na StackOverflowError celu (na przykład) ograniczenia wielkości problemu obliczeniowego.
• Menedżerowie bezpieczeństwa piaskownicy często polegają na analizie stosu wywołań przy podejmowaniu decyzji, czy zezwolić kodowi nieuprzywilejowanemu na wykonanie uprzywilejowanej akcji.

Jak John Rose wyjaśnia w „Wywołaniach Tail w maszynie wirtualnej” :

„Skutki usunięcia ramki stosu dzwoniącego są widoczne dla niektórych interfejsów API, w szczególności kontrole kontroli dostępu i śledzenie stosu. To tak, jakby dzwoniący dzwonił bezpośrednio do odbiorcy. Wszelkie uprawnienia posiadane przez dzwoniącego są odrzucane po przeniesieniu kontroli na Jednak połączenie i dostępność metody odbierającej są obliczane przed przekazaniem kontroli i uwzględniają dzwoniącego. ”

Innymi słowy, eliminacja wywołania ogonowego może spowodować, że metoda kontroli dostępu błędnie uzna, że wrażliwy na bezpieczeństwo interfejs API został wywołany przez zaufany kod.