Java Language
Rekursion

Introduktion

Anmärkningar

Grundidén med rekursion

Vad är rekursion:

I allmänhet är rekursion när en funktion åberopar sig själv, antingen direkt eller indirekt. Till exempel:

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

Villkor för att tillämpa rekursion på ett problem:

Det finns två förutsättningar för att använda rekursiva funktioner för att lösa ett specifikt problem:

1. Det måste finnas ett grundvillkor för problemet, vilket kommer att vara slutpunkten för rekursionen. När en rekursiv funktion når basvillkoret gör den inga ytterligare (djupare) rekursiva samtal.

2. Varje rekursionsnivå bör försöka ett mindre problem. Den rekursiva funktionen delar således problemet upp i mindre och mindre delar. Om man antar att problemet är begränsat kommer detta att säkerställa att rekursionen upphör.

I Java finns det en tredje förutsättning: det borde inte vara nödvändigt att rekrytera för djupt för att lösa problemet; se Djup rekursion är problematisk i Java

Exempel

Följande funktion beräknar factorials med hjälp av rekursion. Lägg märke till hur factorial kallar sig inom funktionen. Varje gång den ringer sig reducerar den parametern n med 1. När n når 1 (basvillkoret) kommer funktionen inte att återgå till djupare.

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

^{Detta är inte ett praktiskt sätt att beräkna factorials i Java, eftersom det inte tar hänsyn till heltalöverskridande, eller anropar stacköverskridning (dvs. undantag från StackOverflowError ) för stora värden på n .}

Beräkna Nth Fibonacci-nummer

Följande metod beräknar Nth Fibonacci-nummer med hjälp av rekursion.

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

Metoden implementerar ett basfall (n <= 2) och ett rekursivt fall (n> 2). Detta illustrerar användningen av rekursion för att beräkna en rekursiv relation.

Men medan detta exempel är illustrativt, är det också ineffektivt: varje enskilt fall av metoden kommer att kalla själva funktionen två gånger, vilket leder till en exponentiell tillväxt i antalet gånger funktionen kallas när N ökar. Ovanstående funktion är O (2 ^N ), men en ekvivalent iterativ lösning har komplexitet O (N). Dessutom finns det ett "sluten form" -uttryck som kan utvärderas i O (N) flytande punktmultiplikationer.

Beräkna summan av heltal från 1 till N

Följande metod beräknar summan av heltal från 0 till N med hjälp av rekursion.

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

Denna metod är O (N) och kan reduceras till en enkel slinga med optimering av svarssamtal. I själva verket finns det ett slutet formuttryck som beräknar summan i O(1) -operationer.

Beräkna ett N: s effekt

Följande metod beräknar värdet av num höjs till exp med rekursion:

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

Detta illustrerar principerna som nämns ovan: den rekursiva metoden implementerar ett basfall (två fall, n = 0 och n = 1) som avslutar rekursionen, och ett rekursivt fall som kallar metoden igen. Denna metod är O (N) och kan reduceras till en enkel slinga med optimering av svarssamtal.

Omvänd en sträng med hjälp av rekursion

Nedan är en rekursiv kod för att vända en sträng

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

Korsa en träddatastruktur med rekursion

Tänk på Node-klassen som har 3 medlemmars data, vänster barnpekare och höger barnpekare som nedan.

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

Vi kan korsa trädet konstruerat genom att ansluta flera Node klassens objekt som nedan kallas traversalen i ordning traversal av träd.

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

Som visas ovan kan vi genom rekursion gå igenom träddatastrukturen utan att använda någon annan datastruktur som inte är möjlig med den iterativa metoden.

Typer av rekursion

Rekursion kan kategoriseras som antingen huvudrekursion eller svansrekursion , beroende på var det rekursiva metodsamtalet är placerat.

Vid huvudrekursion kommer det rekursiva samtalet, när det händer, före annan bearbetning i funktionen (tänk på att det sker längst upp, eller huvudet, för funktionen).

I svansrekursion är det motsatt - behandlingen sker före det rekursiva samtalet. Att välja mellan de två rekursiva stilarna kan verka godtyckligt, men valet kan göra hela skillnaden.

En funktion med en sökväg med ett enda rekursivt samtal i början av banan använder det som kallas huvudrekursion. Den faktiska funktionen för en tidigare utställning använder huvudrekursion. Det första det gör när det bestämmer att rekursion behövs är att kalla sig själv med den dekrementerade parametern. En funktion med ett enda rekursivt samtal i slutet av en väg använder svansrekursion.

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

Om det rekursiva samtalet sker i slutet av en metod, kallas det en tail recursion . Rekursionen av svansen similar to a loop . method executes all the statements before jumping into the next recursive call .

Om det rekursiva samtalet inträffar i beginning of a method, it is called a head recursion . method saves the state before jumping into the next recursive call .

Referens: Skillnaden mellan rekursion av huvud och svans

StackOverflowError & rekursion till loop

Om ett rekursivt samtal går "för djupt", resulterar detta i en StackOverflowError . Java tilldelar en ny ram för varje metodsamtal i trådens stack. Emellertid är utrymmet för varje trådbunt begränsat. För många ramar på stacken leder till Stack Overflow (SO).

Exempel

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

Att ringa denna metod med stora parametrar (t.ex. recursion(50000) kommer förmodligen att resultera i ett överflöde av stacken. Det exakta värdet beror på trådstapelstorleken, som i sin tur beror på trådkonstruktionen, kommandoradsparametrar som -Xss eller standardstorlek för JVM.

Jobba runt

En rekursion kan konverteras till en slinga genom att lagra data för varje rekursivt samtal i en datastruktur. Denna datastruktur kan lagras på högen snarare än på trådbunten.

I allmänhet kan de data som krävs för att återställa tillståndet för en metodinokallering lagras i en bunt och en stundslinga kan användas för att "simulera" de rekursiva samtalen. Uppgifter som kan krävas inkluderar:

• objektet som metoden krävdes (endast instansmetoder)
• metodparametrarna
• lokala variabler
• den aktuella positionen i utförandet eller metoden

Exempel

Följande klass tillåter rekursiv utskrift av en trädstruktur upp till ett specificerat djup.

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

}

t.ex

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

Grafik

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

Detta kan konverteras till följande slinga:

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

Obs: Detta är bara ett exempel på den allmänna strategin. Ofta kan du hitta ett mycket bättre sätt att representera en ram och / eller lagra ramdata.

Djup rekursion är problematisk i Java

Tänk på följande naiva metod för att lägga till två positiva siffror med rekursion:

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

Detta är algoritmiskt korrekt, men det har ett stort problem. Om du ringer add med ett stort a , kommer det att krascha med en StackOverflowError på alla versioner av Java upp till (åtminstone) Java 9.

På ett typiskt funktionellt programmeringsspråk (och många andra språk) optimerar kompilatorn svansrekursion . Kompilatorn märker att samtalet att add (vid den taggade linjen) är ett svanssamtal och skulle effektivt skriva om rekursionen som en slinga. Denna omvandling kallas eliminering av svåranrop.

Men nuvarande generation Java-kompilatorer utför inte eliminering av svanssamtal. (Detta är inte en enkel övervakning. Det finns väsentliga tekniska skäl för detta; se nedan.) Istället orsakar varje rekursivt samtal om add en ny ram tilldelas på trådens stack. Om du till exempel ringer add(1000, 1) tar det 1000 rekursiva samtal för att komma fram till svaret 1001 .

Problemet är att storleken på Java-trådstacken fixas när tråden skapas. (Detta inkluderar "huvud" -tråden i ett en-gängat program.) Om för många stapelramar tilldelas, kommer stacken att flyta över. JVM kommer att upptäcka detta och kasta en StackOverflowError .

En metod för att hantera detta är att helt enkelt använda en större stack. Det finns JVM-alternativ som styr standardstorleken för en stack, och du kan också ange stackstorleken som en Thread . Tyvärr "släpper" detta bara över stacken. Om du behöver göra en beräkning som kräver en ännu större stack, kommer StackOverflowError tillbaka.

Den verkliga lösningen är att identifiera rekursiva algoritmer där djup rekursion är troligt och manuellt utföra optimering av svarssamtal på källkodnivå. Till exempel kan vår add skrivas om enligt följande:

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

(Det finns naturligtvis bättre sätt att lägga till två heltal. Ovanstående är helt enkelt att illustrera effekten av manuell eliminering av svanssamtal.)

Varför eliminering av svåranrop inte implementeras i Java (ännu)

Det finns flera orsaker till att det inte är lätt att lägga till eliminering av halssamtal till Java. Till exempel:

• En del kod kan förlita sig på StackOverflowError att (till exempel) placera en gräns på storleken på ett beräkningsproblem.
• Sandbox-säkerhetschefer litar ofta på att analysera samtalstacken när de beslutar om de vill tillåta icke-privilegierad kod att utföra en privilegierad åtgärd.

Som John Rose förklarar i "Tail call in the VM" :

"Effekterna av att ta bort anroparens stackram är synliga för vissa API: er, särskilt åtkomstkontrollkontroller och stapelspårning. Det är som om den som ringer den som ringer direkt hade ringt callee. Alla privilegier som den som ringer besegras efter att kontrollen har överförts till callee. Kopplingen och tillgängligheten för callee-metoden beräknas emellertid före överföringen av kontrollen och tar hänsyn till den svansuppringande samtalaren. "

Med andra ord, eliminering av svanssamtal kan orsaka att en åtkomstkontrollmetod felaktigt tror att ett säkerhetskänsligt API kallades av betrodd kod.