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) ; => 5Transformed 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))