Java Language
Herhaling

Invoering

Opmerkingen

Het basisidee van recursie

Wat is recursie:

In het algemeen is recursie wanneer een functie zichzelf oproept, direct of indirect. Bijvoorbeeld:

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

Voorwaarden voor het toepassen van recursie op een probleem:

Er zijn twee voorwaarden voor het gebruik van recursieve functies om een specifiek probleem op te lossen:

1. Er moet een basisvoorwaarde voor het probleem zijn, die het eindpunt voor de recursie zal zijn. Wanneer een recursieve functie de basisconditie bereikt, voert deze geen verdere (diepere) recursieve oproepen uit.

2. Elk recursieniveau zou een kleiner probleem moeten uitproberen. De recursieve functie verdeelt het probleem dus in kleinere en kleinere delen. Ervan uitgaande dat het probleem eindig is, zorgt dit ervoor dat de recursie wordt beëindigd.

In Java is er een derde voorwaarde: het zou niet nodig moeten zijn om te diep te gaan om het probleem op te lossen; zie Diepe recursie is problematisch in Java

Voorbeeld

De volgende functie berekent faculteiten met behulp van recursie. Merk op hoe de methode factorial zich binnen de functie noemt. Telkens wanneer het zichzelf oproept, verlaagt het de parameter n met 1. Wanneer n 1 bereikt (de basisconditie), zal de functie niet dieper recidiveren.

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

^{Dit is geen praktische manier om faculteiten in Java te berekenen, omdat het geen rekening houdt met integer overflow, of call stack overflow (dwz StackOverflowError uitzonderingen) voor grote waarden van n .}

Berekening van het Nde Fibonacci-nummer

De volgende methode berekent het Nth Fibonacci-nummer met behulp van recursie.

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

De methode implementeert een basisscenario (n <= 2) en een recursief geval (n> 2). Dit illustreert het gebruik van recursie om een recursieve relatie te berekenen.

Hoewel dit voorbeeld illustratief is, is het echter ook inefficiënt: elke afzonderlijke instantie van de methode roept de functie zelf twee keer aan, wat leidt tot een exponentiële groei van het aantal keren dat de functie wordt aangeroepen als N toeneemt. De bovenstaande functie is O (2 ^N ), maar een equivalente iteratieve oplossing heeft complexiteit O (N). Bovendien is er een uitdrukking "gesloten vorm" die kan worden geëvalueerd in O (N) drijvende-komma-vermenigvuldigingen.

De som van gehele getallen berekenen van 1 tot N

De volgende methode berekent de som van gehele getallen van 0 tot N met behulp van recursie.

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

Deze methode is O (N) en kan worden gereduceerd tot een eenvoudige lus met behulp van tail-call-optimalisatie. In feite is er een expressie in gesloten vorm die de som in O(1) -bewerkingen berekent.

De Nde macht van een getal berekenen

De volgende methode berekent de waarde van num verhoogd tot de kracht van exp met behulp van recursie:

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

Dit illustreert de hierboven genoemde principes: de recursieve methode implementeert een basisscenario (twee gevallen, n = 0 en n = 1) die de recursie beëindigt, en een recursief geval dat de methode opnieuw aanroept. Deze methode is O (N) en kan worden gereduceerd tot een eenvoudige lus met behulp van tail-call-optimalisatie.

Een string omkeren met behulp van recursie

Hieronder staat een recursieve code om een string om te keren

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

Een boomgegevensstructuur doorlopen met recursie

Beschouw de Node-klasse met 3 ledengegevens, linker kinderwijzer en rechter kinderwijzer zoals hieronder.

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

We kunnen de boom doorkruisen die is geconstrueerd door het object van meerdere Node-klassen te verbinden, zoals hieronder, de verplaatsing wordt in volgorde volgorde van boom genoemd.

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

Zoals hierboven aangetoond, met behulp van recursie kunnen we de boom datastructuur doorkruisen zonder het gebruik van andere gegevens structuur die niet mogelijk is met de iteratieve aanpak.

Soorten recursie

Recursie kan worden gecategoriseerd als Head Recursion of Tail Recursion , afhankelijk van waar de recursieve methodeaanroep wordt geplaatst.

In head recursion komt de recursieve aanroep, wanneer het gebeurt, voor andere verwerking in de functie (denk aan het gebeuren aan de bovenkant, of head, van de functie).

Bij staartrecursie is het tegenovergestelde: de verwerking vindt plaats vóór de recursieve aanroep. Kiezen tussen de twee recursieve stijlen lijkt misschien willekeurig, maar de keuze kan het verschil maken.

Een functie met een pad met een enkele recursieve aanroep aan het begin van het pad maakt gebruik van de zogenaamde head recursion. De facultaire functie van een vorige tentoonstelling maakt gebruik van hoofdrecursie. Het eerste wat het doet als het eenmaal heeft vastgesteld dat recursie nodig is, is zichzelf aanroepen met de verlaagde parameter. Een functie met een enkele recursieve aanroep aan het einde van een pad gebruikt staartrecursie.

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

Als de recursieve aanroep plaatsvindt aan het einde van een methode, wordt deze een tail recursion . De staartrecursie is similar to a loop . De method executes all the statements before jumping into the next recursive call .

Als de recursieve aanroep plaatsvindt aan het beginning of a method, it is called a head recursion . De method saves the state before jumping into the next recursive call .

Referentie: het verschil tussen kop- en staartrecursie

StackOverflowError & recursion to loop

Als een recursieve aanroep "te diep" gaat, resulteert dit in een StackOverflowError . Java wijst een nieuw frame toe voor elke methodeaanroep in de stapel van de thread. De ruimte in de stapel van elke thread is echter beperkt. Te veel frames op de stapel leidt tot de Stack Overflow (SO).

Voorbeeld

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

Het aanroepen van deze methode met grote parameters (bijv. recursion(50000) zal waarschijnlijk resulteren in een stapeloverloop. De exacte waarde is afhankelijk van de -Xss , die op zijn beurt afhankelijk is van de draadconstructie, opdrachtregelparameters zoals -Xss of de standaardgrootte voor de JVM.

tijdelijke oplossing

Een recursie kan worden omgezet in een lus door de gegevens voor elke recursieve oproep in een gegevensstructuur op te slaan. Deze gegevensstructuur kan op de heap worden opgeslagen in plaats van op de thread-stack.

Over het algemeen kunnen de gegevens die nodig zijn om de status van een aanroep van een methode te herstellen, in een stapel worden opgeslagen en kan een while-lus worden gebruikt om de recursieve oproepen te "simuleren". Gegevens die nodig kunnen zijn, zijn onder meer:

• het object waarvoor de methode werd gebruikt (alleen instantiemethoden)
• de methode parameters
• lokale variabelen
• de huidige positie in de uitvoering of de methode

Voorbeeld

De volgende klasse maakt het recursief afdrukken van een boomstructuur tot een opgegeven diepte mogelijk.

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

}

bv

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

prints

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

Dit kan worden omgezet in de volgende lus:

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

Opmerking: dit is slechts een voorbeeld van de algemene aanpak. Vaak kun je een veel betere manier bedenken om een frame weer te geven en / of de framegegevens op te slaan.

Diepe recursie is problematisch in Java

Overweeg de volgende naïeve methode voor het toevoegen van twee positieve getallen met behulp van recursie:

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

Dit is algoritmisch correct, maar het heeft een groot probleem. Als je add met een grote a StackOverflowError , crasht het met een StackOverflowError , op elke versie van Java tot (tenminste) Java 9.

In een typische functionele programmeertaal (en vele andere talen) optimaliseert de compiler staartrecursie . De compiler zou opmerken dat de aanroep die moet worden add (op de getagde regel) een staartoproep is en zou de recursie effectief herschrijven als een lus. Deze transformatie wordt tail-call eliminatie genoemd.

Huidige Java-compilers van de generatie voeren echter geen staartoproep eliminatie uit. (Dit is geen eenvoudig overzicht. Er zijn substantiële technische redenen hiervoor; zie hieronder.) In plaats daarvan zorgt elke recursieve aanroep van add ervoor dat een nieuw frame wordt toegewezen aan de stapel van de thread. Als u bijvoorbeeld add(1000, 1) aanroept, zijn er 1000 recursieve oproepen nodig om tot het antwoord 1001 .

Het probleem is dat de grootte van de Java-threadstack is vastgesteld wanneer de thread wordt gemaakt. (Dit omvat de "hoofdthread" in een programma met één thread.) Als er te veel stapelframes zijn toegewezen, loopt de stapel over. De JVM zal dit detecteren en een StackOverflowError gooien.

Een manier om hiermee om te gaan is om gewoon een grotere stapel te gebruiken. Er zijn JVM opties die de standaard grootte van een stack te controleren, en u kunt ook de stack grootte als een opgeven Thread aannemer parameter. Helaas "schakelt" dit alleen de overloop van de stapel uit. Als u een berekening moet uitvoeren die een nog grotere stapel vereist, dan komt de StackOverflowError terug.

De echte oplossing is om recursieve algoritmen te identificeren waar diepe recursie waarschijnlijk is, en de tail-call-optimalisatie handmatig uit te voeren op broncodeniveau. Onze add methode kan bijvoorbeeld als volgt worden herschreven:

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

(Uiteraard zijn er betere manieren om twee gehele getallen toe te voegen. Het bovenstaande is alleen om het effect van handmatige staartverwijdering te illustreren.)

Waarom tail-call eliminatie (nog) niet is geïmplementeerd in Java

Er zijn een aantal redenen waarom het toevoegen van tail call-eliminatie aan Java niet eenvoudig is. Bijvoorbeeld:

• Sommige code kan op StackOverflowError vertrouwen om (bijvoorbeeld) een limiet te stellen aan de omvang van een rekenprobleem.
• Sandbox-beveiligingsmanagers vertrouwen vaak op het analyseren van de call-stack bij het beslissen of niet-geprivilegieerde code een geprivilegieerde actie mag uitvoeren.

Zoals John Rose uitlegt in "Tail calls in the VM" :

"De effecten van het verwijderen van het stapelframe van de beller zijn zichtbaar voor sommige API's, met name toegangscontrolecontroles en stack-tracing. Het is alsof de beller van de beller rechtstreeks de oproep heeft gebeld. Alle rechten die de beller bezit, worden genegeerd nadat de controle is overgedragen aan de callee. De koppeling en toegankelijkheid van de callee-methode worden echter berekend voordat de controle wordt overgedragen en houdt rekening met de beller die de oproep doet. "

Met andere woorden, het elimineren van staartoproepen kan ertoe leiden dat een toegangscontrolemethode ten onrechte denkt dat een beveiligingsgevoelige API door vertrouwde code wordt aangeroepen.