Dana Vrajitoru
C311 Programming Languages

Tail Recursion

Tail Recursion

 
(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

Example - Last

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

Example - gcd

(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)))))
It's not a tail recursive function because the result of the function call must be multiplied afterwards with n.

Converting to Tail-Recursive

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
Transformed into a tail-recursive function:
(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 n2 + 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))