6.001 Recitation #3 – Sept 11, 2002

RI: Konrad Tollmar

Procedures and processes

Substitution model

Recursion veers iteration

1. Writing simple procedures.

Write procedure max that take two arguments and return the larger one.

(define (max a b) (if (> a b) a b))

Write procedure sign that take a number as its argument and return –1 if it is negative, 1 if it is positive and 0 if the argument is zero.

(define (sign a) (cond ((> a 0) 1) ((< a 0) (- 1)) (else 0)))

2. Substitution model.

Imagen that we have defined the procedure y-x*x

(define x-y*y

(lambda (x y)

(- x ((lambda (x) (* x x)) y))))

Use the Substitution model to evaluate the following expression:

(x-y*y 11 3)

(- 11 ((lambda (x) (* x x)) 3))

(- 11 (* 3 3))

(- 11 9)

;Value: 2

3. Iterative vers recursive

Define sum-iterative and sum-recursive that each take two arguments and calculate the accumulative sum between these arguments. E.g. (sum-iterative 2 4) ==> 9.

(define sum-ints (lambda (first last)

(sum-helper 0 first last)))

(define sum-helper (lambda (sum current last)

(if (> current last)

sum

(sum-helper (+ sum current) (+ current 1)

last)))

(define sum-r(lambda (first last)

(if (> first last)

0

(+ first (sum-r (+ first 1) last))))

4. Iterative processes

Write a function count-up2 as count2, but as an iterative process.

(define (our-display x) (display x) x)

(define (count2 x)

(cond ((= x 0) 0)

(else (count2 (- x 1))

(our-display x))))

(define (count-up-2 x)

(define (iter val)

(cond ((> val x) #t)

(else (display val)

(iter (+ val 1)))))

(iter 1))