在Python中，一个Lambda函数能否递归调用自身？

Question

一个常规函数在其定义中可以包含对自身的调用，这没有问题。但是我无法想象如何使用lambda函数实现这一点，因为lambda函数没有名称可以引用回来。有没有办法做到这一点？怎么做呢？

- dsimard

---

我很想给这个打上“有点奇怪”或者“你不想这样做”的标签。为什么不使用一个普通的函数呢？ - phihag

我想做的是在一棵树上运行reduce()。 在一维列表上lambda函数很好用，而递归感觉是使其在树上工作的自然方式。 话虽如此，真正的原因是我正在学习Python，所以我想试一试。 - dsimard

Reduce函数在使用命名函数时表现良好。Guido想要一段时间内从语言中删除lambda表达式。它们幸存了下来，但仍然没有理由在任何情况下都“需要”使用它们。 - John Fouhy

请不要使用reduce。使用递归函数的reduce非常复杂，需要很长时间。我认为它的时间复杂度大约是O(n**3)或者类似的。 - S.Lott

@S.Lott 真遗憾。这是 Python 解释器的问题还是有些更根本的东西我还没有理解？ - dsimard

@dsimard：reduce(f, (a,b,c,d)) 表示 f(f(f(a, b), c), d)。 - jfs

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)

更新: 根据其他答案的思路，我成功地将阶乘函数嵌入单个无名lambda函数中:

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

这是可能的，但并不是真正推荐的做法！

- Greg Hewgill

---

map(lambda n: (lambda f, n: f(f, n))(lambda f, n: n*f(f, n-1) if n > 0 else 1, n), range(10)) - jfs

无用但有趣。这就是为什么我喜欢计算机。 - Bite code

顺便说一句，以下是如何使用相同的技术（给它一个名称）生成斐波那契数列中的数字：fibonacci = lambda n: 0 if n == 0 else 1 if n == 1 else fibonacci(n-1)+fibonacci(n-2)。 - martineau

使用lambda和递归生成斐波那契数列的另一种方法：f = lambda x: 1 if x in (1,2) else f(x-1)+f(x-2) - Juan Gallostra

有人能说明为什么进行递归匿名函数调用是“不推荐”的吗？ - ThorSummoner

Answer 2

不使用reduce、map、命名lambda或Python内部函数：

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

- Hugo Walter

---

由于第一个函数及其返回值立即被调用，它们只起到赋值的作用。稍加 Python 化，这段代码就变成了 a = lambda myself, x: 1 if x==0 else x * myself(myself, x-1)，然后是 v = 10，最后是 a(a, v)。这个复杂的 lambda 函数被设计为接受自身作为第一个参数（因此我将参数重命名为 myself），它使用这个参数来递归调用自己。 - Felipe

我发布了一个新的答案，利用了新的Python语法:=，它给出了(f:=lambda x: 1 if x == 0 else x*f(x - 1))(5)，这样更短更易读。 - gruvw

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)

首先介绍一个与lambda演算中递归有关的不动点组合子，它被称为Y组合子。

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

第二部分是阶乘函数fact的递归定义。

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

应用Y组合子到fact上，形成另一个lambda表达式。

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

- Nux

---

干得好，你刚把Python变成了Lisp :) - Eliza Weisman

我发布了一个新答案，利用了新的 Python 语法 :=，它给出了 (f:=lambda x: 1 if x == 0 else x*f(x - 1))(5)，这个更短更易读。 - gruvw

Answer 4

你不能直接这样做，因为它没有名字。但是有一个像Lemmy指向的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]。

- sth

---

我认为我终于明白 Y 组合器的作用了。但是我认为在 Python 中，通常更容易使用“def”并给函数命名... - pdc

有趣的是，你的斐波那契数列示例是使用生成器更自然的例子。 :-) - pdc

比“不行”好得多的答案。 - new123456

+1，这是我能理解的唯一答案，不包括那些说“这是不可能的”和“函数必须有名字才能调用自己”的话。 - GingerPlusPlus

其实你可以的！我得到了帮助，我们解决了这个问题！ :) 请参见：https://dev59.com/RW4NtIcB2Jgan1znb9JU - TrueY

实际上，有很多基于“穷人版Y”的解决方案。 - Jason Hemann

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)

- Aaron Gallagher

---

我不懂 Python，但那看起来很糟糕。一定有更好的方法。 - Kyle Cronin

没人 - 关键是这看起来很糟糕是有原因的。Python并不是为此而设计的，这是一种不好的实践（在Python中）。Lambda表达式在设计上是有限制的。 - Gregg Lind

是的，对于最糟糕的Python代码给个赞。当Perl人说“如果你知道该怎么做，你可以在Perl中编写可维护的代码”时，我会说“是的，而且如果你知道该怎么做，你也可以在Python中编写不可维护的代码”。 :-) - Lennart Regebro

我曾认为在 Python 中编写混淆代码是不可能的，但现在我被证明是错的了。谢谢你，我的朋友。 - antimatter

@habnabit 感谢您的代码！如果我理解正确，这段代码是从编译后的代码中复制 lambda 对象。在我看来，找到原始对象是一种“更好”的方法。请参见：https://dev59.com/RW4NtIcB2Jgan1znb9JU - TrueY

Answer 6

这个答案相当基础，比Hugo Walter的答案简单一点：

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

Hugo Walter的回答：

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

- motoku

Answer 7

我们现在可以使用新的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

我们使用:=来命名lambda函数：在lambda函数内直接使用名称，并立即调用它作为匿名函数。

(参见https://www.python.org/dev/peps/pep-0572)

- gruvw

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

希望对某些人有所帮助。

- Sergey Luchko

Answer 9

顺便说一下，与其进行缓慢的斐波那契计算：

f = lambda x: 1 if x in (1,2) else f(x-1)+f(x-2)

我建议对Fibonacci数列进行快速计算：

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)

- Andrey Yarmolenko

---

只要你在加速程序，就不要使用递归。线性递归比树更好，但是即使是相对较小的参数也会导致堆栈溢出。 - chepner

Answer 10

简短回答

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

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

print(fact(5))

编辑日期：2022年04月24日

说明

对于这个问题，我们可以使用不动点组合子，特别是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))

请注意：

fact === 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中的不动点组合器：记忆化递归函数

- giokoguashvili

---

问题是关于Python的。 - ruohola

@ruohola 这是适用于所有语言的通用解决方案，但示例是用js编写的。 - giokoguashvili