Exkurs - Umwandlung rekursiver Algorithmen in iterative Algorithmen

Zur Orientierung

Wir werden hier die Umwandlung rekursiver Strukturen in iterative Strukturen betrachten. Diese Umwandlung ist deshalb von besonderer Bedeutung, da rekursive Algorithmen (derzeit) immer auf sequentiell arbeitenden Maschinen ausgeführt werden. Anhand von zwei Beispielen werden wir exemplarisch aufzeigen, dass eine solche Umwandlung immer möglich ist.

Beispiel: Fakultätsfunktion

Die Fakultätsfunktion kann durch die folgenden rekursive Funktionsdefinition festgelegt werden.

def fak(n):
    if n == 0:
        return 1
    else:
        return n * fak(n-1)

Für diese Funktion lässt sich leicht ein äquivalenter iterativer Berechnungsalgorithmus angeben:

def fak(n):
    i = n
    erg = 1
    while not i == 0:
        erg = erg * i
        i = i - 1
    return erg

Der iterative Algorithmus ergibt sich hier nicht aus einem automatisierbaren Umwandlungsverfahren, sondern indem das der rekursiven Funktionsdefinition zu Grunde liegende Berechnungsverfahren iterativ beschrieben wird.

Aufgabe 1

Entwickle einen iterativen Algorithmus zur Berechnung der ggt-Funktion, der dasselbe Berechnungsverfahren beschreibt, das auch der rekursiven Funktionsdefinition zu Grunde liegt.

def ggt(m, n):
    if m == n:
        return m
    else:
        if m > n:
            return ggt(m-n, n)
        else:
            return ggt(m, n-m)

Beispiel: Ackermannfunktion

Bei dem vorangehenden Beispiel war es relativ einfach, einen äquivalenten iterativen Algorithmus anzugeben. Schwieriger wird es im folgenden Beispielfall, der Ackermann-Funktion.

def ack(m, n):
    if m == 0:
        return n+1
    else:
        if n == 0:
            return ack(m-1, 1)
        else:
            return ack(m-1, ack(m, n-1))

Wir zeigen hier ein Umwandlungsverfahren, das auch auf andere rekursive Funktionsdefinitionen übertragbar ist. Das Verfahren basiert auf der Idee, die Reduktionsschritte bei der Berechnung von Termwerten zu simulieren. Dabei nutzen wir zwei Stapel, um den aktuellen Berechnungszustand darzustellen.

Dieses Verfahren lässt sich wie folgt mit Hilfe von stapel.py implementieren:

from stapel import *

def auswerten(term):
    t = Stapel()
    t.setStapel(term)
    s = Stapel()
    while not t.isEmpty():
        print("T:", t.getStapel())
        print("S:", s.getStapel())
        print()
        e = t.top()
        t.pop()
        if type(e) == int:
            s.push(e)
        else:
            m = s.top()
            s.pop()
            n = s.top()
            s.pop()
            op = e    
            if op == "+":
                t.push(m+n)
            elif op == "-":
                t.push(m-n)
            elif op == "*":
                t.push(m*n)
            elif op == "/":
                t.push(m/n)
            elif op == "a":
                if m == 0:
                    t.push(n+1)
                else:
                    if n == 0:
                        t.push("a")
                        t.push(m-1)
                        t.push(1)                
                    else:
                        t.push("a")
                        t.push(m-1)
                        t.push("a")
                        t.push(m)
                        t.push(n-1)    
    print("T:", t.getStapel())
    print("S:", s.getStapel())
    print()
    return s.top()

def ack(m, n):
    term = ["a", m, n]
    return auswerten(term)

Beachte, dass hier die Grundrechenoperatoren mit berücksichtigt werden, obwohl sie für die Auswertung der Ackermann-Funktion nicht benötigt werden.

Bei einem Aufruf von ack(1, 2) erhält man den folgenden Python-Dialog:

>>> ack(1, 2)
T: [2, 1, 'a']
S: []

T: [1, 'a']
S: [2]

T: ['a']
S: [1, 2]

T: [1, 1, 'a', 0, 'a']
S: []

T: [1, 'a', 0, 'a']
S: [1]

T: ['a', 0, 'a']
S: [1, 1]

T: [0, 1, 'a', 0, 'a', 0, 'a']
S: []

T: [1, 'a', 0, 'a', 0, 'a']
S: [0]

T: ['a', 0, 'a', 0, 'a']
S: [1, 0]

T: [1, 0, 'a', 0, 'a', 0, 'a']
S: []

T: [0, 'a', 0, 'a', 0, 'a']
S: [1]

T: ['a', 0, 'a', 0, 'a']
S: [0, 1]

T: [2, 0, 'a', 0, 'a']
S: []

T: [0, 'a', 0, 'a']
S: [2]

T: ['a', 0, 'a']
S: [0, 2]

T: [3, 0, 'a']
S: []

T: [0, 'a']
S: [3]

T: ['a']
S: [0, 3]

T: [4]
S: []

T: []
S: [4]

4

Aufgabe 2

Wandle entsprechend die rekursive Definition der Funktion galton in eine iterative um.

def galton(m, n):
    if m == 0:
        if n == 0:
            return 1
        else:
            return 0
    else:
        if n == 0:
            return 1
        else:
            return (galton(m-1, n-1) + galton(m-1, n))