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

 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:

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.