src/sicp/ex1_11.clj

   1 (ns sicp.ex1_11
   2   (:use [sicp utils]
   3         [clojure.contrib trace test-is]))
   4
   5 ;; exercise 1.11: A function f is defined by the rule that f(n) = n if n < 3
   6 ;;                and f(n) = f(n - 1) + 2f(n  - 2) + 3f(n - 3) if n> 3.
   7 ;;                Write a procedure that computes f by means of a recursive
   8 ;;                process. Write a procedure that computes f by means of an
   9 ;;                iterative process.
  10 (defn f [n]
  11   (if (< n 3)
  12     n
  13     (+ (f (- n 1))
  14        (* 2 (f (- n 2)))
  15        (* 3 (f (- n 3))))))
  16
  17 ;; (comment
  18 ;; user> (map f (range 10))
  19 ;; (0 1 2 4 11 25 59 142 335 796)
  20 ;; )
  21
  22 ;; ex 1.11: iterative version
  23 (defn f-iter [count prev0 prev1 prev2]
  24   (if (= count 3)
  25     (+ prev0
  26        (* 2 prev1)
  27        (* 3 prev2))
  28     (f-iter (dec count)
  29             (+ prev0
  30                (* 2 prev1)
  31                (* 3 prev2))
  32             prev0
  33             prev1)))
  34
  35 (defn f [n]
  36   (if (< n 3)
  37     n
  38     (f-iter n 2 1 0)))
  39
  40 ;; ex 1.11: iterative version with let
  41 (defn f-iter [count prev0 prev1 prev2]
  42   (let [res (+ prev0 (* 2 prev1) (* 3 prev2))]
  43     (if (= count 3)
  44       res
  45       (f-iter (dec count)
  46               res
  47               prev0
  48               prev1))))