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!

Answer 3

I'm afraid call/cc doesn't really have much to do with this. There really are only two ways of defining a recursive function:

• Suppose your language allows recursive function definitions; i.e., a function body can refer to the enclosing function, or the body of a function f can refer to a function g whose body refers to f. In this case, well, you just write it in the usual way.
• If your language forbids both of these, but it still has first-class functions and lambdas, then you can use a fixed-point combinator like the Y combinator. You write your function so that it takes as an extra argument a function that's meant to represent the recursive step; every place where you would recurse, instead you invoke that argument.

So for factorial, you write it like this:

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

The magic of the Y combinator is that it constructs the recurse function that would be fed to factorial-step.