Functional Programming
8. Tail Recursion



8.1 What is tail recursion?

Suppose that a function f is defined in terms of an expression E that mentions f. Informally we say that f is recursively defined. (This is not an all-inclusive definition, functions could be defined in terms of each other, and thus also be mutually recursive).

Also informally, we say a function f is tail recursive if the expression E doesn't do any more work after invoking f. The Scheme/Racket reference has a more formal definition of tail recursive, dealing especially with the special forms like cond and if. Look at the definition of tail position in the language reference Section 1.1 Evaluation Model. But the main idea is that after f is called, the result value of f is the returned value of the function. Thus all the leaves of a tree of conditionals have to either not invoke f, be tail recursive in f, in order for the entire function to be tail recursive in f.

In the following code, the function rev is not tail recursive, since the invocation of rev is not in tail position (it is inside an append function invocation). But the helper function revt-r is tail recursive (because no further work is done after the revt-r invocation returns. (The special form if is not a function)

code/TailRecursion/Reverse.rkt

    #lang racket
     
    ; a version of reverse that is not tail-recursive and is also rather
    ; slow
    (define rev 
      (lambda (L)
        (if (null? L) L
            (append (rev (rest L)) (list (first L)))
            )))
     
    (rev '(1 2 3))
     
    ; a tail-recursive helper function revt-r for reverse that passes along an
    ; accumulator result R
     
    (define revt-r
      (lambda (L R)
        (if (null? L) R
            (revt-r (rest L) (cons (first L) R))
            )))
    (define revt (lambda (L) (revt-r L '())))
     
    (revt '(4 5 6))
Tail recursion is significant, because any tail-recursive program can be written as a loop.

8.2 Converting to tail-recursive form

Every function that is simply-recursive, can always be made tail recursive with the addition of suitable helper functions. By simply-recursive we mean that the recursion is linear: the current case of the problem is either a base case, or can be broken into exactly one smaller case. Recursion is performed on the smaller case, and then the results are combined to compute the current case.

All these simply-recursive functions can be expressed in a general form. The function fn defined below computes factorial using this pattern.

code/TailRecursion/LinearRecursion.rkt

    #lang racket
     
    ; this predicate is true if we are at the base case
    (define AtBase?
      (lambda (current-x) (<= current-x 1)))
     
    ; this function defines the result at the base case
    (define BaseCase
      (lambda (base-x) 1))
     
    ; this function breaks the current case into a smaller one
    (define Decomp
      (lambda (current-x) (- current-x 1)))
     
    ; this function says how to combine the current case and the result of
    ; the recursion on the smaller case into the result for the current case
    (define Combine
      (lambda (current-x smaller-result)
        (* current-x smaller-result)))
     
    ; here is the general definition of a function in terms of these 4 basic
    ; components
     
    (define fn
      (lambda (current-x)
        (if (AtBase? current-x) 
            (BaseCase current-x)
            (Combine current-x (fn (Decomp current-x)))    
         )
      )
    )


In this general form, the function is not tail recursive, because the recursion on fn is inside the Combine invocation. If you trace the execution of this function in the debugger, you will see stacked pending calls to Combine as in
(Combine 3 (Combine 2 (BaseCase 1)))


However, by observing that you can capture the work to be done after the recursive call returns in a closure, and then pass the closure down into the recursion, the function can be re-written in tail-recursive form.

code/TailRecursion/LinearTailRecursion.rkt

    #lang racket
     
    ; The problem with the general pattern is that there is work to be done
    ; after the recursion returns.  We can move the recursive call into tail
    ; position by also passing down into the recursion the work to be done.
     
    ; The helper function fn-r takes the current x value and an additional
    ; builder function cc whose job is to do the work that would have been 
    ; done on return.
     
    ; The builder function cc has a single argument, smaller-result, which is the 
    ; result from the recursion that cc is associated with.
     
    ; Note how fn-r is in tail-position
     
    (define fn-r
      (lambda (current-x cc)
        (if (AtBase? current-x) 
            ; when you get to the base case, you invoke the builder funtion
            ; to construct the result for the base case
            (cc (BaseCase current-x))
     
            ; if you are not a base case, you decompose into a smaller case,
            ; and also define a builder function that combines the current 
            ; case and the recursion result
            (fn-r (Decomp current-x) 
                  ; this combined the smaller-result and current-x, and then
                  ; "returns" that into the body of cc which is the next pending
                  ; computation.
                  (lambda (smaller-result) (cc (Combine current-x smaller-result)))
            )
         )
      )
    )
     
    ; the function is defined in terms of the helper and a builder that simply
    ; returns the final result.
    (define fn (lambda (current-x) 
        (fn-r current-x (lambda (smaller-result) smaller-result))
    ))
     
    ; you can take advantage of the default argument feature of racket
    ; to avoid the helper function.  If the cc argument is missing then
    ; the default identity function is used.
     
    (define fn-cc
      (lambda (current-x [cc (lambda (x) x)] )
        (if (AtBase? current-x)
            ; when you get to the base case, you invoke the builder funtion
            ; to construct the result for the base case
            (cc (BaseCase current-x))
     
            ; if you are not a base case, you decompose into a smaller case,
            ; and also define a builder function that combines the current
            ; case and the recursion result
            (fn-cc (Decomp current-x)
                  ; this combined the smaller-result and current-x, and then
                  ; "returns" that into the body of cc which is the next pending
                  ; computation.
                  (lambda (smaller-result) (cc (Combine current-x smaller-result)))
            )
         )
      )
    )
     


8.3 Converting tail-recursion to loop form

As a last step, we show how to convert the tail recursion into a loop for procedural languages that can create closures, such as Python and Perl. What is happening is that the loop is unrolling the recursion into a lambda expression that captures the work that is to be done after the recursive call. Thus, there is some sleight of hand going on here, where the stack is being replaced by a large nested lambda expression being built on the heap.

Removing Tail Recursion In Python
code/TailRecursion/LinearTailRecursionPython.py

    # we now do the same thing, but in Python, so we can show how the tail
    # recursion can be replaced by a goto (or its equivalent).
     
    # first the recursive decomposition as above
     
    def AtBase(x):
        return x <= 1
     
    def BaseCase(x):
        return 1
     
    def Decomp(x):
        return x - 1
     
    def Combine(x, rec_result):
        return x * rec_result
     
    def fn(x):
     
        if AtBase(x):
            return BaseCase(x)
        else:
            # note how fn is NOT in tail-recursive position since its results
            # are fed into Combine.
            return Combine(x, fn( Decomp(x) ))
     
    print("fn: ", fn(5), "\n")
     
    # now the tail recursive version
     
    def fn_r(x, cc):
        if AtBase(x):
            # apply the builder to the base case
            return cc(BaseCase(x))
        else:
            # fn_r is in tail recusive position, nothing uses its result
            return fn_r(Decomp(x), 
                # this is the new builder
                lambda smaller_result: cc(Combine(x, smaller_result))
                )
     
    def fn_cc(x):
        return fn_r(x, lambda y: y)
     
    print("fn_cc: ", fn_cc(5), "\n")
     
    # and finally we recode it into loop form, where cc and x are updated
    # on each loop
     
    def fn_loop(x):
     
        def cc(y):
            return y
     
        while not AtBase(x):
            print("in loop", x, cc)
     
            def cc(smaller_result, prev_cc = cc, prev_x = x):
                return prev_cc(Combine(prev_x, smaller_result))
            
            x = Decomp(x)
     
            print("lambda", cc, "on", x)
     
        print("done loop", x, cc, cc(BaseCase(x)), "\n")
        return cc(BaseCase(x))
     
    print("fn_loop: ", fn_loop(5), "\n")
     
    # print("fn_loop: ", fn_loop(3), "\n")
     
    # notes on lambda closures in Python, which are broken, so you need to use
    # inner def's instead.
     
    # http://math.andrej.com/2009/04/09/pythons-lambda-is-broken/
    # http://stackoverflow.com/questions/2295290/what-do-lambda-function-closures-capture-in-python
    # http://stackoverflow.com/questions/13355233/python-lambda-closure-scoping
    # http://stackoverflow.com/questions/6035848/python-closure-not-working-as-expected


Removing Tail Recursion In Perl
code/TailRecursion/LinearTailRecursionPerl.pl

    use strict;
    use warnings;
     
    # we now do the same thing, but in Perl, so we can show how the tail
    # recursion can be replaced by a goto.
     
    sub AtBase {
        my ($x) = @_;
        return $x <= 1;
        }
     
    sub BaseCase {
        my ($x) = @_;
        return 1;
        }
     
    sub Decomp {
        my ($x) = @_;
        return $x - 1;
        }
     
    sub Combine {
        my ($x, $rec_result) = @_;
        return $x * $rec_result;
        } 
     
    sub fn {
        my ($x) = @_;
        my $result;
     
        if ( AtBase($x) ) {
            return BaseCase($x);
            }
        else {
            return Combine($x, fn( Decomp($x) ));
            }
        }
     
    print "fn: ", fn(5), "\n";
     
    sub fn_r {
        my ($x, $cc) = @_;
        if ( AtBase($x) ) {
            # apply the builder to the base case
            return $cc->(BaseCase($x));
            }
        else {
            return fn_r(Decomp($x), 
                # this is the new builder
                sub { my ($smaller_result) = @_; 
                      $cc->(Combine($x, $smaller_result));
                    }
                );
            }
        }
     
    sub fn_cc {
        my ($x) = @_;
        return fn_r($x, sub { my ($x) = @_; return $x; });
        }
     
    print "fn_cc: ", fn_cc(5), "\n";
     
    sub fn_loop {
        my ($x) = @_;
     
        my $cc = sub { my ($x) = @_; return $x; };
     
    fn_invoke:
        if ( AtBase($x) ) {
            return $cc->(BaseCase($x));
            }
        else {
            my $old_x = $x;
            my $old_cc = $cc;
     
            $x = Decomp($x);
            $cc = sub { my ($smaller_result) = @_; 
                      $old_cc->(Combine($old_x, $smaller_result));
                    };
     
            goto fn_invoke;
            }
        }
     
    print "fn_loop: ", fn_loop(5), "\n";
8. Tail Recursion
Notes on Functional Programming / Version 2.10 2014-02-24