The Marker
Exercises
Understanding recursion
To see if a recursive function dose what it's supposed to, all you have to ask is, does it cover all cases? For example, here is a recursive function for finding the length of a list
(defun len(lst)
(if (null lst)
0
(+ 1 (len (cdr lst)))))
We can assure overselves that this function is correct by verifying two things:
1. That it works for lists of length 0.
2. Given that it works for lists of length n, that it also works for lists of length n+1.
If we can establish both points, then we know that the function is correct for all possible lists.
Our definition obviously satisfies the first point: if lst is nil, the function immediately returns 0. Now suppose that the function works for lists of length n. We give it a list of length n+1. The definition says that the function will return the len of the cdr of this list, plus 1. The cdr is a list of length n. We know by our assumption that its len is n. Thus the len of the whole list is n+1
This is all we need to know. The secret of understanding recursion is a lot like the secret of dealing with parentheses.
How do you see which parentheses matches which?
You don't have to.
How do you visualize all those invocations?
You don't have to.
Check two lists equality
(defun lists-equal (x y)
(or (eql x y)
(and (consp x)
(consp y)
(lists-equal (car x) (car y))
(lists-equal (cdr x) (cdr y)))))
Show Squares
(defun show-squares (i end)
(format t "~A ~A~%" i (* i i))
(if (> i end)
'done
(show-squares (+ i 1) end)))
>>(show-squares 2 3)
2 4
3 9
4 16
DONE