Vorlesung Informatik 2 - Teil A: Java Kurs
2.2 Rekursion in Java
Rekursion ist ein Konzept der Mathematik, Beispiel:
/ 0 für x=0 f(x) = - \ f(x-1) + x2
Wir verwenden also eine Funktion bei ihrer eigenen Definition. Streng genommen verwenden wir Instanzen der Funktion:
- f(0) wird fest als 0 definiert,
- zur Definition von f(1) wird f(0) verwendet, u.s.w.
Viele Programmiersprachen, auch Java, erlauben Rekursion, d.h. dass eine Methode sich selbst ruft:
int f(int x){
if(x<=0) return 0;
else return 2*f(x-1)+x*x;
} public static void main(String[] a){ y=f(3); }
Bei der Verarbeitung von f(2) wird zunächst f(1) gerufen, dann f(0). Im System-Stack befinden sich zu diesem Zeitpunkt also 3 Instanzen der Methode f:
|-----------| | f: | | x(0) | |-----------| | f: | | x(1) | |-----------| | f: | | x(2) | |-----------| | main: | | args,y | |-----------| /////////////
Beispiel: Fakultät einer Zahl
In Java:
static long fakultaet(long n){ if(x<=1) return 1; else return n*fakultaet(n-1); }
Der Datentyp long ist wichtig, weil die n! schell sehr groß wird - probieren Sie es aus.
Jede Rekursion kann auch als Schleife geschrieben werden:
static long fakultaet(long n){ long f=1; while(n>0) f*=n--; return f; }
Die Schleife ist in diesem Fall natürlich effizienter als die rekursive Variante, weil der System-Stack nicht benötigt wird. In vielen Fällen ist die Rekursion aber eleganter und kürzer, besonders wenn wir später rekursive Datenstrukturen verwenden.