Is it possible to use call/cc to implement recursion?

Question

I wonder if it is possible to define a recursive function without calling the function itself in its body but somehow using call/cc instead? Thanks.

Answer 1

You can implement a Y combinator using call/cc, as described here. (Many thanks to John Cowan for mentioning this neat post!) Quoting that post, here's Oleg's implementation:

Corollary 1. Y combinator via call/cc -- Y combinator without an explicit self-application.

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

Here, we used a fact that

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

and

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

are observationally equivalent.