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

## CS150 Notes 7 (7 September 2005)

• Friday, 9 September: PS2
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.
Recusive Definitions on Lists

1. Be very optimistic. Since lists themselves are recursive structures, we should be able to come up with a recursive definition for almost anything we can think of doing with a list.
1. Assume we can solve a smaller version of the problem.
2. Break the problem into the original list and its cdr.
2. Think of the simplest version of the problem, something you can solve already. For lists, this is usually the null list. (Sometimes, it might be the length 1 list.)
3. Combine them to solve the problem. For lists, we will usually do combine the result of the recursive evaluation on the cdr with the result of doing something with the car of the list.
Many recursive list procedures can be defined with this template:
```(define (listproc lst)
(if (null? lst)
[[[ insert base case here ]]]
([[[ f ]]] (car lst) (listproc (cdr lst)))))
```
For example:
```(define (sumlist lst)
(if (null? lst)
0
(+ (car lst) (sumlist (cdr lst)))))
```
```(define (insertl lst f stopval)
(if (null? lst)
stopval
(f (car lst)
(insertl (cdr lst) f stopval))))

(define (sumlist lst) (insertl lst + 0))

(define (productlist lst) (insertl lst * 1))

(define (length lst)
(insertl lst (lambda (head rest) (+ 1 rest)) 0))
```
```(define (remove cf lst)
;; operands: cf is a comparison function that takes one operand and
;;              evaluates to #t or #f
;;           lst is a list of values
;; result: evaluates to a list containing the only elements of lst for
;;            which (cf ) evaluates to #f
(if (null? lst)  _________________________
(if (cf (car lst))

______________________________    ;; discard first element

______________________________))) ;; keep first element
```
Could you define remove using just a map application? (Explain how or why it is impossible.)

Could you define remove using just an insertl application? (Explain how or why it is impossible.)

```(define (filter cf lst)
;; operands: cf is a comparison function that takes one operand and
;;              evaluates to #t or #f
;;           lst is a list of values
;; result: evaluates to a list containing the only elements of lst for
;;            which (cf ) evaluates to #t

)
```
There are many ways to define filter. Try to find the shortest one. You can use anything we have already defined.

Challenge: Define a procedure (intsto n) that evaluates to a list containing the integers less than or equal to n in order. For example, (intsto 3) ==> (1 2 3) and (intsto 0) ==> (). This is pretty tricky. Try your definition in DrScheme.

In mathematics you don't understand things, you just get used to them.
John Von Neumann

"); print ( \$res[\$first] ) ; print (""); ?>