Lisp Recursion Examples, Tail Recursion

Using Cond with Recursion

1. (defun mylength (lst)

(if (null lst)

0

(+ 1 (mylength (rest lst)))))

2. With tail recursion (see p. 75):

(defun mylength (lst)

(mylength-aux lst 0))

(defun mylength-aux (lst len)

(if (null lst)

len

(mylength-aux (rest lst) (+ 1 len))))

3. (defun my-exp (base exp)

(if (= exp 0)

1

(* base (my-exp base (- exp 1)))))

4. With tail recursion:

(defun my-exp (base exp)

(my-exp-aux base exp 1))

(defun my-exp-aux (base exp product)

(if (= exp 0)

power

(my-exp-aux base (- exp 1) (* base product))))

5. (defun fibonacci (n)

(if (or (= n 0) (= n 1))

1

(+ (fibonacci (- n 1))

(fibonacci (- n 2)))))

With cond:

(defun fibonacci (n)

(cond ((= n 0) 1)

((= n 1) 1)

(t (+ (fibonacci (- n 1))

(fibonacci (- n 2))))))