Exkurs - Umwandlung iterativer Algorithmen in rekursive Algorithmen

Zur Orientierung

Wir werden hier die Umwandlung iterativer Algorithmen in rekursive betrachten. Am Beispiel der Potenzfunktion werden wir exemplarisch aufzeigen, dass eine solche Umwandlung immer möglich ist.

Beispiel: Potenzfunktion

Die Potenzfunktion kann durch die folgenden iterative Funktionsdefinition festgelegt werden.

def pot(a, n):
    p = 1
    while n > 0:
        p = p * a
        n = n - 1
    return p

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

def pot(a, n):
    if n == 0:
        return 1
    else:
        return a * pot(a, n-1)

Der rekursive Algorithmus ergibt sich hier nicht aus einem automatisierbaren Umwandlungsverfahren, sondern indem das der iterativen Funktionsdefinition zu Grunde liegende Berechnungsverfahren rekursiv beschrieben wird.

Im Folgenden soll ein allgemeines Verfahren beschrieben werden, mit dem man jeden iterativen Algorithmus in einen rekursiven Algorithmus umwandeln kann. Die Idee besteht darin, die Abarbeitung eines iterativen Algorithmus mit Hilfe rekursiver Funktionen zu simulieren.

Abarbeitung eines iterativen Algorithmus

Betrachte zunächst die Abarbeitung des iterativen Algorithmus zur Berechnung der Potenzfunktion.

{a -> 2; n -> 3}
p = 1
while n > 0:
    p = p * a
    n = n - 1
{a -> 2; n -> 3; p -> 1}
while n > 0:
    p = p * a
    n = n - 1
{a -> 2; n -> 3; p -> 1}
p = p * a
n = n - 1
while n > 0:
    p = p * a
    n = n - 1
{a -> 2; n -> 3; p -> 2}
n = n - 1
while n > 0:
    p = p * a
    n = n - 1
{a -> 2; n -> 2; p -> 2}
while n > 0:
    p = p * a
    n = n - 1
{a -> 2; n -> 2; p -> 2}
p = p * a
n = n - 1
while n > 0:
    p = p * a
    n = n - 1
{a -> 2; n -> 2; p -> 4}
n = n - 1
while n > 0:
    p = p * a
    n = n - 1
{a -> 2; n -> 1; p -> 4}
while n > 0:
    p = p * a
    n = n - 1
{a -> 2; n -> 1; p -> 4}
p = p * a
n = n - 1
while n > 0:
    p = p * a
    n = n - 1
{a -> 2; n -> 1; p -> 8}
n = n - 1
while n > 0:
    p = p * a
    n = n - 1
{a -> 2; n -> 0; p -> 8}
while n > 0:
    p = p * a
    n = n - 1
{a -> 2; n -> 0; p -> 8}

Aufgabe 1

Analysiere die gezeigte Darstellung zur Abarbeitung eines iterativen Algorithmus. Verfahre analog beim folgenden iterativen Algorithmus und setze die begonnene Abarbeitung fort.

{a -> 2; n -> 3}
p = 1
while n > 0:
    if (n % 2) == 1:
        p = p * a
        n = n - 1
    a = a * a
    n = n // 2
{a -> 2; n -> 3; p -> 1}
while n > 0:
    if (n % 2) == 1:
        p = p * a
        n = n - 1
    a = a * a
    n = n // 2
{a -> 2; n -> 3; p -> 1}
if (n % 2) == 1:
    p = p * a
    n = n - 1
a = a * a
n = n // 2
while n > 0:
    if (n % 2) == 1:
        p = p * a
        n = n - 1
    a = a * a
    n = n // 2
{a -> 2; n -> 3; p -> 1}
p = p * a
n = n - 1
a = a * a
n = n // 2
while n > 0:
    if (n % 2) == 1:
        p = p * a
        n = n - 1
    a = a * a
    n = n // 2
{a -> 2; n -> 3; p -> 2}
...
{a -> 16; n -> 0; p -> 8}

Implementierung mit rekursiven Funktionen

Zunächst müssen die zu verarbeitenden Daten mit Hilfe geeigneter Datenstrukturen modelliert werden. Das folgende Ablaufprotokoll zeigt, wie die Daten mit Hilfe von Listen, Tupeln etc. dargestellt werden sollen.

[('a', 2), ('n', 3)]
[('=', 'p', 1), ('while', ('>', 'n', 0), [('=', 'p', ('*', 'p', 'a')), ('=', 'n', ('-', 'n', 1))])]

[('a', 2), ('n', 3), ('p', 1)]
[('while', ('>', 'n', 0), [('=', 'p', ('*', 'p', 'a')), ('=', 'n', ('-', 'n', 1))])]

[('a', 2), ('n', 3), ('p', 1)]
[('=', 'p', ('*', 'p', 'a')), ('=', 'n', ('-', 'n', 1)), ('while', ('>', 'n', 0), [('=', 'p', ('*', 'p', 'a')), ('=', 'n', ('-', 'n', 1))])]

[('a', 2), ('n', 3), ('p', 2)]
[('=', 'n', ('-', 'n', 1)), ('while', ('>', 'n', 0), [('=', 'p', ('*', 'p', 'a')), ('=', 'n', ('-', 'n', 1))])]

[('a', 2), ('n', 2), ('p', 2)]
[('while', ('>', 'n', 0), [('=', 'p', ('*', 'p', 'a')), ('=', 'n', ('-', 'n', 1))])]

[('a', 2), ('n', 2), ('p', 2)]
[('=', 'p', ('*', 'p', 'a')), ('=', 'n', ('-', 'n', 1)), ('while', ('>', 'n', 0), [('=', 'p', ('*', 'p', 'a')), ('=', 'n', ('-', 'n', 1))])]

[('a', 2), ('n', 2), ('p', 4)]
[('=', 'n', ('-', 'n', 1)), ('while', ('>', 'n', 0), [('=', 'p', ('*', 'p', 'a')), ('=', 'n', ('-', 'n', 1))])]

[('a', 2), ('n', 1), ('p', 4)]
[('while', ('>', 'n', 0), [('=', 'p', ('*', 'p', 'a')), ('=', 'n', ('-', 'n', 1))])]

[('a', 2), ('n', 1), ('p', 4)]
[('=', 'p', ('*', 'p', 'a')), ('=', 'n', ('-', 'n', 1)), ('while', ('>', 'n', 0), [('=', 'p', ('*', 'p', 'a')), ('=', 'n', ('-', 'n', 1))])]

[('a', 2), ('n', 1), ('p', 8)]
[('=', 'n', ('-', 'n', 1)), ('while', ('>', 'n', 0), [('=', 'p', ('*', 'p', 'a')), ('=', 'n', ('-', 'n', 1))])]

[('a', 2), ('n', 0), ('p', 8)]
[('while', ('>', 'n', 0), [('=', 'p', ('*', 'p', 'a')), ('=', 'n', ('-', 'n', 1))])]

[('a', 2), ('n', 0), ('p', 8)]
[]

Die folgenden rekursiven Funktionen dienen dazu, die Abarbeitung eines iterativen Algorithmus zu simulieren.

VariablenWert:

def VariablenWert(bezeichner, zustand):
    """ liefert den Wert einer Variablen

    >>> VariablenWert('y', [('x', 4), ('y', 3), ('z', 7)])
    3
    >>> VariablenWert('a', [('x', 4), ('y', 3), ('z', 7)])
    '?'
    """
    if len(zustand) == 0:
        return '?'
    else:
        if bezeichner == zustand[0][0]:
            return zustand[0][1]
        else:
            return VariablenWert(bezeichner, zustand[1:])

NeuerZustand:

def NeuerZustand(bezeichner, wert, zustand):
    """ aktualisiert den Wert einer Variablen

    >>> NeuerZustand('y', 6, [('x', 4), ('y', 3), ('z', 7)])
    [('x', 4), ('y', 6), ('z', 7)]

    >>> NeuerZustand('a', 0, [('x', 4), ('y', 3), ('z', 7)])
    [('x', 4), ('y', 3), ('z', 7), ('a', 0)]

    """
    if len(zustand) == 0:
        return [(bezeichner, wert)]
    else:
        if bezeichner == zustand[0][0]:
            return [(bezeichner, wert)] + zustand[1:]
        else:
            return [zustand[0]] + NeuerZustand(bezeichner, wert, zustand[1:])

TermWert:

def TermWert(term, zustand):
    """ liefert den Wert eines Terms

    >>> TermWert(('+', 'z', 4), [('x', 4), ('y', 3), ('z', 7)])
    11
    >>> TermWert(('+', 'z', ('+', 'x', 'x')), [('x', 4), ('y', 3), ('z', 7)])
    15
    """
    if isinstance(term, int):
        return term
    else:
        if not isinstance(term, tuple):
            return VariablenWert(term, zustand)
        else:
            if term[0] == '+':
                return TermWert(term[1], zustand) + TermWert(term[2], zustand)
            elif term[0] == '-':
                return TermWert(term[1], zustand) - TermWert(term[2], zustand)
            elif term[0] == '*':
                return TermWert(term[1], zustand) * TermWert(term[2], zustand)
            elif term[0] == '//':
                return TermWert(term[1], zustand) // TermWert(term[2], zustand)
            elif term[0] == '%':
                return TermWert(term[1], zustand) % TermWert(term[2], zustand)

BooleWert:

def BooleWert(term, zustand):
    """ liefert den Wert eines booleschen Terms

    >>> BooleWert(('>', 'x', 4), [('x', 4), ('y', 3), ('z', 7)])
    False
    
    """
    if isinstance(term, bool):
        return term
    else:
        if not isinstance(term, tuple):
            return '?'
        elif term[0] == '==':
            return TermWert(term[1], zustand) == TermWert(term[2], zustand)
        elif term[0] == '<':
            return TermWert(term[1], zustand) < TermWert(term[2], zustand)
        elif term[0] == '>':
            return TermWert(term[1], zustand) > TermWert(term[2], zustand)
        elif term[0] == '<=':
            return TermWert(term[1], zustand) <= TermWert(term[2], zustand)
        elif term[0] == '>=':
            return TermWert(term[1], zustand) >= TermWert(term[2], zustand)

AnweisungenAusfuehren:

def AnweisungenAusfuehren(anweisungen, zustand):
    """ fuehrt eine Anweisung aus

    >>> AnweisungenAusfuehren([('=', 'x', 2), ('if', ('>', 'x', 3), [('=', 'y', '0')], [('=', 'y', 1)])], [])
    [('x', 2), ('y', 1)]

    >>> AnweisungenAusfuehren([('while', ('>', 'u', 0), [('=', 'u', ('-', 'u', 1))])], [('u', 3)])
    [('u', 0)]

    """

    # zur Ausgabe der aktuellen Daten  
    #print("Z: ", zustand)
    #print("P: ", anweisungen)
    #print()
    # die Kommentarzeichen entfernen
    if len(anweisungen) == 0:
        return zustand
    else:
        if anweisungen[0][0] == '=':
            return AnweisungenAusfuehren(anweisungen[1:], \
                                         NeuerZustand(anweisungen[0][1], \
                                                      TermWert(anweisungen[0][2], zustand), zustand))
        else:
            if anweisungen[0][0] == 'if':
                if BooleWert(anweisungen[0][1], zustand):
                    return AnweisungenAusfuehren(anweisungen[0][2] + anweisungen[1:], zustand)
                else:
                    return AnweisungenAusfuehren(anweisungen[0][3] + anweisungen[1:], zustand)
            else:
                if anweisungen[0][0] == 'while':
                    if BooleWert(anweisungen[0][1], zustand):
                        return AnweisungenAusfuehren(anweisungen[0][2] + anweisungen, zustand)
                    else:
                        return AnweisungenAusfuehren(anweisungen[1:], zustand)

Die Funktion potenz(a, n) lässt sich jetzt mit den oben aufgelisteten rekursiven Funktionen auch wie folgt definieren:

def potenz(a, n):
    return VariablenWert('p', \
                         AnweisungenAusfuehren(\
                             [\
                                 ('=', 'p', 1), \
                                 ('while', ('>', 'n', 0), \
                                 [\
                                     ('=', 'p', ('*', 'p', 'a')), \
                                     ('=', 'n', ('-', 'n', 1))\
                                 ])\
                             ], \
                             [('a', a), ('n', n)]))

Aufgabe 2

Teste diese Funktionsdefinition, z. B. so:

>>> potenz(2, 3)
8

Aufgabe 3

Entwickle analog eine Funktionsdefinition zu folgendem iterativen Algorithmus:

def potenz(a, n):
    p = 1
    while n > 0:
        if (n % 2) == 1:
            p = p * a
            n = n - 1
        a = a * a
        n = n // 2
    return p