CSC 151.01, Class 21: Other forms of list recursion

Overview

• Preliminaries
  • Notes and news
  • Upcoming work
  • Extra credit
  • Friday PSA
  • Questions
• Quiz
• Lab
• Debrief

Preliminaries

News / Etc.

• New partners!
• Don’t forget that we “Spring Forward” on Sunday morning. (And sorry, I know that means that you’ll be extra tired on Monday a.m.)
• I appreciate that those of you who are ill are missing class so as to avoid infecting others. Please remember that you owe me an email message in cases like that.

Upcoming work

• Lab writeup for class 21: Exercise 5. Due before class Monday.
• Reading for Monday
  • Numeric Recursion
• Assignment 6 due Tuesday.
  • Preliminary reports suggest that TK and I succeeded in making a shorter assignment.
  • I’ve rearranged the problems. Check the problem numbers before submitting. (The one group that submitted can ignore this comment; I’ll let the graders know.)
  • Evidence suggests that problem 7 (permutations) is the most difficult.
  • If you weren’t here on Wednesday, you and your partner have until the end of class today to tell me when you are working on the assignment.
• Flash Cards due Wednesday.

Extra credit (Academic/Artistic)

• Visit the two exhibits at the Faulconer Gallery.
• CS Extra Monday at 4:15 p.m. in 1023: “An Introduction to the Automatic Extraction of Keyphrases”. (Snacks at 4pm.)
• CS Table Tuesday at noon: Unknown topic.

Extra credit (Peer)

• Play this weekend. Today through Sunday. See the campus memo or elsewhere for details.
• Men’s Tennis, Sunday at 9am (Central) and 2pm (Augustana) in the Field House.

Extra credit (Recurring peer)

• Listen to KDIC Wednesdays at 6pm - Witty banter with other personalities and/or co-host. Also Indian, Arabic, and Farsi music.
  (Up to two units of extra credit.)
• Peer editing with SS. Talk to SS about the details. Make your English Lit more literate.
  • Preliminary reports suggest that these appointments are really helpful.

Extra credit (Misc)

• Host one or more prospective students.

Other good things

• GHS presents “The Little Mermaid” Friday, Saturday.
• Singers concert, Sunday, 4 p.m., Plymouth United Church of Christ, 4126 Ingersoll Ave., Des Moines.

Friday PSA

• Take care of yourself.
• Even though I make jokes about these issues, I’m very serious.
• Consent is even more serious (and necessary).

Questions

How do I decide whether to use direct recursion or helper recursion?

You are new to this. And even experienced programmers have difficulty choosing. So the model will generally be “try one approach; if you don’t make forward progress, try another.”

Sometimes different ways of thinking about the problem. If a “table” of steps makes sense, helper/tail recursion is probably the way to go.

Why use and and or instead of if or cond?

To feel superior to those who are unable to understand the intracacies (which sam can’t spell) of and and or.

Sometimes it leads to shorter code.

Sometimes it makes more logical sense / corresponds to the English.

Because you’re returning #t or #f and it makes you uncomfortable to do so explicitly. (Sam thinks code that explicilty says #t or #f is generally less elegant.)

Can you do everything with and and or (and not) that you can do with a conditional?

I think so.

Are there uncommon forms of recursive procedures?

Certainly.

There is a huge universe of possible problems. Some match common patterns. Some do not.

You’ll also learn some new common patterns in the coming weeks.

Why does reduce not work on the empty list?

If reduce is supposed to repeatedly combine values until you have a single value. It’s hard to get one value from nothing. Hence, reduce expects at least one value.

What’s the difference between using helpers and not using helpers?

Helpers traditionally carry along an extra parameter. In most cases, that lets you build a nice table to explain to yourself what it’s doing.

What’s the difference between tail recursion and non-tail recursion?

Tail recursion: You do nothing with the result of the recursive call (other than give it back).

Non-tail recursion: You do something with ther esult of the recursive call (e.g., add to it)

Non-tail recursion requires the computer to build up a list of incomplete computations, which takes additional effort. So non-tail recursion can be less efficient.

Quiz

• The most fun you’ll have all weekend!
• Nonetheless, take quizzes in moderation.

Lab

Is it okay if smallest ends up giving us an inexact number even when the smallest number in the list is exact?

Yes.

Couldn’t we have written lists-join with an empty-list base case?

Um … let me think … possibly.

(define lists-join
  (lambda (lst)
    (if (null? lst)
        null
        (append (car lst)
                (lists-join (cdr lst))))))

Is the last problem the same as problem 2 on the homework?

Yes.

Writeup: Problem 5

Debrief

Our goal is to build a collection of things like the following:

(define REDUCE-PROC
  (lambda (lst)
    (if (null? (cdr lst))
        (car lst)
        (PROC (car lst) (REDUCE-PROC (cdr lst))))))

Once we have these, our work often becomes more something like “Determine if an appropriate pattern exists. If so, copy that pattern and change a few things.”

Note to SamR: Go over how students might have solved problem 5 in class on Monday.