Y-Kombinator in Python

sma · Mittwoch 4. März 2009, 17:31

Mir war gerade danach... :)

# Y combinator
def Y(r): return (lambda f: f(f))(lambda f: r(lambda x: f(f)(x)))

Der Y-Kombinator ist eine Funktion, die auf eine Funktion angewandt wird, die eine nicht-rekursive Funktion liefert und diese Funktion dann rekursiv macht.

Beispiele:

Code: Alles auswählen

# factorial
print Y(lambda f: lambda n: 1 if n == 0 else n * f(n - 1))(20)

# fibonacci
print Y(lambda f: lambda n: 1 if n < 2 else f(n - 1) + f(n - 2))(20)

Stefan