Is this a generic way to convert any recursive procedure to tail-recursion?

Question

It seems that I've found a generic way to convert any recursive procedure to tail-recursion:

1. Define a helper sub-procedure with an extra "result" parameter.
2. Apply what would be applied to the procedure's return value to that parameter.
3. Call this helper procedure to get started. The initial value for the "result" parameter is the value for the exit point of the recursive process, so that the resulting iterative process starts from where the recursive process starts to shrink.

For example, here is the original recursive procedure to be converted (SICP exercise 1.17):

(define (fast-multiply a b)
  (define (double num)
    (* num 2))
  (define (half num)
    (/ num 2))
  (cond ((= b 0) 0)
        ((even? b) (double (fast-multiply a (half b))))
        (else (+ (fast-multiply a (- b 1)) a))))

Here is the converted, tail-recursive procedure (SICP exercise 1.18):

(define (fast-multiply a b)
  (define (double n)
    (* n 2))
  (define (half n)
    (/ n 2))
  (define (multi-iter a b product)
    (cond ((= b 0) product)
          ((even? b) (multi-iter a (half b) (double product)))
          (else (multi-iter a (- b 1) (+ product a)))))
  (multi-iter a b 0))

Can someone prove or disprove this?

Answer 1

Your description of your algorithm is really too vague to evaluate it at this point. But, here are some things to consider.

CPS

In fact, there is a way to transform any code into a form that uses only tail-calls. This is the CPS transform. CPS (Continuation-Passing Style) is a form of expressing code by passing each function a continuation. A continuation is an abstract notion representing "the rest of a compuation". In code expressed in CPS form, the natural way to reify a continuation is as a function that accepts a value. In CPS, instead of a function returning a value, it instead applies the function representing the current continuation to the being "returned" by the function.

For example, consider the following function:

(lambda (a b c d)
  (+ (- a b) (* c d)))

This could be expressed in CPS as follows:

(lambda (k a b c d)
  (- (lambda (v1)
       (* (lambda (v2)
            (+ k v1 v2))
          a b))
     c d))

It's ugly, and often slow, but it does have certain advantages:

• The transform can be completely automated. So there's no need to write (or see) the code in CPS form.
• Combined with thunking and trampolining, it can be used to provide tail-call optimization in languages that do not provide tail-call optimization. (Tail-call optimization of directly tail-recursive functions can be accomplished via other means, such as converting the recursive call into a loop. But indirect recursion is not as trivial to convert in this manner.)
• With CPS, continuations become a first-class objects. Since continuations are the essence of control, this enables virtually any control operator to be implemented as a library without requiring any special support from the language. For example, goto, exceptions, and cooperative threading can all be modeled using continuations.

TCO

It seems to me that the only reason to be concerned with tail-recursion (or tail-calls in general) is for the purposes of tail-call optimization (TCO). So I think a better question to ask is "does my transform yield code that is tail-call optimizable?".

If we once again consider CPS, one of its characteristics is that code expressed in CPS consists solely of tail-calls. Since everything's a tail-call, we don't need to save a return-point to the stack. So all code in CPS form must be tail-call optimized, right?

Well, not quite. You see, while it might appear that we have eliminated the stack, all we have done is merely change the way we represent it. The stack is now part of the closure representing a continuation. So CPS doesn't magically make all our code tail-call optimized.

So if CPS can't make everything TCO, is there a transform specifically for direct recursion that can? No, not in general. Some recursions are linear, but some are not. Non-linear (e.g., tree) recursions simply must maintain a variable amount of state somewhere.