Lecture 5 -- Recursion examples Recursion templates Today, in the aftermath of Hurricane Opal, we spent our time together in small groups, working out recursive solutions to small problems. Each of these solutions served as a new example of a standard recursive form. That is, while each solution used recursion, each was slightly different in either the way the test was done, what the recursive call looked like, or how the results were combined together. We can think of each of these different forms as "recursion templates," and once you get the hang of how they're different and how they're similar, you'll probably find it easy to solve problems recursively by going to the appropriate template and plugging in the right stuff. (The templates come from "Common LISP: A Gentle Introduction to Symbolic Computation" by David S. Touretzky.) Augmenting recursion The first example is called "augmenting recursion". This refers to the fact that in the COND clause which contains the recursive call, there's work being done outside the recursive call itself. This work augments the recursion, and in our substitution model of evaluation, that's what makes the program stack grow each time the recursive call is made. That in turn gives us that linear (or worse) recursive process shape that we've looked at before. We've seen augmenting recursion when we constructed our first factorial function. Here's another example of augmenting recursion. It's our own version of LISP's "length" function, which returns the number of top-level elements of a list: (defun my-length (my-list) (cond ((null my-list) 0) (T (+ 1 (my-length (rest my-list)))))) Single-test tail recursion As you'll recall, tail recursion is that magic solution which allows us to use the elegance and readability of a recursively-defined procedure while gaining none of the nasty memory usage associated with augmenting recursion. Furthermore, some LISP systems recognize tail recursion and optimize the object code to run as a simple loop, so we get better speed and bounded memory usage. Neat, huh? In this example, we constructed the tail recursive version of the my- length function, and we used a helping function to set it all up: (defun my-length (my-list) (my-length-tr my-list 0)) (defun my-length-tr (my-list counter) (cond ((null my-list) counter) (T (my-length-tr (rest my-list) (+ 1 counter))))) Multiple-test tail recursion In LISP, the function "nthcdr" takes two arguments, an integer and a list. The "nthcdr" function then counts down the number of list elements indicated by the integer (by taking successive "rest"s or "cdr"s) and returns the list without those first elements. For example: ? (nthcdr 0 '(a b c)) (A B C) ? (nthcdr 2 '(a b c)) (C) ? Here's our own version of "nthcdr": (defun my-nthcdr (integer my-list) (cond ((null my-list) nil) ((eql integer 0) my-list) (T (my-nthcdr (- integer 1) (rest my-list))))) There are at least three interesting things to note here. First, we used tail recursion again. In fact, it just seemed like the obvious thing to do. Second, we use more than one test for termination. This is fairly common, and occurs with augmenting recursion as well as tail recursion. Finally, note that there's no helping function in this example of tail recursion. Because we can use the argument "integer" as a counter, we don't need to introduce any new arguments to be used as variables to keep track of intermediate results. So it's safe to say that we don't always need a helping function to get tail recursion going. List-consing recursion (a type of augmenting recursion) LISP's "append" function is a very commonly used function. It takes two lists as arguments and joins them together: ? (append '(a b) '(c d)) (A B C D) ? It's not immediately obvious how to implement this...it takes a little thought. Folks just sort of naturally try to go at it by getting to the last element of the first list and tacking it on to the second one, then somehow going backwards along the first list to tack on the previous element, and so on. But we need to take advantage of recursion here, along with the fact that as recursion postpones computations, those computations actually get performed in the reverse of the order in which they were postponed (last-in-first-out or LIFO). Thus, we don't really want to go to the end of the first list and work backward---we want to start with the first element of the first list and work forward, postponing our operations as we go. Another insight that is useful here is to think of some simpler operations that might get us this same result, it becomes a little more obvious. Consider that ? (cons 'a (cons 'b '(c d))) (A B C D) ? gets us the same result, and suddenly the light goes on: (defun my-append (my-list1 my-list2) (cond ((null my-list1) my-list2) (T (cons (first my-list1) (my-append (rest my-list1) my-list2))))) What makes this particular template of interest is the nature of the augmenting recursion. The computation being done outside of the recursive call is a "cons". In this case, the elements of the first list are being "cons"ed onto the second list, resulting in a new structure combining the two original structures. List consing recursion is a commonly-used way of constructing new structures from old ones. Conditional augmenting recursion The problem here is to implement our own version of LISP's "remove" function, which takes two arguments: some possible list element, and a list. If the possible list element is "eql" to any top-level element of the given list, then that element is effectively removed from the list. What is returned is the orginial list minus any elements that are "eql" to the possible list element. For example: ? (remove '(a b c) '((a b c) (d e f))) ((A B C) (D E F)) ? (remove 'a '(a b a c)) (B C) ? Note that while 'a is "eql" to 'a, '(a b c) is NOT "eql" to '(a b c). However, '(a b c) is "equal" to '(a b c). So how do we implement our own version of "remove"? The trick here is to look at each element of the list, and if that element is "eql" to our element to be deleted, we recursively call "remove" on the rest of the list, thereby discarding the element to be removed. What if they're not "eql" and we want to keep the element? Then we use list- consing recursion (remember...that's a form of augmenting recursion) to "cons" that element onto the recursive call of "remove" on the rest of the list. (Sometimes you feel like a "cons", sometimes you don't....) What we end up with is what's called conditional augmenting recursion, a commmon way of skipping over some elements and reconstructing with the others. This is another standard recursive template: (defun my-remove (element my-list) (cond ((null my-list) nil) ((eql element (first my-list)) (my-remove element (rest my-list))) (T (cons (first my-list) (my-remove element (rest my-list)))))) There's at least one other standard recursion template that's worth knowing intimately, and you'll see that one in the next set of notes. Copyright 1995 by Kurt Eiselt. All rights reserved. -- Kurt Eiselt Assistant Dean, Student Services College of Computing Georgia Institute of Technology Atlanta, GA 30332-0280 http://www.cc.gatech.edu/aimosaic/faculty/eiselt.html