Lecture Notes on Tail Recursion and call/cc

Tail recursion

A function is said to be tail recursive when the recursive call is the last function invoked in the evaluation of the body of the function.

Example:

(define (Sumit ls) 
    (define (aux l c) 
        (if (null? l) 
            c 
            (aux (cdr l) (+ c (car l))))) 
  (aux ls 0))  

The function aux is tail recursive because after the recursive call there is nothing else left to do.

If we define the same function without tail recursion we get

(define (Sum l) 
    (if (null? l)  
        0 
        (+ (car l) (Sum (cdr l)))))  

Try and see by yourself what happens during the evaluation of Sum on a list, say (2 4 6 1 3). You need to leave a number of additions uncompleted until you reach the base case. When the base case is reached, all the additions can be made.
In a sense, you need a stack to remember what "remains to be computed".
Now, mimic the evaluation of Sumit on the same input. You need to remember nothing, since no operation is left to be computed.

Tail recursion, in a sense, correspond to the notion of iteration in functional programming (indeed you can translate tail recursive functions in an imperative language by using a simple loop. The translation of a non tail recursive function, instead, will definitely use a stack, or something equivalent.)

In the function aux (the local function of Sumit) the argument 'c' plays the role of an accumulator. In each recursive call a shorter list is passed to aux, while the accumulator is "extended" with the first element of the list. In a sense, each recursive call is like an iteration that modifies a variable, the accumulator, and the "assignment" of a new value to the accumulator is mimicked by passing the new value as second argument of the recursive call.

It is possible to provide iterative versions of all the functions, not always easily.

Let us see a few tail recursive versions of well known functions

(define (reverseiter ls)
  (letrec ((reverseiteraux ls lsaux)
              (if (null? ls)
                  '()
	          (reverseiteraux 
		         (cdr ls) 
			 (cons (car ls) lsaux))))
        (reverseiteraux ls '())))

(define (appenditer ls1 ls2)
  (letrec ((appenditeraux ls1 ls2 lsaux)
               (if (and (null? ls1) 
	                (null? lsaux))
                   ls2
                   (if (null? ls1)
                       (appenditeraux 
		            (reverseiter lsaux) 
			    ls2 
			    '())
                       (appenditeraux 
		            (cdr ls) 
			    ls2 
			    (cons (car ls1) 
			          lsaux) ) )))
        (appenditer ls1 ls2 '())))

In this definitions there is a "hidden" iterative imperative algorithm.
Tail recursion can be thought of as the functional counterpart of Iteration.

call/cc

We do not explain how these particular Scheme operator, and other similar operators in functional programming languages, works.
We just show an example of the sort problems these kind of operators have been devised for.

(define (Mt tree) 
  (if (emptytree? tree) 
      1 
      (if (= (label tree) 0) 
          0 
          (* (label tree) 
	     (Mt (rightchild tree)) 
	     (Mt (leftchild tree))))))  

The above function computes the product of all the nodes of a binary tree with numeric labels.

Let's assume we want to apply it to the following tree:

         2 
       /   \ 
      5     0 
     / \   / \ 
    3  6  1   7 
	       \ 
	        2 
 

The right subtree of the upper node 2 has the root with label zero. So the function Mt applied to this subtree returns 0 as result. This means that the product of all the nodes of the tree will be also 0, by the property of multiplication. However, the interpreter proceeds in the computation, evaluating also (Mt (leftchild tree)), even if such evaluation is completely useless. There is no way to prevent this waste of computation if you do not use call/cc or something similar since, even if at a certain point you could stop the computation, you are sort of "obliged" to complete the recursive calls present on the "stack".
In cases like our example, the use of the operator call/cc enables you to stop the computation as soon as we meet a 0, by "removing" all that is still on the "stack".
In a sense call/cc enables you to perform a sort of "go to" or "exit"; in a sense, it stops the computation and empties the stack.