EBoard 16: Recursion, Initiated

Approximate overview

• Admin
• Quick comments on style
• Background/Review: Key components of algorithms
• Recursion basics
• Examples!
• Some key points

Administrative stuff

Reminders on getting help

• We have three mentor sessions a week. You don’t need to attend all three, but feel free to attend them to work on practice problems and to get help.
• Evening tutors are (generally) helpful. Please use them.
• Reach out to me with questions, to set up meetings, whatever.
  • I try to check Teams before email.
  • I am happy to meet in person, both during office hours and outside of office hours.
• Individual tutors are available if the primary resources do not provide enough help.

Introductory notes

• Zakrasjek and Asprey are back!
• Happy National Disability Employment Awareness Month!
• Please update your csc151 library. See email for details.
  • Sam will attempt to demo.
• I understand that there are reasons you cannot make it to class. Please drop me a note to say what’s going on. I prefer that the notes be prospective, but retrospective notes are also okay.
• Yay! We start recursion!

Upcoming activities

Events

• Pioneer Weekend introductory talk, 7:00 p.m. TONIGHT
• Pioneer Weekend, October 1–3
• Mentor Session Sunday at 4pm
• Arcadia Next Weekend!
  • Arcadia is a play by Tom Stoppard

Other good things

Upcoming work

• Mini-Project 4 due next Thursday.
• Readings for Monday, but no reading writeup!
  • Review the reading on recursion, now that you have some context.
  • Read The Zen of Booleans
  • Read SamR’s Scheme Style Suggestions
• No lab writeup for Monday!

Friday PSA

• Sleep is a good thing.
• Everything else in moderation.
• Consent is ESSENTIAL!
• Watch out for each other.

Q&A

Do we need to use recursion?

No.

What do you mean by visual representation?

A picture that we can look at quickly to determine some characteristic or characteristics of the text.

Does the positive/negative words site have other word lists?

No, but you can find others out there. DDG “Sentiment Analysis Word List” or something similar.

Quick comments on style

Do not do the following.

(define count-word (lambda (str filename)
  (list str(length(filter(section equal? <> (string-downcase str))(no-letters(string-downcase(file->string filename))))))))

Issues:

• Doesn’t follow the lambda convention.
• Breaking it onto separate lines would help.
• Documentation would be nice.
• Consider decomposition.
• Spaces help. Welearnedthatalongtimeagowhendevelopingwriting.
• There are potential efficiency issues (at least in the context of this assignment).

Background/Review: Core Algorithm Components

At the beginning of the semester, we learned about various parts of algorithms, including the following.

• Built-in Functions
• Conditionals
• Input/Output
• Repetition
• Sequencing
• Subroutines
• Variables (identifiers, named values)

How do we do each of these in Racket?

Built-in Functions

• um - Universal method
• string-append and hundreds more.
• We can find them in our reference or the DrRacket reference.

Conditionals

• (if TEST CONSEQUENT ALTERNATE)
  • First turns the test.
  • If the test is truish (anything but false), evaluate the consequent and use its result.
  • If the test is #f, evaluate the alternate and use its result.
• (cond [GUARD1 CONS1a CONS1b ...] [GUARD2 CONS2a CONS2b ...] ... [ELSE ALTERNATE])
  • Keep evaluating the guards until you hit a truish guard, then evaluate the consequent and return its value.
  • If you never hit a truish guard, evaluate the alternate and use it.
  • What happens if we have more than one consequent? We evaluate all of them and use the last one.
• (and EXP1 EXP2 EXP3 ... EXPn)
  • If any of these evaluate to false, returns false.
  • Evaluates left to right, stops as soon as it hits a false expression.
  • If none of these evluate to false, returns the value of the last one.
  • (and) evaluates to #t?
• (or ...)
• (when ...)

Input/Output

• We can give input to a procedure. Lambdas name that input.
• The interactions pane gives us input and output: The user types the expression they want evaluated and the computer prints out the value.
• You know input from a file.
• YOu know output to a fle.
• You will learn other ways of doing input and output.

Repetition

• map: Repeatedly applies a procedure to each element in a list, producing a new list.
• reduce: Repeatedly applies a procedure to neighboring values in a list, eventually reducing it down to one value.
• filter: Repeatedly look at the elements of a list, deciding whether to keep or discard them.
• We will be learning recursion, the most general form of repetition.

Sequencing

• We use parentheses to order stuff: More inner things get evaluated first.
• reduce-left and reduce-right provide a kind of ordering.
• We assume that the parameters to a procedure are evaluated left to right (it turns out that that’s not guaranteed).
• If we write things in order in the interactions pane, Racket evaluates them in order.
• let* does the naming in order, top to bottom.
  • Nested let is similar.
• cond and when can have multiple consequents that are evaluated in order.
• and and or also do sequencing.

Subroutines

• lambda, section, and compose all allow us to build subroutines. We can name them using the techniques below.

Variables (identifiers, named values)

• define
• let and let*
• parameters name values

Recursion

Recursion is the most general form of repetition.

It takes advantage of a skill we’ve been using/developing: Decomposition.

Instead of decomposing into different problems, we decompose into a “smaller” or simpler version of the same problem. (Sometimes multiple smaller/simpler versions.)

We then use the solution to the smaller problem(s) to find a solution to our larger problem.

How do we solve the smaller problem(s)? Generally, we use the same approach. We decompose them into even small problems and use them to solve our larger problem.

Eventually, we decompose into a small enough problem that we can solve it directly.

Examples!

Counting cards

• If you have one card, report “one”
• Otherwise
  • Remove one card
  • Ask you assistant to count the remaining cards
  • Add one

Finding the alphabetically last card

• If you have one card, return the card
• Otherwise
  • Remove one card
  • Ask your assistant to return the alphabetically last
  • Compare to your card.
  • Return the alphabetically last of the cards

(null? (cdr lst)) is how you ask if you have one card?
(car lst) is the first element
(cdr lst) is all but the first element

(define one-element?
  (lambda (lst)
    (null? (cdr lst))))

(define alphabetically-last
  (lambda (lst)
    (if (null? (cdr lst))
        (car lst)
        (let ([my-card (car lst)]
              [assistant-answer (alphabetically-last (cdr lst))])
          (if (str<? my-card assistant-answer)
              assistant-answer
              my-card)))))

An alternate version

• Delegate half to one assistant
• Delegate half to other assistant
• Compare the two results and return the alphabetically last of the two

Putting the cards in order

• If you have one card, return the card
• Otherwise
  • Remove one card
  • Ask you assistant to put the cards in order
  • Insert your card in the proper place
  • Return the list Notes —–

Trust the magic recursion fairy. Assume that you have a solution for “a smaller version of the problem”. How does that help you solve the larger problem?

Your helper procedure is the procedure you are writing!