What is wrong with my solution ?
(define (halve x) (/ x 2))
(define (double x) (* x 2))
(define (mult-iter acc a b)
(cond ((= b 0) acc)
((even? b) (mult-iter acc (double a) (halve b)))
(else (mult-iter (+ a acc) a (- b 1)))))
(define (* a b)
(mult-iter 0 a b))
When I run this interpriter fails:
1 ]=> (load "e1.18.scm")
;Loading "e1.18.scm"... done
;Value: *
1 ]=> (* 2 2)
;Aborting!: maximum recursion depth exceeded
"Paper" debugging didn't help: (* 2 2) -> mult-iter 0 2 2 -> (b is even so) mult-iter 0 4 1 -> (b isn't even) -> mult-iter 4 4 0 -> (b is equal to 0) 4.
The result should be 4, where do I get infinite recursion?
The problem is in here:
(define (double x) (* x 2))
The * procedure that you're using is the same you're defining below! that leads to a circular recursion. In general, it's not a good idea to name a procedure using an existing built-in's name. You should rename your new definition:
(define (mul a b)
(mult-iter 0 a b))
Or alternatively, define double without using *, but I prefer the previous approach:
(define (double x) (+ x x))