Saturday, May 30, 2009

Ex-1.11

;;
;; foo(n) = 0 if n=0
;; = 1 if n=1
;; = 2 if n=2
;; = foo(n-1)+2foo(n-2)+3foo(n-3)
;;

;;recursive definition
(define (foo n)
(cond
((= n 0) 0)
((= n 1) 1)
((= n 2) 2)
(else
(+ (foo (- n 1))
(* 2 (foo (- n 2)))
(* 3 (foo (- n 3)))))))

;;iterative definition
(define (foo n)
(foo-iter 2 1 0 n))
(define (foo-iter a b c count)
(cond
((= count 0) c)
(else
(foo-iter
(+ a (* 2 b) (* 3 c)) a b (- count 1)))))

The general technique to convert recursive->iterative is to somehow find an invariant assertion that remains true from one iteration to another and wind-up the state in arguments.
As in above iterative definition state is in a, b & c and invariant assertion is that c, b & a are foo of 3 consecutive numbers.

No comments:

Post a Comment