funktionale Programmierung Material Motivation Grundlagen Rekursion Listen Funktionen höherer Ordnung list comprehension Generator lazy evaluation Haskell Endrekursion Beispiele
Pfad: Startseite / Fächer / Informatik / funktionale Programmierung / Endrekursion
Autor: mk
25.08.2010 19:21:14
612
Endrekursion

Beispiel 1

def f(n):
    """
    Fakultät rekursiv
    """
    if n == 0:
        return 1
    else:
        return n * f(n-1)

def fe(n):
    """
    Fakultät endrekursiv
    """
    def h(akku,n):
        if n == 0:
            return akku
        else:
            return h(n*akku,n-1)
    return h(1,n)

Beispiel 2

def ggti(a,b):
    """
    berechnet iterativ den ggt von a und b
    """
    while b > 0:
        (a,b) = (b,a%b)
    return a

def ggt(a,b):
    """
    berechnet rekursiv den ggt von a und b
    """
    if b == 0:
        return a
    else:
        return ggt(b,a%b)

def phii(n):
    """
    berechnet iterativ die Eulerfunktion
    """
    s = 1
    a = 2
    while a < n:
        if ggti(a,n) == 1:
            s = s + 1
        a = a + 1
    return s

def phi(n):
    """
    berechnet (end-)rekursiv die Eulerfunktion
    """
    def h(akku,n,a):
        if a == 1:
            return akku + 1
        else:
            if ggt(a,n) == 1:
                return h(akku+1,n,a-1)
            else:
                return h(akku,n,a-1)

    return h(0,n,n-1)

Das Beispiel phi zeigt, wie gewisse Parameter 'weitergereicht' werden. Das kann unverändert geschehen wie bei der Weitergabe der Zahl n, die zur ggt-Berechnung jeweils unverändert gebraucht wird. Das kann auch verändert geschehen, wenn in einem 'Akkumulator' ein Endergebnis 'angesammelt' wird.

Links