• New partners!

Overview

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

Preliminaries

Admin

• Review session tonight at 7:00 p.m.
• Office hours today and tomorrow at 10:00 a.m.
  
  • 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 (Morning Section)

• Julia's radio show, "The Hot Box". Wednesday night/Thursday morning 1:00-2:00 a.m.
• Orchestra Saturday at 2 p.m. in Sebring-Lewis: Musicals, Show Tunes, and Soloists.

Other Good Things

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

Questions

When will we get grades on homework assignments?

By Sunday evening.

Background

Approximately seven things that we expect to see in algorithms

• Subroutines with parameters (named inputs)
• Variables: Things that are defined so that the program will be faster or cleaner. (Names for computed values.)
• Conditional: Choose between different possibilities
• Repetition: Where you repeat stuff
• Subroutines: Helper algorithms
• Sequencing (including sequencing by nesting).
• Some basic built-in operations.

What kinds of repetition have we seen?

• map: Takes a function and at least one list and applies the function to each element (or groups of elements) - returns a list
• image-variant: Takes as input an RGB transformation and an image and applies the transformation to each pixel - returns an image
• "repeat by hand"
• make-list makes a list of a particular length
• image-compute returns a computed image by applying a function at each position.

How do we do other kinds of repetition? In Scheme, with recursion.

The idea of recursion

• Given a complex problem, break it down into simpler parts.
• Recursion: Given a complex problem, solve a simpler version of the problem, and then use that solution to solve the "bigger" problem.
• With lists, we can car and cdr the list
  • car takes the first element
  • cdr takes all but the first element

Some sample recursive procedures

To count the number of items in a list

• If the list is not empty
  • Count the number of items in the cdr
  • Add 1

• Otherwise, it's 0

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

Heaviest item in the list

• If you have only one item, it's the heaviest

• Otherwise

  • Find the heaviest remaining item
  • Compare to the car

  • Return the heavier of the two

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

    (define redder (lambda (color1 color2) (if (> (irgb-red color1) (irgb-red color2)) color1 color2)))

    (define reddest (lambda (lst) (if (= (length lst) 1) (car lst) (redder (car lst) (reddest (cdr lst))))))

All the red items

• If you have no items

  Expressing recursion in Scheme

Lab