# Class 06: Recursion with Lists

Back to Conditionals. On to Numeric Recursion.

Held: Thursday, 29 January 2004

Summary: Today we investigate recursion over lists with a number of experiments.

Related Pages:

Assignments:

Notes:

• Don't forget the cool convo right after this class. Extra credit for attending.
• Don't forget the equally cool panel tonight at 7:30 in the South Lounge. Extra credit for attending.
• Extra credit is generally 1/2 point per event and is capped at 3 points.

Overview:

## Recursion Basics

• Recursion is Scheme's primary mechanism for repetition.
• Key ideas:
• Call the same procedure on a smaller parameter.
• Use that partial result to compute the final result.
• Natural to Mathematicians. For example,
```0! = 1
n! = n * (n-1)!
```
• To write recursive procedures you need to think about
• How to identify the base case
• What value to use in the base case (Make sure you get the right type!)
• How to simplify
• What to do with result of recursive call

## Patterns of Recursion in Lists

• I find it useful to think about the pattern one uses to design certain kinds of procedures.
• Here's the pattern of a typical recursive procedure:
```(define proc
(lambda (val)
(if (base-case-test)
(base-case val)
(combine (partof val)
(proc (update val))))))
```
• When the value you're working with is a list and your base case is the null list, the form is somewhat simpler:
```(define proc
(lambda (lst)
(if (null? lst)
null-case
(combine (onestep (car val))
(proc (cdr val))))))
```
• You may even find that there are some boolean procedures that don't even need an `if`. For example, here's one implementation of member that works on the principle that `val` is a member of `lst` if the list is not empty and `val` is the first element of `lst` or `val` is a member of the remainder of `lst`.
```(define member?
(lambda (val lst)
(and (not (null? lst))
(or (equal? val (car lst))
(member? val (cdr lst))))))
```

## Designing Case Cases

• The biggest problem I see in recursive procedure design is the choice of base case.
• If it returns numbers, your base case should be a number.
• If it returns lists, your base case should be a list (often null).
• If it returns some other type of value, your base case should be that type of value.
• You should also make sure to have a base case. (Scheme is funny when you don't return a value and then try to use it.)

## History

Back to Conditionals. On to Numeric Recursion.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Fri May 7 09:43:05 2004.
The source to the document was last modified on Tue Jan 13 10:26:10 2004.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2004S/Outlines/outline.06.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu