CS 2360 Lecture 4: January 17

Recursion & Recursion Templates

Touretzky Reading: Chapter 8

Touretzky Exercises: 8.4, 8.5, 8.9, 8.12, 8.17-19,8.22, 8.26, 8.27-28, 8.31,8.45 8.61,8.32, 8.34-35,8.40-41,8.44,8.48-49,8.58, 8.63

Before doing 8.44, be sure you understand how CONS works for lists that are not well formed (i.e. dotted pairs). More info on this can be found in section 2.17. I've selected a lot of exercises from this section because it is so important! Be sure that as you work these exercises that you keep in mind which section of Turetzky they are in so you know which recursion template to apply.

Administrivia

I think the Dragon examples in Touretzky chapter 8 are a little childish, but, if they help you understand this stuff, great. If you feel like they stink, just ignore them.
My s-expressions definition the other day was wrong. An s-expression can be either:
- An atom (symbol)
- A list of s-expressions separated by spaces and delimited by parenthesis.
Sorry about that mistake.
Also, in class I mentioned the function =. This function is the best equality predicate if your numbers are of different types. E.g. -> (equal 3 3.0) NIL -> (eql 3 3) T -> (eql 3 3.0) NIL -> (= 3 3.0) T
Make sure to check the home page for what *exactly* you should turn in to your TAs for assignment 1.

Recursion

I like the definition of how to define a recursive function by Turetzky. (If you'd like see Kurt's definition, its in his third lecture in the Recursion section.) Turetzky has "three rules of recursion" in section 8.8. They are:

Know when to stop.
Decide how to take one step.
Break the journey down into that step plus a smaller journey.

An example may be of some use here: (defun contains-number-p (the-list) (cond ((null the-list) nil) ((numberp (car the-list)) t) (t (contains-number-p (cdr the-list))))) This function returns T or NIL based on whether or not the list it is given as input in the-list contains any numbers. It uses the built-in NUMBERP to test for "numberness."

Note how the COND clauses in contains-number-p correspond to these cases. It could also be written as:

(defun contains-number-p (the-list) (if (null the-list) nil (if (numberp (car the-list)) t (contains-number-p (cdr the-list)))))

Here's one of Kurt's examples:

(defun my-member (input-item input-list) (cond ((null input-list) nil) ((eql input-item (first input-list)) T) (T (my-member input-item (rest input-list)) This function determines if the input item is a member of the input-list. What does this function return in the false case? What about the true case? This is why non-NIL is defined to be true.

Tail Recursion

Consider this very simple recursive definition of the factorial for integers:

(defun factorial (n) (cond ((equal n 0) 1) (T (* n (factorial (- n 1))))))

What does the stack look like during the evaluation of (factorial 4)? Here is a listing of the stack frames which is something of a representation of this: -> ;;; Evaluate factorial | 2 Enter FACTORIAL 4 | 3 Enter FACTORIAL 3 | | 4 Enter FACTORIAL 2 | | 5 Enter FACTORIAL 1 | | | 6 Enter FACTORIAL 0 | | | 6 Exit FACTORIAL 1 | | 5 Exit FACTORIAL 1 | | 4 Exit FACTORIAL 2 | 3 Exit FACTORIAL 6 | 2 Exit FACTORIAL 24 24
This is O(N) usage in space and is called a "linear recursive process".
This is the process not the function.
This is bad; could outstrip available memory.
This is because there is work being done outside the recursive call so some storage is required to handle the substitution.

Tail Recursion can be used to allow the system to use only O(1) space. This is because the final recursive call is just substituted for the current call (there is no need to save state). Many lisp compilers/interpreters implement this optimization when they see it. Here is a new version of the factorial function: (defun factorial (n) (factorial-iterative 1 1 n)) (defun factorial-iterative (product counter max-count) (cond ((> counter max-count) product) (T (factorial-iterative (* counter product) (+ counter 1) max-count)))) What is this doing?

We introduced a helper function to get things started out right.
Note that the values of the parameters in each call are effectively the loop variables you might see in a procedural language's while construct and the first test of the COND is the termination condition. The final part of the COND is the body. Consider: WHILE (> counter max-count) DO product := (* counter product); counter := (+ counter 1) END (* WHILE *) Do you see how the parameters effectively are being used as looping variables?
This is a "linear iterative process" although it is still defined recursively.
We can do this because there is nothing to "pass back" that requires more computations; it is a pure substitution.

Although we told you that you shouldn't think about whether your program runs fast or not, this is a real problem in big lisp programs because many linear recursive processes could swamp available memory and leave you unable to perform your computation.

All this talk about Lisp being slow is mostly rhetoric, as we can see here. Lisp offers you the choice to do things the simple way or use a little brain power and do it the fast way.

Recursion Templates

Turetzky claims that once you learn the templates you can do almost any recursive functions with the these templates.
I'd suggest thinking about the problems rather than just blindly trying to use the templates as given. However they can be valuable in giving you ideas, and understanding other peoples code.

Augmenting Recursion

Our first factorial example from before was an augmenting recursion: (defun factorial (n) (cond ((equal n 0) 1) (T (* n (factorial (- n 1)))))) This is type of recursion I usually think of first when trying to solve a problem. Somehow to me it seems to have the cleanest type of implementation.

This is called augmenting recursion because we are adding something to the result through each iteration. Further, we really aren't doing anything else in the way of computation. Can you see how to write a function to compute the length of a list this way?

List Consing Recursion

This is a special type of augmenting recursion where we add a cons cell at each step of the way. Here is an example: (defun laugh (number) (laugh-helper number 0 )) (defun laugh-helper (number target) (if (equal target number) nil (cons 'ha (laugh-helper number (+ target 1))))) And when you run it you get: > (laugh 2) (HA HA) > (laugh 0) NIL > (laugh 5) (HA HA HA HA HA) Note that although I used an IF conditional, it's still augmenting recursion. I find that this type of recursion tends to be most needed when you are constructing a data structure from "scratch" or based on some "specification" as we were above. Another common use is the transformation of one data-structure into another.

Kurt has an excellent example of list-consing recursion in his notes involving the function APPEND; click here to go to Kurt's lecture on recursion templates. A crucial thing you should pick up from this is that recursion postpones computation.

Conditional Augmenting Recursion

This is yet another version of the augmenting recursion template, mostly used in the transformation of one structure into another. Consider: (defun i-hate-zero (input-list) (cond ((null input-list) nil) ((= (car input-list) 0) (i-hate-zero (cdr input-list))) ( t (cons (car input-list) (i-hate-zero (cdr input-list)))))) This is effectively "selecting" all the zeroes and reconstructing the rest. The result of a "selection" here is a removal, but it might be replacement with some other value, etc.

Single Test Tail Recursion

This is the magic bullet that ups our performance and bounds our memory usage. Our improved version of the fibonacci is an example an example of this. (defun factorial (n) (factorial-iterative 1 1 n)) (defun factorial-iterative (product counter max-count) (cond ((> counter max-count) product) (T (factorial-iterative (* counter product) (+ counter 1) max-count)))) This is a fairly general type of computation, I really can't mention specific cases where I see it used more often.

Multiple Test Tail Recursion

This type of recursion is frequently used in searching some data structure for a value. This is not its only use, but this might be a clue.

Here is a double tail test recursive function:

(defun contains-number-p (the-list) (cond ((null the-list) nil) ((numberp (car the-list)) t) (t (contains-number-p (cdr the-list))))) Its our contains-number-p friend from before. Why is there no helper function needed here? Because the the-list is effectively all the temporaries we need, we don't need to introduce new ones.

Tree Recursion

This is probably the one that most people have problems with. I've stolen this example straight from Kurt's lecture on recursion templates if you would like to check out his discussion of it.

Here is an example of Tree recursion in action:

>(flatten '(a (b (c) d (e) f))) (A B C D E F)

This function should remove all layers (levels) of parenthis; it should produce a flat list.
There are three cases here:
- Flattening the first element of the list (might be atom or list)
- Flattening the rest of the list
- Combining the first two parts into one flat list (This is APPEND.)

This type of recursion has several names:

Multiple Recursion: This is because each call to flatten is replaced by multiple calls to flatten. (Think about the big-O of this!)
Tree Recursion: The structure we are flattening is really tree; the flatten is pre-order traversal.
CAR/CDR recursion: This is because we recursively call the flatten function on the car and cdr.

Here is the function that makes it work: (defun flatten (my-list) (cond ((null my-list) nil) ((atom my-list) (list my-list)) (T (append (flatten (first my-list)) (flatten (rest my-list))))))

Back To The CS2360 Home Page

Ian Smith (iansmith@cc.gatech.edu)