python - 没有引用和赋值的递归

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在函数定义中。

编辑:

附加约束:
分配必须不是解决方案起作用的必要条件。

一种没有附加约束的解决方案(来自评论)是创建两个函数 a和 b它们交替调用并有效地进行阶乘。这是不允许的，因为它要求您在两个变量中分配两个函数。

一个不需要赋值的函数的简单示例是

f = lambda x: x + 1

让它在参数 55 上执行, 我可以写

(lambda x: x + 1)(55)

所以没有必要分配。

对此有任何提示吗？还是我被欺骗了一个不可能的问题？

Answer 1

您可以使用 lambda calculus 之类的内容为了避免赋值和自引用，将两者都替换为访问匿名函数的参数。例如:

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

测试于 Ideone .

下面的一些详细信息可提供更多背景信息。

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

规范的表达方式recursion in lambda calculus正在使用 fixed point combinator .虽然该组合子可以用 Python 语法简单地表达，但急切求值会导致无限递归。

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

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

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

我需要将该函数传递给另一个将函数作为值的函数。点赞lambda f: … .该调用的结果应该是一个应该采用 n 的函数。作为计算阶乘的参数。我的第一个近似值是 f本身作为递归调用的表达式，所以我首先有了这个:

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

但后来我意识到这是错误的:f本身不是递归调用，因为 f是带参数的函数 f .所以f(f)是递归调用，导致我在一开始打印的解决方案。