Может ли лямбда-функция вызывать себя рекурсивно в Python?

Question

Обычная функция может содержать вызов для себя в своем определении, нет проблем. Я не могу понять, как это сделать с помощью лямбда-функции, хотя по той простой причине, что у лямбда-функции нет имени, на которое можно сослаться. Есть ли способ сделать это? Как

Answer 1

Единственный способ, которым я могу придумать, состоит в том, чтобы дать функции имя:

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

или поочередно, для более ранних версий python:

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

Обновление : используя идеи из других ответов, я смог втиснуть факторную функцию в одну безымянную лямбду:

>>> 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]

Так что это возможно, но не очень рекомендуется!

Answer 2

без редуктора, map, именованные лямбды или внутренности питона:

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

Answer 3

Вопреки сказанному, вы МОЖЕТЕ делать это напрямую.

(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)

Первая часть - это комбинатор с фиксированной точкой Y , который облегчает рекурсию в лямбда-исчислении

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

вторая часть - это факториальная функция факт определяется рекурсивно

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

Y применяется к fact для формирования другого лямбда-выражения

F = Y(fact)

, который применяется к третьей части, n , который оценивается как n-й факториал

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

или эквивалентно

>>> (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

Если вы предпочитаете от выдумок до фактов , вы можете сделать это тоже, используя тот же комбинатор

>>> (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

Answer 4

Вы не можете сделать это напрямую, потому что у него нет имени. Но с помощью вспомогательной функции, на которую указал Лемми Y-комбинатор, вы можете создать рекурсию, передав функцию в качестве параметра себе (как бы странно это не звучало):

# 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))

Это печатает первые десять чисел Фибоначчи: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55],

Answer 5

Да. У меня есть два способа сделать это, и один уже был покрыт. Это мой любимый способ.

(lambda v: (lambda n: n * __import__('types').FunctionType(
        __import__('inspect').stack()[0][0].f_code, 
        dict(__import__=__import__, dict=dict)
    )(n - 1) if n > 1 else 1)(v))(5)

Answer 6

Я никогда не использовал Python, но это , вероятно, то, что вы ищете.

Answer 7

Этот ответ довольно простой. Это немного проще, чем ответ Хьюго Уолтера:

>>> (lambda f: f(f))(lambda f, i=0: (i < 10)and f(f, i + 1)or i)
10
>>>

Хьюго Уолтер ответил:

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

Answer 8

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))

Надеюсь, это будет кому-то полезно.

Answer 9

Для этого мы можем использовать комбинаторы с фиксированной точкой , в частности Z комбинатор, поскольку он будет работать на строгих языках, также называемых нетерпеливыми языками:

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

Определите fact функцию и измените ее:

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))

Обратите внимание, что:

факт === Z (_fact)

И используйте это:

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

Смотри также: Комбинаторы с фиксированной запятой в JavaScript: запоминание рекурсивных функций

Answer 10

Ну, не совсем чистая лямбда-рекурсия, но она применима в местах, где вы можете использовать только лямбда-выражения, например, уменьшить, отобразить и составить список, или другие лямбды. Хитрость заключается в том, чтобы извлечь пользу из понимания списка и области имен Python. В следующем примере словарь проходит по заданной цепочке ключей.

>>> 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

Лямбда повторно использует свое имя, определенное в выражении понимания списка (fn). Пример довольно сложный, но он показывает концепцию.