Class 29: Deep Recursion

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:

• EBoard.

Assignments

• Read the reading on higher-order procedures.

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.