Recursion Examples

1. (defun fibonacci (n)

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

1

(+ (fibonacci (- n 1))

(fibonacci (- n 2)))))

>(fibonacci 1)

1

>(fibonacci 2)

2

>(fibonacci 3)

3

>(fibonacci 4)

5

2. Version 1:

(defun count-elements (lst)

(if (endp lst)

0

(+ 1 (count-elements (rest lst)))))

Version 2:

(defun count-elements (lst)

(count-elements-aux 1 0))

(defun count-elements-aux (1 result)

(if (endp lst)

result

(count-elements-aux (rest lst) (+ 1 result))))

OR: (cond ((endp lst) result)

(t (count-elements-aux (rest lst) (+ 1 result))))

>(count-elements '(fast computers are nice))

4

>(count-elements '(fast computers (are nice)))

3

3. (defun count-atoms (lst)

(cond ((null lst) 0)

((atom lst) 1)

(t (+ (count-atoms (first lst))

(count-atoms (rest lst))))))

>(count-atoms '(sqrt (expt x 2) (expt y 2)))

7