sicp exercise 1.11

;  Exercise 1.11. A function f is defined by the rule that
;  f(n) = n if n<3 and
;  f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n> 3.
;  Write a procedure that computes f by means of a recursive process.
;  Write a procedure that computes f by means of an iterative process.



(begin
(define f_recur (lambda (n)
  (if (< n 3)
      n
      (+ (f_recur (- n 1))
         (* 2 (f_recur (- n 2)))
         (* 3 (f_recur (- n 3)))  ))))

(define f_iter_impl (lambda (a b c count)
  (if (= count 0) a
      (f_iter_impl (+ a (* 2 b) (* 3 c) ) a b (- count 1)))))

(define f_iter (lambda (n)
  (f_iter_impl 2 1 0 (- n 2))))

(display (f_iter 4)) (newline)
(display (f_recur 4)) (newline)
(display (f_iter 5)) (newline)
(display (f_recur 5)) (newline)
(display (f_iter 23)) (newline)
(display (f_recur 23)) (newline)
(display (f_iter 100)) (newline)
(display (f_recur 100)) (newline)
)