sicp-2e/c1/e1.11.scm

; f(n) = { n if n < 3
;          f(n - 1) + 2f(n - 2) + 3f(n - 3) if n > 3

; linear recursive process implementation
(define (f n)
    (cond ((< n 3) n)
          (else (+ (* 1 (f (- n 1)))
                   (* 2 (f (- n 2)))
                   (* 3 (f (- n 3)))))))

(f 2)
(f 3)
(f 4)
(f 5)
(f 10)

; linear iterative process implementation

; the idea here is to keep a growing sum of values, accumulated within c
; with every iteration the precomputed values of c bubble to b and later to a
; i begins at n and is decremented for a total of n iterations (simple iterator)
; our base case is for our base cases 1, 2 and 3, the values are held within a, b and c respectively, and bubble timely to a to be evaluated at our iteration's base case (= i 0)
; as computation really only sets off for n >= 3, a, b and c are set as
;     a = n - 3
;     b = n - 2
;     c = n - 1
; respectively

; a = 0; b = 1; c = 2;
; for (i = n; i >= 0; i--) {
;     t_c = c; t_b = b;
;     c = 3*a + 2*b + c;
;     b = t_c;
;     a = t_b;
; }

(define (f2-iter i a b c)
    (cond ((= i 0) a)
          (else
                (f2-iter (- i 1)
                         b
                         c
                         (+ (* 3 a)
                            (* 2 b)
                            c)))))

(define (f2 n) (f2-iter n 0 1 2))

(f2 2)
(f2 3)
(f2 4)
(f2 5)
(f2 10)