functional-programming - 是否可以使用 call/cc 来实现递归？

Question

我想知道是否可以定义一个递归函数而不在其主体中调用函数本身，而是以某种方式使用 call/cc 来代替？谢谢。

Answer 1

您可以使用 来实现 Y 组合器call/cc，如此处所述。（非常感谢 John Cowan 提到这篇简洁的帖子！）引用该帖子，这是 Oleg 的实现：

推论 1. Y 组合器通过call/cc-- Y 组合器没有明确的自我应用。

(define (Y f)
  ((lambda (u) (u (lambda (x) (lambda (n) ((f (u x)) n)))))
   (call/cc (call/cc (lambda (x) x)))))

在这里，我们使用了一个事实

((lambda (u) (u p)) (call/cc call/cc))

和

((lambda (u) (u p)) (lambda (x) (x x)))

观察上是等价的。

Answer 2

你的问题有点含糊。特别是，听起来您想要一个使用 call/cc 来模拟递归调用而不直接进行递归调用的系统。但事实证明，您可以在不进行递归调用且不使用 call/cc 的情况下对递归调用进行建模。例如：

#lang racket

(define (factorial f n)
  (if (= n 0) 1 (* n (f f (- n 1)))))

(factorial factorial 3)

这看起来像是作弊，但它是 Y 组合器的基础。也许您可以收紧您正在考虑的一系列限制？

PS：如果这是作业，请引用我！

Answer 3

恐怕call/cc与这件事关系不大。实际上只有两种定义递归函数的方法：

• 假设您的语言允许递归函数定义；即，函数体可以引用封闭函数，或者函数体可以引用其主体引用f的函数。在这种情况下，好吧，您只需以通常的方式编写它。gf
• 如果您的语言禁止这两者，但它仍然具有一流的函数和 lambda，那么您可以使用像 Y 组合器这样的定点组合器。您编写函数，以便将表示递归步骤的函数作为额外参数；您将递归的每个地方，而不是调用该参数。

所以对于factorial，你可以这样写：

(define (factorial-step recurse n)
  (if (zero? n)
      1
      (* n (recurse (- n 1)))))

Y 组合器的神奇之处在于它构造了recurse将被馈送到factorial-step.