comparing the work done
the same work?
- do the iterative and recursive versions do the same work?
- imagine an expression that captures the entire computation
ignore the calling of procedures and the binding of values to parameters
- compare exp and expi:
(exp 2 3) and (expi 2 3) both compute (* 2 (* 2 (* 2 1)))
- but consider sum and sumi
(sum 4) computes (+ 4 (+ 3 (+ 2 1)))
(sumi 4) computes (+ 1 (+ 2 (+ 3 4)))
commutativity
- + is commutative: (= (+ a b) (+ b a))
- so the order doesn’t make a difference
but sometimes
- the order does make a difference
- we must reverse the “direction of motion” of the index
- example
(define (f k) (if (= k 1) 1 (+ (* k 10) (f (- k 1)))))