不带引用和赋值的递归

Question

这个问题在python（或类似）中被赋予了一个递归函数，可以重写它，这样它就不会引用自己。我做了一个简单的例子，适用于这个问题。当然，不允许将其设置为非递归函数。它仍然必须执行相同的递归过程。def fact(n):  if n == 0:    return 1  return n * fact(n - 1)这也相当于一个简写。fact = lambda n: 1 if n == 0 else n * fact(n - 1)在示例中，我不应该在函数定义内部调用。fact编辑：其他约束：解决方案工作时，不必进行分配。没有附加约束的一种解决方案（来自注释）是创建两个函数，它们交替调用彼此并有效地执行阶乘。这是不允许的，因为它要求您在两个变量中分配两个函数。ab不需要赋值的函数的快速示例是f = lambda x: x + 1为了让它执行在arugment上，我可以写55(lambda x: x + 1)(55)因此，分配是没有必要的。对此有什么提示吗？还是我被骗到了一个不可能的问题？

Answer 1

您可以使用 lambda 演算之类的东西来避免赋值和自引用，将两者都替换为对匿名函数参数的访问。例如：

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

在Ideone中测试。

---

下面提供了一些详细信息，以获取进一步的背景信息。

我知道lambda演算以强大（图灵完备）但极简主义的“编程语言”而闻名。它只使用变量的标识符，变量可以是绑定的（几乎是函数参数）也可以是未绑定的（在谈论表达式的某些部分时最相关）。所以这感觉就像一个很好的起点。

在 lambda 演算中表示递归的规范方法是使用不动点组合器。虽然该组合器可以在Python语法中天真地表达，但急切的评估会导致无限递归。

注释中提到的 https://rosettacode.org/wiki/Y_combinator#Python 的代码通过延迟其中一个递归调用直到函数实际被调用来避免这种无限递归。但我更愿意把对这种方法的详细解释留给一个单独的答案。

在lambda演算中表达递归的核心思想是什么？将函数作为参数传递给自身。所以我从这个开始：

lambda f: f(f)  # λ f.f f

我需要向该函数传递另一个将函数作为值的函数。喜欢。该调用的结果应该是一个函数，该函数应将 an 作为计算阶乘的参数。我的第一个近似值是将自己视为递归调用的表达式，所以我首先有这个：lambda f: …nf

(lambda f: f(f))(lambda f: (lambda n: n*f(n-1) if n else 1))

但后来我意识到这是错误的：它本身不是递归调用，因为它是接受参数的函数 。递归调用也是如此，导致我在开始时打印的解决方案。ffff(f)

Answer 2

这很可能绝对不是问题所在，但是通过一些/魔术，您可以重建所调用的函数...inspecttypes

import types, inspect

def fact(n):

    frame = inspect.currentframe()

    fn = types.FunctionType(frame.f_code, frame.f_globals)

    if n == 0:

        return 1

    return n * fn(n - 1)

print(fact(10))