Tail Call - Example Programs

Example Programs

Take this Scheme program as an example:

;; factorial : number -> number ;; to calculate the product of all positive ;; integers less than or equal to n. (define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))

This program is not written in a tail recursion style. Now take this Scheme program as an example:

;; factorial : number -> number ;; to calculate the product of all positive ;; integers less than or equal to n. (define (factorial n) (let fact ( ) (if (zero? i) acc (fact (- i 1) (* acc i)))))

The inner procedure fact calls itself last in the control flow. This allows an interpreter or compiler to reorganize the execution which would ordinarily look like this:

call factorial (3) call fact (3 1) call fact (2 3) call fact (1 6) call fact (0 6) return 6 return 6 return 6 return 6 return 6

into the more efficient variant, in terms of both space and time:

call factorial (3) call fact (3 1) replace arguments with (2 3), jump to "fact" replace arguments with (1 6), jump to "fact" replace arguments with (0 6), jump to "fact" return 6 return 6

This reorganization saves space because no state except for the calling function's address needs to be saved, either on the stack or on the heap, and the call stack frame for fact is reused for the intermediate results storage. This also means that the programmer need not worry about running out of stack or heap space for extremely deep recursions. It is also worth noting, in typical implementations, the tail recursive variant will be substantially faster than the other variant, but only by a constant factor.

Some programmers working in functional languages will rewrite recursive code to be tail-recursive so they can take advantage of this feature. This often requires addition of an "accumulator" argument (acc in the above example) to the function. In some cases (such as filtering lists) and in some languages, full tail recursion may require a function that was previously purely functional to be written such that it mutates references stored in other variables.

An example in pseudo-C follows. Suppose we have the following functions:

int a(int x, int y) { foobar(x, y); return b(x + 1, y + 2); } int b(int u, int v) { foobar(u, v); return u + v; }

Function a can be changed to:

int a(int x, int y) { foobar(x, y); b:u = a:x + 1; b:v = a:y + 2; jump b; }

There are possible aliasing problems but this is the basic idea.