9

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.

day
  • 2,292
  • 1
  • 20
  • 23

3 Answers3

14

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.

C. K. Young
  • 219,335
  • 46
  • 382
  • 435
6

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!

John Clements
  • 16,895
  • 3
  • 37
  • 52
  • Well, I have already known this trick to do recursion. What I wonder is if a non-self-referring way using call/cc exists to define a recursive function, say your `factorial`. This is not a homework exercise! Thanks. – day Mar 29 '12 at 17:16
  • 1
    @plmday John's solution is already not self-referencing. What more would you need from `call/cc`? – Sam Tobin-Hochstadt Mar 29 '12 at 18:50
  • @SamTobin-Hochstadt Well, it is, `f` refers to itself, doesn't it? I wanna see how far we can go with `call/cc`, in particular, given its ability, can we employ it to simulate the usual or unusual way of defining a recursive function. – day Mar 29 '12 at 20:33
  • 2
    What do your mean by "refer to itself"? Self-reference in a (self-) recursive function definition is of this form: you have a function definition whose body contains an occurrence of an identifier that's lexically bound to the enclosing function itself. The definition of `factorial` that John provides does not have `factorial` appearing in the body, nor any identifier that's lexically bound to it. – Luis Casillas Mar 29 '12 at 21:49
  • Ah, OK, you are right. I mixed it with self-application. Thanks for clarifying it. – day Mar 30 '12 at 08:25
  • (After taking a look at oleg's post:) Yep, recursion without self-application: that *is* interesting. See, I knew there was an interesting question in there! – John Clements Mar 30 '12 at 18:38
2

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.

Luis Casillas
  • 29,802
  • 7
  • 49
  • 102