是否可以使用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:如果这是作业,请引用我!