Recursion

June 8, 2008 | Filed Under Common Lisp - Touretzky 

———————————————————
Chapter 8
———————————————————

Recursion:

Double-tail recursion returns one of two results:
(DEFUN anyoddp (x)
(COND ((null x) NIL)
((oddp (first x)) T)
(T (anyoddp (rest x)))))

Single-tail recursion returns one result:
(DEFUN find-first-atom (x)
(COND ((atom x) x)
(T (find-first-atom (rest x)))))

Augmenting recusion loops using the result to build the final answer:
(DEFUN fib (x)
(COND ((NULL x) 0)
(T (+ x (fib (- x 1))))))

List consing recursion - CONSing the result of a recursion into a final list:
(DEFUN square-list (x)
(COND ((null x) NIL)
(T (CONS
(* (first x) (first x))
(square-list (rest x)))))
(square-list ‘(1 2 3 4)) -> (1 4 9 16)

Simultaneous recursion on multiple variables:
(DEFUN my-nth (n lst)
(COND ((zerop n) (first lst))
(T (my-nth (- n 1) (rest lst)))))
(my-nth 2 ‘(a b c d e)) -> c

Conditional Augmentation - tests for a property and uses the result of that test for the base of the recursion, or skips to continue the recursion:

(DEFUN extract-symbols (x)
(COND ((null x) nil)
((symbolp (first x))
(cons (first x)
(extract-symbols (rest x)))
(T (extract-symbols (rest x)))))

(extract-symbols ‘(1 bear and 2 girls)) -> (bear and girls)

CAR/CDR recursion - used to traverse a list of lists (the lists may be uneven - ‘(1 (girl and) (2 . bears)))

(DEFUN find-number (x)
(COND ((numberp x) x)
((atom x) nil)
(T (or (find-number (car x))
(find-number (cdr x))))))

Keeps going until it finds a number to return.

Helping functions:
A function like (COUNT-UP 5) -> (1 2 3 4 5) uses recursion, but is more difficult than COUNT-DOWN, as it must keep track of both the target number, and the number of iterations. Use a helper function:

(DEFUN COUNT-UP (x)
(COUNT-UP-RECURSIVELY 1 x))

(DEFUN COUNT-UP-RECURSIVELY (i n)
(COND ((equal i n) i)
(T (LIST i (count-up-recusively (+ i 1) n)))))

Comments