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.

Lehrvideo  (YouTube)