6.001 Structure and Interpretation of Computer Programs
Recitation #3
Student Name: ____________________
Friday, September 17, 2004
Topics
- recursion & iteration
- sequencing
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).
2. Write an iterative version of alt-sum.
Show a substitution model evaluation for (alt-sum 1 4).
(pow a n) = an
for integers n >= 0
3. Write a recursive version of pow.
Show a substitution model evaluation for (pow 3 4).
4. Write an iterative version of pow.
Show a substitution model evaluation for (pow 3 4).
(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).
6. Write an iterative version of fib.
Show a substitution model evaluation for (fib 4).