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 / Rekursion
Autor: mk
15.04.2011 10:06:08
524
Rekursion

Ersatz von Schleifen durch Rekursion

Da in bei rein-funktionaler Programmierung nur Funktionen ohne innere Zustände verwendet werden, können Schleifen im bisherigen Stil nicht realisiert werden.

Beispiel

Man beachte, dass eine Funktion f als Parameter übergeben wird. In diesem Sinn sind p1 und p2 Funktionen höherer Ordnung.

iterativ

def p1(n,f):
    """
    die Funktion f wird n-mal aufgerufen, iterativ
    """
    for i in range(n):
        f()

rekursiv

def p2(n,f):
    """
    die Funktion f wird n-mal aufgerufen, rekursiv
    """
    if n > 0:
        f()
        p2(n-1,f)

Tests

>>> def f():
	print('Ich darf meinen Lehrer nicht beißen!')

	
>>> p1(3,f)
Ich darf meinen Lehrer nicht beißen!
Ich darf meinen Lehrer nicht beißen!
Ich darf meinen Lehrer nicht beißen!
>>> p2(3,f)
Ich darf meinen Lehrer nicht beißen!
Ich darf meinen Lehrer nicht beißen!
Ich darf meinen Lehrer nicht beißen!

lambda-Funktionen

>>> p2(4,lambda : print('Ich liebe funktionale Programmierung!'))
Ich liebe funktionale Programmierung!
Ich liebe funktionale Programmierung!
Ich liebe funktionale Programmierung!
Ich liebe funktionale Programmierung!
>>>

lambda-Funktionen sind syntaktischer Zucker für eine anonyme und platzsparende Definition von Funktionen. Nach dem Schlüsselwort lambda steht durch ein Doppelpunkt getrennt eine Variable und ein Ausdruck, der die Variable enthält. Der für eine konkrete Variable ausgewertete Ausdruck ist die Rückgabe der Funktion. Statt der Funktion einen Namen zu geben, kann man sie auch anonym benutzen.

>>> f = lambda x : x**2
>>> f(3)
9
>>> (lambda a : a**3)(2)
8

Realisierung rekursiver Strukturen mit eigenem Stack

Manche einfache Programmiersprachen, typischerweise Assembersprachen z.B. von Mikrocontrollern, haben keine eingebaute Rekursion. Hier müssen rekursive Problemlösungen 'zu Fuß' mit Hilfe von Stacks realisiert werden.

def fakui(n):
    """
    return n! , n (int), iterativ
    """
    erg = 1
    for i in range(2,n+1):
        erg = erg * i
    return erg

def fakur(n):
    """
    return n! , n (int), rekursiv
    """
    if n == 0:
        return 1
    else:
        return n * fakur(n-1)

def fakus(n):
    """
    return n! , n (int), mit Stack
    """
    def erzeugeStack(n):
        if n > 0:
            stack.append(n)
            erzeugeStack(n-1)

    def werteStackaus():
        erg = 1
        while stack != []:
            erg = erg * stack.pop()
        return erg

    stack = []
    erzeugeStack(n)
    return werteStackaus()

import time

def test(f,*args):
    """
    gibt die Zeit zurueck, die der Aufruf f(*args) verbraucht
    """
    t1 = time.time()
    f(*args)               # Rueckgabe kann hier entfallen
    t2 = time.time()
    return t2-t1

Tests

>>> test(fakui,500)
0.0007519721984863281
>>> test(fakur,500)
0.0013439655303955078
>>> test(fakus,500)
0.0024619102478027344

Bemerkung

pop ist eine Funktion, wie sie es in funktionaler Programmierung gerade nicht sein sollte. Sie gibt den Wert oben auf dem Stack zurück und nimmt den Wert als Seiteneffekt vom Stack.

Unterrichtseinheit zur Rekursion

Was ist dran an Rekursion, sodass keine moderne Programmiersprache auf sie verzichtet? Ist Rekursion besser oder schlechter als Iteration? Fragen dieser Art werden in der Unterrichtseinheit zur Rekursion auf www.inf-schule.de geklärt.

Links