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?

  • 1
    First thought: This might work for all singly recursive functions, but I'd be surprised if it worked for functions that make multiple recursive calls, since that would imply, e.g., that you could implement quicksort without needing $O(\log n)$ stack space. (Existing efficient implementations of quicksort generally make 1 recursive call on the stack, and turn the other recursive call into a tail-call that can be (manually or automatically) turned into a loop.) – j_random_hacker Nov 23 '16 at 15:08
  • Second thought: Choosing b to be a power of 2 shows that initially setting product to 0 isn't quite right; but changing it to 1 doesn't work when b is odd. Maybe you need 2 different accumulator parameters? – j_random_hacker Nov 23 '16 at 15:13
  • 3
    You haven't really defined a transformation of a non tail recursive definition, adding some result parameter and using it for accumulation is pretty vague, and hardly generalizes to more complex cases, e.g. tree traversals, where you have two recursive calls. A more precise idea of "continuation" exists though, in which you do part of the work, and then allow a "continuation" function to take over, receiving as a parameter the work you have done so far. It is called continuation passing style (cps), see en.wikipedia.org/wiki/Continuation-passing_style. – Ariel Nov 23 '16 at 15:15
  • 4
    These slides fsl.cs.illinois.edu/images/d/d5/CS422-Fall-2006-13.pdf contain a description of the cps transformation, in which you take some arbitrary expression (possibly with function definitions with non tail calls) and transform it to an equivalent expression with only tail calls. – Ariel Nov 23 '16 at 15:16
  • @j_random_hacker Yes, I can see that my "converted" procedure is in fact wrong... – nalzok Nov 23 '16 at 16:31
up vote 8 down vote accepted

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.

  • it's a bit confusing when in the "TCO" subsection, when you say "tail-call optimized" you actually mean "with constant memory usage". That the dynamic memory usage is not constant still doesn't negate the fact that the calls are indeed tail and there is no unbounded growth in the stack usage. SICP calls such computations "iterative", so saying "though it's TCO, it's still doesn't make it iterative" might have been a better wording (for me). – Will Ness Dec 22 '17 at 10:59
  • @WillNess We still have a call stack, it's just represented differently. The structure doesn't change just because we are using the heap, rather than the hardware stack. After all, there are plenty of data structures based on dynamic heap memory that have "stack" in their name. – Nathan Davis Dec 23 '17 at 2:31
  • the only point here is that some languages have hardwired limits to using the call stack. – Will Ness Dec 23 '17 at 13:08

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.