Bayern Abitur Informatik

## Was Rekursion ist Ein Algorithmus oder eine Methode heißt **rekursiv**, wenn sie sich zur Lösung einer Aufgabe selbst wieder aufruft, und zwar mit einer kleineren oder einfacheren Version derselben Aufgabe. Die Grundidee besteht darin, ein Problem auf ein gleichartiges, aber kleineres Problem zurückzuführen, bis die Lösung so einfach ist, dass sie ohne weiteren Aufruf angegeben werden kann. Jede korrekte rekursive Methode hat zwei Bestandteile. - Die **Abbruchbedingung** (auch Rekursionsanker oder Basisfall) behandelt den einfachsten Fall direkt und ruft die Methode nicht mehr auf. - Der **rekursive Aufruf** löst den übrigen Fall, indem er dieselbe Methode mit einem Argument aufruft, das näher an der Abbruchbedingung liegt. Fehlt die Abbruchbedingung, oder nähert sich das Argument ihr nie an, dann endet die Rekursion nicht. Bei Java führt das nach einiger Zeit zu einem `StackOverflowError`, weil jeder Aufruf Speicherplatz auf dem Aufrufkeller (Stack) belegt und dieser irgendwann voll ist. ## Lineare Rekursion Bei der **linearen Rekursion** führt jeder Aufruf höchstens einen weiteren rekursiven Aufruf aus. Die Aufrufe bilden eine Kette. Das Standardbeispiel ist die Fakultät, $n! = n \cdot (n-1)!$ mit $0! = 1$. ```java public static int fakultaet(int n) { if (n == 0) { return 1; // Abbruchbedingung } return n * fakultaet(n - 1); // rekursiver Aufruf } ``` Für `fakultaet(3)` entsteht zuerst die Aufrufkette, dann wird von innen nach außen zurückgerechnet: $$3! = 3 \cdot 2! =…