University of Virginia Computer Science CS150: Computer Science, Fall 2005 (none) 9 September 2005

## CS150 Notes 8 (9 September 2005)

#### Upcoming Assignments

• Now: PS2
• Monday, 19 September: PS3
Schedule Update: Problem Set 4 will be handed out on Monday, September 19 and due on Monday, September 26. Exam 1 will be handed out on Friday, September 30 and due on Wednesday, October 5. (There is no class on October 3, which is Reading Day.)

Recursive Definitions

1. Be optimistic.
• Assume you can solve it.
• If you could, how would you solve a bigger problem.
2. Think of the simplest version of the problem, something you can already solve. (This is the base case.)
3. Combine them to solve the problem.
```

(define (find-closest goal numbers)
(if (= 1 (length numbers))
(first numbers)
(if (< (abs (- goal (first numbers)))
(abs (- goal
(find-closest goal (rest numbers)))))
(first numbers)
(find-closest goal (rest numbers))))

```
Languages

How can we compare notations for describing languages?

What is the difference between RTN and BNF?

Music and Recursion

Song ::= Verse VBBD VBBD Better Coda