rekursive - Kann sich eine Lambda-Funktion in Python rekursiv aufrufen?




rekursive programmierung (8)

Dafür können wir Festkomma-Kombinatoren , speziell Z Kombinator, verwenden, da es in strengen Sprachen, auch als Eager-Sprachen bezeichnet, funktioniert:

const Z = f => (x => f(v => x(x)(v)))(x => f(v => x(x)(v)))

Definieren Sie die Faktenfunktion und ändern Sie sie:

1. const fact n = n === 0 ? 1 : n * fact(n - 1)
2. const fact = n => n === 0 ? 1 : n * fact(n - 1)
3. const _fact = (fact => n => n === 0 ? 1 : n * fact(n - 1))

Beachte das:

Tatsache === Z (_Fakt)

Und benutze es:

const Z = f => (x => f(v => x(x)(v)))(x => f(v => x(x)(v)));

const _fact = f => n => n === 0 ? 1 : n * f(n - 1);
const fact = Z(_fact);

console.log(fact(5)); //120

Siehe auch: Fixpunkt-Kombinatoren in JavaScript: Memorisieren von rekursiven Funktionen

Eine reguläre Funktion kann einen Aufruf an sich selbst in ihrer Definition enthalten, kein Problem. Ich kann nicht herausfinden, wie man es mit einer Lambda-Funktion macht, aber aus dem einfachen Grund, dass die Lambda-Funktion keinen Namen hat, auf den man sich beziehen kann. Gibt es einen Weg, es zu tun? Wie?


Die einzige Möglichkeit, dies zu tun, besteht darin, der Funktion einen Namen zu geben:

fact = lambda x: 1 if x == 0 else x * fact(x-1)

oder alternativ für frühere Versionen von Python:

fact = lambda x: x == 0 and 1 or x * fact(x-1)

Update : Mit den Ideen aus den anderen Antworten konnte ich die faktorielle Funktion in ein einziges unbenanntes Lambda kürzen:

>>> map(lambda n: (lambda f, *a: f(f, *a))(lambda rec, n: 1 if n == 0 else n*rec(rec, n-1), n), range(10))
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

Also ist es möglich, aber nicht wirklich empfehlenswert!


Ich habe Python nie benutzt, aber this ist wahrscheinlich das, wonach Sie suchen.


Im Gegensatz zu dem, was gesagt wurde, können Sie dies direkt tun.

(lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda f: (lambda i: 1 if (i == 0) else i * f(i - 1)))(n)

Der erste Teil ist der Fixpunktkombinator Y , der die Rekursion im Lambda-Kalkül erleichtert

Y = (lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))

Der zweite Teil ist die faktorielle Funktion fact, die rekursiv definiert wird

fact = (lambda f: (lambda i: 1 if (i == 0) else i * f(i - 1)))

Y wird auf die Tatsache angewendet , um einen anderen Lambda-Ausdruck zu bilden

F = Y(fact)

was auf den dritten Teil, n , angewandt wird, der zum n- ten Faktorisch auswertet

>>> n = 5
>>> F(n)
120

oder gleichwertig

>>> (lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda f: (lambda i: 1 if (i == 0) else i * f(i - 1)))(5)
120

Wenn Sie jedoch Fakten bevorzugen, können Sie das auch mit dem gleichen Kombinator tun

>>> (lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda f: (lambda i: f(i - 1) + f(i - 2) if i > 1 else 1))(5)
8

Nun, nicht gerade reine Lambda-Rekursion, aber es ist anwendbar an Orten, an denen Sie nur Lambdas verwenden können, z. B. Reduzieren, Abbilden und Auflisten von Comprehensions oder anderen Lambdas. Der Trick besteht darin, vom Listenverständnis und dem Namensumfang von Python zu profitieren. Das folgende Beispiel durchläuft das Wörterbuch anhand der angegebenen Schlüsselkette.

>>> data = {'John': {'age': 33}, 'Kate': {'age': 32}}
>>> [fn(data, ['John', 'age']) for fn in [lambda d, keys: None if d is None or type(d) is not dict or len(keys) < 1 or keys[0] not in d else (d[keys[0]] if len(keys) == 1 else fn(d[keys[0]], keys[1:]))]][0]
33

Das Lambda verwendet seinen im Listenverständnisausdruck (Fn) definierten Namen wieder. Das Beispiel ist ziemlich kompliziert, aber es zeigt das Konzept.


Sie können es nicht direkt tun, weil es keinen Namen hat. Aber mit einer Hilfsfunktion wie dem Y-Kombinator, auf den Lemmy gezeigt hat, können Sie Rekursion erzeugen, indem Sie die Funktion als Parameter an sich selbst übergeben (so seltsam das auch klingt):

# helper function
def recursive(f, *p, **kw):
   return f(f, *p, **kw)

def fib(n):
   # The rec parameter will be the lambda function itself
   return recursive((lambda rec, n: rec(rec, n-1) + rec(rec, n-2) if n>1 else 1), n)

# using map since we already started to do black functional programming magic
print map(fib, range(10))

Dies druckt die ersten zehn Fibonacci-Zahlen: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55] ,


ohne reduce, map, named lambdas oder python internals:

(lambda a:lambda v:a(a,v))(lambda s,x:1 if x==0 else x*s(s,x-1))(10)

def recursive(def_fun):
    def wrapper(*p, **kw):
        fi = lambda *p, **kw: def_fun(fi, *p, **kw)
        return def_fun(fi, *p, **kw)

    return wrapper


factorial = recursive(lambda f, n: 1 if n < 2 else n * f(n - 1))
print(factorial(10))

fibonaci = recursive(lambda f, n: f(n - 1) + f(n - 2) if n > 1 else 1)
print(fibonaci(10))

Ich hoffe, es wäre hilfreich für jemanden.





y-combinator