# Class 29: Deep Recursion

Back to Vectors. On to Procedures as Values.

Held: Monday, 10 March 2003

Summary: Today we consider a variant of recursion known as deep recursion. In this variant, you often recurse in multiple directions, such as into sublists in addition to across top-level lists.

Related Pages:

Assignments

Notes:

• Are there questions on vectors?
• Today's class will mostly consist of group algorithm design in a round-robin fashion.
• I had fun at the conference on attracting and retaining majors. One key point raised was that students frustrated when what you test them on is substantially different from what you teach them. While I don't think I fall into that trap, I do understand some of your concern that I test you on style without discussing it explicitly. I'll work on that issue.
• We'll also try an interesting game (the muddy children problem) that I learned there.
• Sorry that the last homework took so long. When things work fine in Scheme but don't work on the Web, find me.

Overview:

• List recursion, revisited.
• Deep recursion, considered.
• Group design example 1: `count-elements`.
• Group design example 2: `depth`.

## Review: List Recursion

• By now, you should have a good sense of what recursion over a list looks like.
• With the most typical base case (that is, the list is null), we write something like
```(define procname
(lambda (lst)
(if (null? lst)
base-case
(do-something (car lst) (procname (cdr lst))))))
```
• `do-something` usually does something fairly simple with the combination of the car and the recursive call.

## Complicating Things: Deep Recursion

• What kind of complex thing might you want to do with the `car` of the list? If the car is a list, you might want to recurse over that list, too.
• And if the car list has its own element list, we'd like to recurse on that list, too.
• Does this interesting theoretical approach have any practical implications?
• That is, "Are there ways we'd want to use this?"
• There are certainly many cases in which it helps to have a helper of this form.
• Note that the form of recursion, in which you recurse over sublists as well as along the top-level list, is typcially called deep recursion.
• There are many common problems and algorithms for which deep recursion is an appropriate technique.

## Extending `length`

• Some of you have noted that a key deficiency of `length` is that it does not count the values in sublists when determining the length of the list. Hence, the length of the list `((1 2 3))` is 1, rather than the 3 that most people might expect.
• Let's try to design a procedure that counts all the elements in a list or its sublists.
• Design:
• What is the base case?
• What value do we return in the base case?
• What are some recursive cases?
• What do we do in the recursive cases?
• Implementation:
• How do we translate all that to Scheme?
• Testing:
• Choose some interesting tests.
• Here's one `(list null null null)`

## Determining the Depth of a Nested List

• When lists nest, one might wonder how much nesting is going on (particlarly if one plans to recurse into nested lists).
• We often call such a procedure `depth`
• Design:
• What is the base case?
• What value do we return in the base case?
• What are some recursive cases?
• What do we do in the recursive cases?
• Implementation:
• How do we translate all that to Scheme?
• Testing:
• Identify some interesting tests.

## History

Thursday, 16 January 2003 [Samuel A. Rebelsky]

• First version, created mostly automatically from previous course.

Monday, 10 March 2003 [Samuel A. Rebelsky]

• Filled in the details.

Back to Vectors. On to Procedures as Values.

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 Tue May 6 09:30:00 2003.
The source to the document was last modified on Mon Mar 10 12:31:28 2003.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2003S/Outlines/outline.29.html`.

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

Samuel A. Rebelsky, rebelsky@grinnell.edu