How would I go about making this tail-recursive?

Question

I have this code:

(define (prog1 x y)
    (let ([rel (related x y)])
      (cond
        [(null? rel) (list x)]
        [else (cons x (map (lambda (d) (prog1 (neighbour d) y)) rel))])))

What I want to do is try and make it tail-recursive. I know that I need to do something like:

(define (prog1 x y)
  (prog1-iter x y `()))

(define (prog1-iter x y acc)
  (...
   ))

But I am unsure how to go from my code to this code... I think it's because the original has a map in it and I am unsure how to incorporate this into an prog1-iter. Could someone point me in the correct direction!

Answer 1

Tail-recursion is easy to write for things that are inherently iterative. Your function potentially calls itself many times, so it is not going to be simple. Nevertheless, any program can be made iterative (e.g. your computer is a giant iterative machine), so it can be done.

First of all, your function is not directly recursive (i.e. prog1 does not directly call itself). Rather, prog1 calls map, which then calls the lambda you gave it (perhaps multiple times), which then calls prog1; so it is indirect. The call to map is not a tail call; the call from map to the lambda is certainly not a tail call (it may need to call it more than once); and the call from the lambda to prog1 is a tail call.

Therefore, I am not sure what exactly you require when you ask it to be "tail-recursive". Do you want each call in the chain of calls from prog1 to itself to be a tail-call? Or do you want to make every call in the program a tail call? There exist "tail-recursive" versions of map, but they are only "tail-recursive with respect to calls from map to map, and not calls to the mapping function, so they are not useful for your case.

The general method to make every call in a program a tail call is called continuation-passing style. Basically, every function takes an additional function argument, the "continuation". Instead of making a non-tail call to a function, you instead make a tail call to it, and pass it a continuation specifying how to process the results of the function call. Basically, the continuation would encompass the "rest of" the original function after the non-tail call, and it would take in the "return result" of the original non-tail call as an argument. I will leave it as an exercise how to convert your program to CPS.