• New partners!

Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Background.
• The idea of recursion.
• Some sample recursive procedures.
• Expressing recursion in Scheme.
• Contrast recursion and interation.
• Start Lab.

Preliminaries

Admin

• Happy Texas unindependence day.
• Review session tonight at 7:00 p.m.
• Office hours tomorrow at 10:00 a.m. and probably 3:15-4:00ish
  • http://rebelsky.youcanbook.me
  • I'm trying to free hours from about 3:15-4:30 tomorrow. They will appear soon.
• Reminder: Please clean up after yourself in 3813 and 3815 and beyond.
• Today's class has a slightly different format (because of the topic, not because of the visitors)
• Welcome to our prospective students and/or parents.

Upcoming Work

• Homework 6.
  • Due Tuesday at 10:30 p.m.
  • Optional! Replaces lowest homework grade.
  • If you don't do the homework, promise to get two hours of extra rest.
• Exam 2 to be assigned on Tuesday. Due 10:30 p.m. Thursday the 12th.
• No lab writeup for today.
• Reading for Tuesday:
  • Review Recursion Basics

Extra Credit Opportunities

Academic

• Any of the disability activities this week.
• David Berliner lecture Thursday at 7:00 p.m. in Harris.
• CS Table Friday - Unknown topic.
• Town Hall on Town Halls, noon or 7:30 p.m. on March 11.
• Post-break: April 1 Scholars Convocation on Implicit Bias.

Peer Support (Afternoon Section)

• Belly Dancing Club Wednesday, 7-8 p.m.

Other Good Things

• Orchestra Saturday at 2 p.m. in Sebring-Lewis: Musicals, Show Tunes, and Soloists.
• Behavioral Economicsc talk today at 7:30 in JRC 101

Questions

When will we get homework back?

Next Sunday, if all goes well.

Will you send us an answer key for HW6 because we are sleeping for our health instead of doing the homework for our brain?

Yes. I'll shoot for Sunday.

Will we get our quiz back tomorrow?

I hope so?

Background

Six or seven basic components to an algorithm

• Subroutines or helper procedures - Smaller algorithm that gets used as part of the bigger algorithm.
• Parameters to subroutines, i.e., named inputs.
• Conditionals - If something applies, then apply a procedure A way to make choices in different situations (when, if, cond)
• Repetition: Repeat the same thing again and again and again
• Variables: Names to values we compute
• Sequencing: A way to determine the order in which we do things
• Basic operations: Things that are built in to the language

Repetition

• map to apply a procedure to each element of a list. Gives you a list.
• iota - creates a sequence of numbers, and so is implicitly doing some repetition
• make-list - create a list of identical values
• image-variant and image-transform! change all the pixels in an an image (applying a color transformation), the first creates a new image, the second changes it in place. Both return images
• image-compute builds an image by applying a function at each (x,y) pair.
• list which calls cons again and again and again

If we restrict ourselves to lists, we don't always want another list of the same size.

• Length of the list (returns a number)
• Extract all elements that meet some criteria (returns a potentially smaller list)
• Find the "best"/"worst" element of a list (returns a value)
• iota and make-list, if we wanted to write them ourselves.

The idea of recursion

A common problem solving topic: Decompose a big problem into simpler problems and combine those solutions.

Recursion: Take a large problem and solve a smaller version of the problem.

• We pretend that we can use the same procedure to solve the smaller problem. (The magic recursion fairy helps.)
• We use the solution to the samller problem to solve the bigger problem.

Some sample recursive procedures

Counting items in a bag:

• If there's nothing left in the bag,
  • report 0

• Otherwise

  • Remove one item from the bag.
  • Count the remaining items in the bag.

  • Add 1

    (define count (lambda (lst) (if (null? lst) 0 (+ 1 (count (cdr lst))))))

Find the heaviest thing in the bag

• If there's only one thing,
  • Return that item

• Otehrwise

  • Remove one item
  • Find the heaviest remaining item

  • Take the heavier of the the item you get back and the item you removed

    (heaviest (list 'expo-red 'expo-black 'stapler 'cards 'eraser) 'stapler

    (define heaviest (lambda (lst) (if (= (length lst) 1) (car lst) (heavier (car lst) (heaviest (cdr lst))))))

    (define largest (lambda (lst) (if (= (length lst) 1) (car lst) (max (car lst) (largest (cdr lst))))))

To find all the red items in the bag

• If the bag is empty
  • Hand back nothing
• Otherwise
  • Remove one item from the bag
  • Find all the red items left in the bag
  • If the one item is red, add it to the things you got
  • Otherwise, just pass all of them along

Expressing recursion in Scheme

• See above.

Contrast recursion and iteration

• Both are mechanisms for repeating operation.
• Recursion operates by having a procedure call itself.
• Iteration is more of the form "Do this thing some number of times"

Start Lab

We will continue lab next class.