SICP 1.11

sicp-1.1.hs

-- SICP 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 computes f by means of a recursive process.
--
f :: Integer -> Integer
f n
    | n < 3 = n
    | otherwise = f (n - 1) + 2 * f (n - 2) + 3 * f (n - 3)

-- Write a procedure that computes f by means of an iterative
-- process.

fIterative :: Integer -> Integer
fIterative n = fIterative' n 2 1 0 3

fIterative' :: Integer ->
               Integer ->
               Integer ->
               Integer ->
               Integer ->
               Integer
fIterative' n n1 n2 n3 count
    | n < 3 = n
    | n == count = strippedAwayF n1 n2 n3
    | otherwise =
        fIterative' n (strippedAwayF n1 n2 n3) n1 n2 (count + 1)

strippedAwayF :: Integer ->
                 Integer ->
                 Integer ->
                 Integer
strippedAwayF n1 n2 n3 = n1 + (n2 * 2) + (n3 * 3)