Tail Recursion

• Def: a tail recursive function is one for which additional computations do not follow recursive calls.
• It means that for each branch of the main conditional or for any given values of the parameters there must be at most one recursive call.
• The value returned by the recursive call is the result of the function.
• Usually a tail-recursive function can be easily transformed into an iterative one.
• Compilers can also optimize the code for such functions by using a single function space for the entire stack of recursive calls.

 
(defun last (L)
  (if (not (cdr L)) 
      (car L)
    (last (cdr L))))

(defun gcd (n m)
  (cond ((= n m) n)  ;a
        ((= n 0) m)  ;b
        ((= m 0) n)  ;c
        ((> n m) 
         (gcd (- n m) m)) ;d
        (t (gcd n (- m n)))))  ;e

Tail Recursion Transformation

• The terminating conditions are transformed into the continuation conditions for a loop by negation. If more than one base case is present, the continuation condition will link their negations with an "and" operator.
• The recursive calls are transformed into assignments of values to the variables. It will assign to any of the parameters that is different at the top and in the recursive call, the new value it takes in the recursive call.
• The returned value must replicate the base cases. If only one case is present, the function will return whatever the recursive version returns for it. If more than one are present, then after the loop we must test them again and return whatever the recursive version returns for each of these cases.

Example - Last

• The termination condition becomes the continuation condition for the loop. The negation of a negation just removes the "not".
• The recursive call is replaced by assigning to L the value of its cdr.
• The return value is whatever was returned in the base case.

(defun last (L)
  (while (cdr L)
    (setq L (cdr L)))
  (car L))

Example - gcd

• The termination condition n=m becomes the continuation condition n!=m. The same goes for the two others. Then we link them together with the “and”.
• The call gcd(n-m, m) can be resolved by assinging to n the value n-m and the same for the other one.
• After the loop we need to find out which of the base cases we ended up with and return the appropriate value.

(defun gcd (n m)
  (while (and (/= n m) (/= n 0) (/= m 0))
    (if (> n m) 
        (setq n (- n m))
      (setq m (- m n))))
  (cond ((= n m) n)
        ((= n 0) m)
        ((= m 0) n)))

Recursive Binary Search

(defun binary-search (A first last val)
  (if (> first last) -1
    (let ((mid (/ (+ first last) 2)))
      (cond
       ((= (elt A mid) val) mid)
       ((> (elt A mid) val)
        (binary-search A first 
                  (- mid 1) val))
       (t (binary-search A (+ mid 1)
                    last val))))))
(binary-search a 0 4 2); 1
(binary-search a 0 4 7) ; -1

Result of the Transformation

(defun binary-search-it (A first last val)
  (let ((mid (/ (+ first last) 2)))
    (while (and (<= first last)
                (not (= (elt A mid) val)))
      (if (> (elt A mid) val)
          (setq last (- mid 1))
        (setq first (+ mid 1)))
      (setq mid (/ (+ first last)
                   2)))
    (if (= (elt A mid) val) mid -1)))
(binary-search-it a 0 4 2) ; 1
(binary-search-it a 0 4 7) ; -1

Counter Example

(defun factorial (n)
  (if (< n 2) 1
    (* n (factorial (- n 1)))))

Converting to Tail-Recursive

• Some functions which are not tail-recursive can be written in the tail-recursive way.
• This involves adding some extra parameters to contain the additional operations and information required after the recursive call.
• One of these parameters will compute and pass forward the result through the recursive calls, so that it can be directly returned when we reach the base case.
• The number of extra parameters needed is usually at least as much as the number of recursive calls needed by the result.
• The initial value of the extra parameters is taken from the base cases.

Tail-Recursive Factorial

(defun fact (n result)
  (if (< n 2)
      result
    (fact (- n 1) (* n result))))

(fact 6 1)  ; => 720

Recursive Fibonacci
Usual recursive implementation: non tail recursive because the results of two recursive calls must be added to obtain the result.

(defun fib1 (n)
  (if (< n 2)
      1
    (+ (fib1 (- n 1)) (fib1 (- n 2)))))
(fib1 4) ; => 5

(defun fib2 (n f1 f2)
  (if (< n 2)
      f1
    (fib2 (- n 1) (+ f1 f2) f1)))
(fib2 5 1 1) ; => 8

Simple Transformation for Functions with a Single Recursive Call

Top-Down Transformation
When there's only one recursive call involved in a computation (factorial), and when the computation is a simple associative operation (+, *) -> store the value in a local variable.

(defun factorial (n)
  (let ((f 1))
    (while (>= n 2)
      (setq f (* f n))
      (setq n (- n 1)))
    f))

Bottom-Up Transformation
Starting from the base case going up. A local variable (f) stands in place of the value returned by recursive calls.

(defun factorial (n)
  (let ((f 1) (i 2))
    (while (<= i n)
      (setq f (* f i) i (+ i 1)))
  f))

One Recursive Call

(defun factorial1 (n)
  (let ((st ()) (r 1) (ln n))
    (push ln st)
    (while st
      (cond
       ((>= ln 2)
        (setq ln (- ln 1))
        (push ln st))
       (t (setq r (* r (pop st))))))
    r))

Second Example
f(n) = 2 n² + 3 f(n-1),    f(1) = 2

(defun f (n)
  (if (= n 1) 2
    (+ (* 2 n n)
       (* 3 (f (- n 1))))))

Iterative BU Version

(defun iter-f (n)
  (let ((f 2) (i 2))
    (while (<= i n)
      (setq f (+ (* 2 i i)
                 (* 3 f)))
      (setq i (+ i 1)))
    f))

Iterative Version

(defun f (n)
  (let ((st ()) (r 2) (ln 0))
    (push n st)
    (while st
      (cond
       ((> n 1)
        (setq n (- n 1))
        (push n st))
       (t (setq ln (pop st))
          (setq r (+ (* 2 ln ln)
                     (* 3 r))))))
    r))