6.001 Structure and Interpretation of Computer Programs
Recitation #3
Friday, September 17, 2004

Topics

Practice

(alt-sum low high) returns an alternating sum of the integers from low to high inclusive.  For example, (alt-sum 0 5) = 0 - 1 + 2 - 3 + 4 - 5.

1. Write a recursive version of alt-sum.  Show a substitution model evaluation for (alt-sum 1 4).
(define alt-sum
  (lambda (low high)
    (if (> low high)
        0
        (- low (alt-sum (+ 1 low) high)))))

(alt-sum 1 4)
(- 1 (alt-sum 2 4))
(- 1 (- 2 (alt-sum 3 4)))
(- 1 (- 2 (- 3 (alt-sum 4 4))))
(- 1 (- 2 (- 3 (- 4 (alt-sum 5 4)))))
(- 1 (- 2 (- 3 (- 4 0))))
(- 1 (- 2 (- 3 4)))
(- 1 (- 2 -1))
(- 1 3)
-2

2. Write an iterative version of alt-sum.  Show a substitution model evaluation for (alt-sum 1 4).

Here's an iterative algorithm that counts up from low to high. sum  The sign variable is either +1 or -1, depending on the sign of the next integer to add.
(define alt-sum-helper
  (lambda (i sign high answer)
    (if (> i high)
        answer
        (alt-sum-helper (+ 1 i) (- sign) high (+ (* sign i) answer)))))

(define alt-sum
  (lambda (low high)
    (alt-sum-helper low 1 high 0))

(alt-sum 1 4)
(alt-sum-helper 1  1 4  0)
(alt-sum-helper 2 -1 4  1)
(alt-sum-helper 3  1 4 -1)
(alt-sum-helper 4 -1 4  2)
(alt-sum-helper 5  1 4 -2)
-2


Here's another iterative algorithm that counts down from high to low.  It doesn't need to keep track of a sign, because it subtracts the previous answer from the next integer.
(define alt-sum-helper
  (lambda (i low answer)
    (if (< i low)
        answer
        (alt-sum-helper (- 1 i) low (- i answer)))))

(define alt-sum
  (lambda (low high)
    (alt-sum-helper high low 0))

(alt-sum 1 4)
(alt-sum-helper 4 1  0)
(alt-sum-helper 3 1  4)
(alt-sum-helper 2 1 -1)
(alt-sum-helper 1 1  3)
(alt-sum-helper 0 1 -2)
-2


(pow a n) = an for integers n >= 0

3. Write a recursive version of pow.  Show a substitution model evaluation for (pow 3 4).

(define pow
  (lambda (a n)
    (if (= n 0)
        1
        (* a (pow a (- n 1))))))

(pow 3 4)
(* 3 (pow 3 3))
(* 3 (* 3 (pow 3 2))
(* 3 (* 3 (* 3 (pow 3 1)))
(* 3 (* 3 (* 3 (* 3 (pow 3 0))))
(* 3 (* 3 (* 3 (* 3 1)))
(* 3 (* 3 (* 3 3)))
(* 3 (* 3 9))
(* 3 27)
81


4. Write an iterative version of pow.  Show a substitution model evaluation for (pow 3 4).

(define pow-helper
  (lambda (a m answer)
    (if (= m 0)
        answer
        (pow-helper a (- m 1) (* a answer)))))

(define pow
  (lambda (a n)
    (pow-helper a n 1)))

(pow 3 4)
(pow-helper 3 4 1)
(pow-helper 3 3 3)
(pow-helper 3 2 9)
(pow-helper 3 1 27)
(pow-helper 3 0 81)

(fib n) computes the nth Fibonacci number F(n), where F(0)=0, F(1)=1, and for all n>1, F(n)=F(n-1)+F(n-2).

5. Write a recursive version of fib.  Show a substitution model evaluation for (fib 4).

(define fib
  (lambda (n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (else (+ (fib (- n 1)) (fib (- n 2)))))))

(fib 4)
(+ (fib 3) (fib 2))
(+ (+ (fib 2) (fib 1)) (fib 2))
(+ (+ (+ (fib 1) (fib 0)) (fib 1)) (fib 2))
(+ (+ (+ 1 (fib 0)) (fib 1)) (fib 2))
(+ (+ (+ 1 0) (fib 1)) (fib 2))
(+ (+ 1 (fib 1)) (fib 2))
(+ (+ 1 1) (fib 2))
(+ 2 (fib 2))
(+ 2 (+ (fib 1) (fib 0)))
(+ 2 (+ 1 0))
(+ 2 1)
3

6. Write an iterative version of fib.  Show a substitution model evaluation for (fib 4).

In this iterative algorithm, the variable i counts up from 0 to n.  We keep track of both fib_i=F(i) and fib_i+1=F(i+1), so that we can compute the values of the next iteration F(i+1) and F(i+2), and so that when i finally reaches n, our answer is found in fib_i. 
(define fib-helper
  (lambda (i n fib_i fib_i+1)
    (if (= i n)
        fib_i
        (fib-helper (+ i 1) n fib_i+1 (+ fib_i fib_i+1)))))

(define fib
  (lambda (n)
    (fib-helper 0 n 0 1)))


(fib 4)
(fib-helper 0 4 0 1)
(fib-helper 1 4 1 1)
(fib-helper 2 4 1 2)
(fib-helper 3 4 2 3)
(fib-helper 4 4 3 5)
3