Search code examples
functional-programmingschemecallcc

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

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.

Solution

  • 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.