Overview

• General questions on the exam
• A bit of info about the quiz (topics, general forms of questions)
• Your questions on recent topics
• Sample quiz questions

Questions on the exam

On problem 6, can we use map in building the list, even if we don't use it for the repetition?

No.

On problem 3d, what are the input and output types of shift-up?

shift-up takes an integer as input and gives an integer as output.

What if the user wants a character?

Then he/she/ze can call integer->char.

For problem 4, do we have to use map, which appears in the topics?

No. But one of your goals is to make the code concise, and map often leads to more concise code.

Since the topic of the exam is "recursion", should we assume we'll use recursion on every problem?

No. The topic is "recursion and repetition", so you are likely to use both. And even then, not all problems require either. Two problems do not mention repetition/iteration/recursion, and probably don't require them.

On problem 8, why is multiplication "faster" than counting?

If we were counting down from 1000 to 1 by subtracting 1, we have 999 or so recursive calls.

What if we divide by 2 each time? 1000 -> 500 -> 250 -> 125 -> 125/2 (or 62.5) -> 125/4 (31.25) -> 125/8 -> 125/16 -> 125/32 -> 125/64 -> 125/128.

So we are doing many fewer recursive calls.

Will you take off if we use the "wrong" kind of recursion (helper, rather than direct, or vice versa)?

Probably not, provided your code is correct, reasonably efficient, and reasonably concise.

About the Quiz

What's on the quiz?

Turtles

Pairs and pair structures (lists, trees, etc.)

Recursion and repetition using the previous things

What kinds of questions might you ask?

"Sketch the picture that results from the following set of turtle expressions."

"Sketch the pair structure that corresponds to this expression."

"Write the expression that corresponds to this pair structure."

"Given this partially completed tree procedure, fill in the blanks."

"Show the steps when I apply this procedure to *this input."

"Read this procedure, tell me what it does, give me the preconditions, and rewrite it so that it's clearer. (Probably only two of the three.)

General Questions

Can you talk about trees?

Trees are structures that are built from pairs (aka "cons cells").

Trees are like lists except that (1) for a list, only the cdr has to be a list, while in trees, both the car and the cdr have to be trees; (2) for lists, the "simplest list" is null; for trees, the "simplest tree" is often a value of a particular type.

Can you explain the base case of tree recursion?

Normal recursion: Keep simplifying until you reach something "simple enough".

Tree recursion. Often recurse on both car and the cdr - likely to be more recursion. Pairs are generally not "simple enough", so our base case is when it's not a pair. And the model of trees above says that if it's not a pair, it's a single value.

We generally make trees of particular types, such as trees of numbers or trees of strings, or trees of colors, or .... So, in a tree of numbers, we know that the base case is a number. In a tree of strings, the base case is a string, ....

Can a tree contain lists?

Yes, but then it's hard to tell what part is the tree and what part is a list. And it makes things confusing.

One strategy: Generalize our view of trees. A tree of numbers is either a number or a pair of trees of numbers. A listree of numbers is either: a number, null, or a pair of listrees of numbers.

Hmmm ... that might be something fun for the next exam.

Why would we use trees?

To confuse you. (More precisely, to help you think about times in which recursion is more complex.)

As a lead in to things that are also trees, but have more information.

Trees provide one mechanism for simplifying images.

Can we talk about for-each?

Similar to map.

Parameters to map? (map PROC LIST). Note that the procedure could be a predefined procedure, a lambda expression, a section (l-s or r-s) or .... In each case, it applies the procedure to each element of the list, takes the resulting values, and combines them back into a list.

We also have (map PROC LST1 LST2 ... LSTN). Similar meaning: Apply procedure, combine results into a list.

Sometimes our list of values tells us other information, or its information we want to use in different ways. For example, we might represent a continuous line drawing as a list of (turn . forward) pairs. We could have a turtle use each pair to turn and movev, but we don't need values back. We would use for-each for this.

Model (for-each PROC LIST). The PROC is a side-effecting procedure (so usually with a ! in its name).

Sample code from the for-each example

#lang racket
(require gigls/unsafe)

(define turtle-step!
  (lambda (turtle step)
    (turtle-turn! turtle (car step))
    (turtle-forward! turtle (cdr step))))

(define sams-drawing
  (list (cons 0 10) (cons 90 20) (cons 90 12) (cons 135 24) (cons 225 10)))

(define world (image-show (image-new 200 200)))
(define sam (turtle-new world))
(turtle-teleport! sam 100 100)
(turtle-face! sam -90)
(for-each (l-s turtle-step! sam) sams-drawing)