Rekursion

Ein rekursiver Algorithmus oder Programm ist ein Alorithmus/Programm, welches sich selber immer wieder aufruft. Jede Rekursion kann theoretisch durch eine Schleife ersetzt werden und umgekehrt, jedoch ist dies nicht immer ratsam. Schleifen und Rekursionen sind also semmantisch äquivalent. Rekursion kommt vom lateinischen Wort recurrere, was zurücklaufen bedeutet.

Erstes Beispiel für eine Rekursion

?

1 2 3 4 5 6 7 8 9 10 11

public int Beispiel1(int n)  {   if(n == 0)   {        return 1;   }   else     {        return n*Beispiel1(n-1);     }  }

Dieses Beispiel berechnet n Fakultät. Dieses Programm wird nun beispielhaft mit dem Wert n = 3 aufgerufen:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

'''n = 3''' Z. 3 ist ''false'', else-Zweig wird ausgeführt Z. 9 wird ausgeführt: ''3''  *Beispiel(''3''-1)   Das Programm führt nun die Methode für n = 2 aus '''n = 2''' Z. 3 ist ''false'', else-Zweig wird ausgeführt Z. 9 wird ausgeführt: ''2'' * Beispiel(''2''-1)   Das Programm führt nun die Methode für n = 1 aus '''n = 1''' Z. 3 ist nun ''true'' Z. 6 Die Methode Beispiel(1) gibt nun 1 an Beispiel(2) zurück   Beispiel1(2) erhält nun das Ergbnis der Methode Beispiel1(1) und gibt ''2*1'' an die Methode Beispiel1(3) zurück   Beispiel1(3) erhält nun das Ergbnis der Methode Beispiel1(2) und gibt ''3*2*1'' zurück, was ''6'' ist.