CSC 151.01, Class 18: Recursion basics

Overview

• Preliminaries
  • Notes and news
  • Upcoming work
  • Extra credit
  • Detour on partners
  • Friday PSA
  • Questions
• Quiz
• Background
• Some examples
• Key ideas in recursion
• Sample recursive procedures
• Expressing recursion in Scheme

Preliminaries

News / Etc.

• New partners!
• Sorry about Wednesday. It appears that I’m late in catching whatever has been going around campus. (And now I am even more behind.)
• No lab today; we start our exploration of recursion with lecture/discussion.

Upcoming work

• No lab writeup!
• Reading for Monday:
  • Reread Recursion basics
• Exam 2 due Tuesday
  • Prologue due TONIGHT!
  • Exam due Tuesday night
  • Epilogue due Wednesday night

Extra credit (Academic/Artistic)

• Visit the two exhibits at the Faulconer Gallery.

Extra credit (Peer)

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.

Extra credit (Misc)

• Fill out NCHA Survey (aka the latest food truck survey).
  • Students received e-mails from “Jen Jacobsen ncha-web@acha.org” with the subject line “NCHA survey: Help GC help you + food trucks!” (Depending on outlook settings, this may end up in other or clutter folders)
  • NCHA data help me give my PSAs
  • Your reflection should not just be “I filled out the survey”. Reflect on what was interesting (or not) about the survey.

Other good things

• President White in regional diving.
• GHS Girl’s Basketball in State Finals tonight.

Working together

I continue to hear things about students having difficulty with their partners. That makes me sad. I’ll give some of my perspective and then ask you to discuss the issue a bit.

• I am getting a lot of “My partner won’t meet with me / My partner does not respond to my email.”
• There can be good reasons.

Suggested solutions

• Give students the option to do the work on their own.
• “This is when I’m free. Pick a time.”
• Partner evaluation
  • If someone has two or more “negative” evaluations, Sam should talk with them.
• There are other issues, such as condescension.
• Whoops. Anything that includes Sam as a bottleneck is likely to fail.
• There are good reasons that you had difficulty meeting, but you should always respond to email.
• Give 24 hours?

Friday PSA

• Get rest
• Make good choices
• Moderation
• Consent is essential

Questions

Non-exam Questions

Can you explain husk and kernel again?

You already know about preconditions. We used to say “If the preconditions are not met, anything can happen.” Moving to a world in which “If the preconditions are not met, the procedure reports an error.”

We can report errors with the amazing “error” procedures.

In writing procedures, we think about two separate parts: (1) Husk - Checking preconditions and (2) Kernel - Doing the work.

Do the husk and kernel have to be in the same procedure, with the kernel locally bound?

It’s a matter of preference. There are risks in separating the two, but some people find that an acceptable strategy. E.g., sort-unsafe and sort.

Will you be more sympathetic on grading exam 2 since we won’t get exam 1 back until Monday or so?

Yes.

Exam Questions

Can you explain the check-error thing?

I can try.

We’ll do concept and then code.

Concept: Unit testing suggests that we should write tests that check that our procedure behaves the way we expect. We now have procedures that we expect to fail in certain ways. In particular, we expect that they will issue an error message. Our test is now not “It succeeds and returns X”; our test is “it fails when given incorrect inputs”.

Example. Compute the square of a number.

(define unsafe-square 
  (lambda (x)
    (* x x)))

(define square
  (lambda (x)
    (cond
      [(not (number? x))
       (error "Square expects a number, given" x)]
      [else
       (unsafe-square x)])))

I want to be able to say “When I call (square 'a), I’ll get an error.”

We will use a slightly strange syntax for that.

(check-error (lambda () (square 'a)))

Let’s use it.

> (unsafe-square 'a)
. . *: contract violation
  expected: number?
  given: 'a
  argument position: 1st
  other arguments...:
> (square 'a)
. . Square expects a number, given a
> (check-error (lambda () (square 'a)))
> (check-error (lambda () (unsafe-square 'a)))
--------------------
FAILURE
message:     "Wrong exception raised"
exn-message: "*: contract violation\n  expected: number?\n  given: 'a\n  argument position: 1st\n  other arguments...:\n   'a"
exn:         #(struct:exn:fail:contract "*: contract violation\n  expected: number?\n  given: 'a\n  argument position: 1st\n  other arguments...:\n   'a" #<continuation-mark-set>)
name:        check-exn
location:    (#<path:/home/rebelsky/Desktop/exn-example.rkt> 7 4 118 79)
expression:  (check-exn (conjoin exn:fail? (negate exn:fail:contract?)) proc)
params:      (#<procedure:conjoined> #<procedure>)

. Check failure
--------------------
> (check-error (lambda () (square 2)))
--------------------
FAILURE
message:    "No exception raised"
name:       check-exn
location:   (#<path:/home/rebelsky/Desktop/exn-example.rkt> 7 4 118 79)
expression: (check-exn (conjoin exn:fail? (negate exn:fail:contract?)) proc)
params:     (#<procedure:conjoined> #<procedure>)

. Check failure
--------------------

It feels a bit like an opposite thing: We’re looking for an error. If there’s an error, life is good. If there’s not an error, then there’s a problem (the check failed).

Why are we distinguishing user-defined errors and extant errors?

It lets us check whether your are successfully generating your own errors.

When should we use check-= vs check-equal?

Use the former for numbers and the latter for everything else.

What about eq? and eqv?

Don’t use them. Subtleties that are not currently important.

Do we need to check for a particular error message?

No.

Would you explain the empty lambda thing?

I assume you mean (check-error (lambda () (square 'a)))

You don’t have to understand it to use it.

Scheme evaluates inside out.

Traditionally, as soon as an error is issued, it stops the execution.

If we write (check-error (square 'a)) and (square 'a) fails, it will never call check-error.

So instead of passing the result of (square a) into check-error, we’re passing a procedure that, when evaluated, computes square a.

Am I correct that our test suite should check both (a) correct inputs produce correct outputs and (b) incorrect inputs produce errors?

Yes.

Quiz

Background

Seven or so components to algorithms. What are they? What do they mean? Example from Scheme.

• Building blocks
  • The things that come in the language.
  • Numbers and numeric operations (+, -, …)
  • Strings and string operations
  • Lists and list operations
• Variables
  • Ways of naming things
  • We can use the parameters in a lambda (lambda (a b c) ...)
  • We can use define
  • We can use let or let*
• Repetition
  • Want to do something over and over again
  • Recursion provides one form of repetition
  • Physically type it out
  • map is a form of repetition: We’re doing something to each element of a list
  • reduce is a form of repetition: We’re repeatedly combining elements.
• Inputs and outputs
  • The last expression in the body of a Scheme procedure is the output of that procedure.
• Conditionals
  • Ways to make choices.
  • cond
  • if
  • when
  • and and or do a kind of choices (or (...) (...) (...))
  • Related: not and negate are used in those
• Subroutines - Procedures
  • Ways to group instructions together and parameterize them
  • lambda
  • section
  • o
• Sequencing
  • Knowledge of evaluation order - inside-out
  • let* evaluates things in order
  • cond does checks in order (and and and or look at things in order)
  • We also just type things in order

Today, we are looking at how we might implement repetition if we did not have map and reduce.

Some live examples

Count the stack of books

• If the stack has no books
  • Say zero
• Otherwise
  • Remove one book
  • Ask someone else to count the remaining books
  • Add 1 to whatever they gave you back

Find the books about writing

• If the stack has no books
  • Give back no books
• Otherwise, if the top book is about writing
  • Ask your assistant to find the remaining books about writing
  • Add the top book
  • Hand it back
• Otherwise
  • Ask your assistant to find the remaining books about writing
  • Hand them back

Key ideas in recursion

Sample recursive procedures

Expressing recursion in Scheme