Exkurs - Rekursive Berechnungen mit hohem Aufwand

Wege im Galtonbrett

Betrachte noch einmal die Funktion galton zur Berechnung der Anzahl der Wege im Galton-Brett.

def galton(m, n):
    print('galton(', m, ",", n, ')')
    if m < n:
        return None
    else:
        if (n == 0) or (m == n):
            return 1
        else:
            return (galton(m-1, n-1) + galton(m-1, n))

Beachte, dass diese Implementierung jeden Funktionsaufruf mit den aktuellen Parameterwerten auf dem Bildschirm ausgibt.

Aufgabe 1

Der folgende Python-Dialog zeigt die Auswertung des Funktionsaufrufs galton(5, 3).

>>> galton(5, 3)
galton( 5 , 3 )
galton( 4 , 2 )
galton( 3 , 1 )
galton( 2 , 0 )
galton( 2 , 1 )
galton( 1 , 0 )
galton( 1 , 1 )
galton( 3 , 2 )
galton( 2 , 1 )
galton( 1 , 0 )
galton( 1 , 1 )
galton( 2 , 2 )
galton( 4 , 3 )
galton( 3 , 2 )
galton( 2 , 1 )
galton( 1 , 0 )
galton( 1 , 1 )
galton( 2 , 2 )
galton( 3 , 3 )
10

Was fällt hier auf?

Erstelle selbst eine vollständige Reduktionskette. In jedem Reduktionsschritt sollst du nur eine Reduktionsregel anwenden. Kürze den Funktionsnamen galton mit g ab.

g(5, 3) ->
g(4, 2) + g(4, 3) ->
(g(3, 1) + g(3, 2)) + g(4, 3) ->
...
10

Warum handelt es sich bei der vorliegenden Funktionsdefinition um ein ineffizientes Berechnungsverfahren? Woran liegt das?

Die Ackermann-Funktion

Die Ackermann-Funktion wird durch folgende Reduktionsregeln festgelegt.

ack(0, y) -> y+1 
ack(x, 0) -> ack(x-1, 1), falls x > 0
ack(x, y) -> ack(x-1, ack(x, y-1)), falls y > 0

Aufgabe 2

Implementiere die Ackermann-Funktion in Python so, dass jeder Funktionsaufruf mit den aktuellen Parameterwerten auf dem Bildschirm ausgegeben wird (vgl. Aufgabe 1).

Teste verschiedene Funktionsaufrufe wie z. B. ack(2, 3) und ack(3, 2). Was fällt auf?

Kaskadenartige und verschachtelte Rekursion

Wenn auf der rechten Seite in einer Reduktionsregel mehrere rekursive Funktionsaufrufe vorkommen, dann spricht man von kaskadenartiger Rekursion. Verschachtelte Rekursion liegt vor, wenn ein rekursiver Aufruf weitere rekursive Aufrufe der Fuktion enthält. In beiden Fällen kann es zu einer raschen Vermehrung an rekursiven Funktionsaufrufen kommen. Dabei kann es durchaus vorkommen, dass ein und dieselbe Berechnung mehrfach durchgeführt wird. Beide Aspekte - die Verwaltung vieler Funktionsaufrufe sowie die mehrfache Durchführung identischer Berechnungen - führen zu einem hohen Verbrauch an Ressourcen.