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.

Answer 2

Your question is a bit vague. In particular, it sounds like you want a system that models recursive calls without directly making recursive calls, using call/cc. It turns out, though, that you can model recursive calls without making recursive calls and also without using call/cc. For instance:

#lang racket

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

(factorial factorial 3)

That may seem like cheating, but it's the foundation of the Y combinator. Perhaps you can tighten up the set of restrictions you're thinking of?

P.S.: if this is homework, please cite me!