ex1_11.clj

(ns sicp.chapter1.ex1_11)

; SICP chapter 1, exercise 11
; let f(x) = x for x<3
;     f(x) = f(x-1) + 2f(x-2) + 3f(x-3) otherwise

(defn f
  "the tree-recursive version"
  [n]
  (if (< n 3) n
    (+
      (f (- n 1))
      (* 2 (f (- n 2)))
      (* 3 (f (- n 3))))))

(defn f2
  "iterative version, single argument version starts the iteration"
  ([n] (if (< n 3) n
         (f2 0 1 2 (- n 2))))
  ([a b c counter]
    (if (= counter 0) c
      (recur
        b c (+ (* 3 a) (* 2 b) c) (- counter 1)))))

Exercise 11 from SICP chapter 1. For comparison, on my Dell laptop calculating f(30), timing both algorithms gives the following output:

user=> (time (f 30))
"Elapsed time: 1829.070002 msecs"
61354575194
user=> (time (f2 30))
"Elapsed time: 0.082814 msecs"
61354575194