Может ли лямбда-функция вызывать себя рекурсивно в Python?
Обычная функция может содержать вызов для себя в своем определении, без проблем. Я не могу понять, как это сделать с помощью лямбда-функции, хотя по той простой причине, что у лямбда-функции нет имени, на которое можно сослаться. Есть ли способ сделать это? Как?
19 ответов
Единственный способ сделать это состоит в том, чтобы дать функции имя:
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]
Так что это возможно, но не очень рекомендуется!
Без редуктора, map, с именами lambdas или python:
(lambda a:lambda v:a(a,v))(lambda s,x:1 if x==0 else x*s(s,x-1))(10)
Вопреки сказанному, вы МОЖЕТЕ сделать это напрямую.
(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 применяется к факту, чтобы сформировать другое лямбда-выражение
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
Вы не можете сделать это напрямую, потому что у него нет имени. Но с помощью вспомогательной функции, на которую указал Лемми 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],
Да. У меня есть два способа сделать это, и один уже был покрыт. Это мой любимый способ.
(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)
Этот ответ довольно простой. Это немного проще, чем ответ Хьюго Уолтера:
>>> (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)
Я никогда не использовал Python, но это, вероятно, то, что вы ищете.
Теперь мы можем использовать новый синтаксис Python, чтобы сделать его короче и легче для чтения:
Фибоначчи:
>>> (f:=lambda x: 1 if x <= 1 else f(x - 1) + f(x - 2))(5)
8
Факториал:
>>> (f:=lambda x: 1 if x == 0 else x*f(x - 1))(5)
120
Мы используем
:=чтобы назвать лямбду: используйте имя непосредственно в самой лямбде и сразу вызывайте ее как анонимную функцию.
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))
Надеюсь, это будет полезно для кого-то.
Кстати, вместо медленного вычисления Фибоначчи:
f = lambda x: 1 if x in (1,2) else f(x-1)+f(x-2)
Предлагаю быстрый расчет Фибоначчи:
fib = lambda n, pp=1, pn=1, c=1: pp if c > n else fib(n, pn, pn+pp, c+1)
Работает очень быстро.
Также здесь факториальный расчет:
fact = lambda n, p=1, c=1: p if c > n else fact(n, p*c, c+1)
Для этого мы можем использовать комбинаторы с фиксированной точкой, в частности 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: запоминание рекурсивных функций
Ну, не совсем чистая лямбда-рекурсия, но она применима в тех местах, где вы можете использовать только лямбды, например, уменьшить, отобразить и составить список, или другие лямбды. Хитрость заключается в том, чтобы извлечь выгоду из понимания списка и области имен 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). Пример довольно сложный, но он показывает концепцию.
Я получил домашнее задание по этому поводу и кое-что понял, вот пример лямбда-функции с рекурсивными вызовами:
sucesor = lambda n,f,x: (f)(x) if n == 0 else sucesor(n-1,f,(f)(x))
Ответ Мотокура мне понравился как лаконичный. Вот мои мысли о поиске решения:
Для рекурсии нам нужно вызвать тот же метод, но, поскольку это лямбда, мы не можем получить ссылку на него. Один из способов ссылаться на имя — через параметры метода. Итак, метод, который мы хотим вызвать, должен быть передан в качестве параметра. (Другой способ — получить ссылку на текущий метод, проверив стек вызовов, как в ответе Хабнабита)
Следующее, что нужно сделать, это иметь возможность передавать разные значения каждому рекурсивному вызову. Поэтому мы вводим еще один параметр для хранения значения.
Пример расчета факториала 6:
(lambda f : f(f,6) )( lambda f, x : 1 if x <= 1 else x * f(f, x-1) )
ИЛИ
Определение параметра с самого начала вместо его жесткого кодирования:
(lambda f,x : f(f,x) )( (lambda f, x : 1 if x <= 1 else x * f(f, x-1)), 6)
Есть два основных способа реализовать это:
1)
fact = lambda n : n*fact(n-1) if n>0 else 1
print(fact(6))
Выход:
2)
fact = lambda n : 1 if n==0 else n*fact(n-1)
print(fact(6))
Выход:
720
Я знаю, что это старая ветка, но она занимает высокие позиции в некоторых результатах поиска Google :). С появлением python 3.8 вы можете использовать оператор моржа для реализации Y-комбинатора с меньшим синтаксисом!
fib = (lambda f: (rec := lambda args: f(rec, args)))\
(lambda f, n: n if n <= 1 else f(n-2) + f(n-1))
Lambda может легко заменить рекурсивные функции в Python:
Например, это базовое соединение_interest:
def interest(amount, rate, period):
if period == 0:
return amount
else:
return interest(amount * rate, rate, period - 1)
можно заменить на:
lambda_interest = lambda a,r,p: a if p == 0 else lambda_interest(a * r, r, p - 1)
или для большей наглядности:
lambda_interest = lambda amount, rate, period: \
amount if period == 0 else \
lambda_interest(amount * rate, rate, period - 1)
ПРИМЕНЕНИЕ:
print(interest(10000, 1.1, 3))
print(lambda_interest(10000, 1.1, 3))
Выход:
13310.0
13310.0
Если бы вы были действительно мазохистами, вы могли бы сделать это, используя расширения C, но, повторяя Грега (привет, Грег!), Это превосходит возможности лямбда-функции (безымянный, анонимный).
Нет (для большинства значений нет).