University of Virginia, Department of Computer Science
CS200: Computer Science, Spring 2004

Notes: Wednesday 28 January 2004

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 (fibo n)
(if (or (= n 1) (= n 2))
       1 ;;; base case
       (+ (fibo (- n 1))
            (fibo (- n 2)))))
(define (fast-fibo n)
    (define (fibo-worker a b count)
       (if (= count 1)
            (fibo-worker (+ a b) a (- count 1))))
    (fibo-worker 1 1 n))

How many times is fibo evaluated to evaluate (fibo 10)?

How many times is fibo-worker evaluated to evaluate (fast-fibo 10)?


What does cons do?

What do car and cdr do?

How could we define cons, car and cdr if Scheme did not have them as primitives?

A quintuple is a pair where ...

Why do we need the special list null?

What is the value of (car (cdr (cons 1 (cons 2 (cons 3 null)))))?

If you're in the penalty area and don't know what to do with the ball,
put it in the net and we'll discuss the options later.

Bob Paisley
Using these Materials