Rekursion

Eine Prozedur teilt ein Problem auf indem es sich immer wieder selbstaufruft, bis es zu einer einfachen Lösung kommt. Eine rekursive Berechnung geht von dem zu berechnenden Folgeglied aus und berechnet von dort ausgehend immer weitere Folgeglieder.

Rekursionsschreibweise:

• Basis ist der startpunkt
  • z.B. f(0)=0, f(1)=1
• Rekursionsschritt definiert für alle anderen validen Werte
  • z.B. f(n) = f(n-1) + f(n-2) für n > 1

Rekursive Zahlenfolgen

• Hofstadter Funktion
  • Definitionsmenge: n >= 1
  • Basis: f(1) = 1, f(2) = 2
  • Rekursionsschritt: f(n) = f(n - f(n-1)) + f(n - f(n-2))
• Fibbonachi Folge
  • Definitionsmenge: n >= 0
  • Basis: f(0) = 0, f(1) = 1
  • Rekursionsschritt: f(n - 1) + f(n - 2)
• Fakultät Funktion
  • Definitionsmenge: n >=1
  • Basis: f(1) = 1
  • Rekursionsschritt: f(n) = n * f(n - 1)

Türme von Hanoi

Die Türme von Hanoi ist ein Puzzel, bei dem es darum geht die Scheiben vom ersten Turm zu einem weiteren zu transferieren. Dabei darf immer nur eine jede Scheibe einzeln bewegt werden. Außerdem darf eine Scheibe nur auf eine größere Scheibe gelegt werden.

Anzahl der Schritte

Formel zur Berechnung der benötigten Schritte

• Rekursiv: s(n) = s(n-1)*2 + 1, s(1) = 1
• Explizit: s(n) = 2^s - 1

Rekursive beweg-funktion

FUNKTION bewege(anzahl, start, ziel, hilfe)
    bewege(anzahl-1, start, hilfe)
    bewege(1, start, ziel)
    bewege(anzahl-1, hilfe, ziel)

Struktogram der Algorithmus

Rekursive Beweg-Funktion in Java implementiert

/*Bewege eine Scheibe von einem Stapel zu einem anderen*/
public static void bewege_scheibe(int startstapel, int zielstapel)
{
    /* Bewege scheibe */
}

/*Bewege einen Turm vom startstapel zum zielstapel*/
public static void bewege_turm(int hoehe, int startstapel, int zielstapel, int hilfstapel)
{
    if (hoehe == 1)
    {
        bewege_scheibe(startstapel, zielstapel);
        return;
    }
    bewege_turm(hoehe-1, startstapel, hilfstapel, zielstapel);
    bewege_scheibe(1, startstapel, zielstapel);
    bewege_turm(hoehe, hilfstapel, zielstapel, startstapel);
}