SICP exercise 1.11

From Drewiki

Jump to: navigation, search

Problem

A function f is defined by the rule that

f(n) = \begin{cases} n, & \mbox{if }n<3 \\ f(n-1)+2f(n-2)+3f(n-3), & \mbox{if }n>=3 \end{cases}

Write a procedure that computes f by means of a recursive process. Then write a procedure that computes f by means of an iterative process.

Solution

Here's a recursive implementation: 

(define (f-recursive n)
  (if (< n 3)
      n
      (+ (f-recursive (- n 1))
         (* 2 (f-recursive (- n 2)))
         (* 3 (f-recursive (- n 3))))))

Tests: 

(f-recursive 0)

Output: 

0

(f-recursive 1)

Output: 

1

(f-recursive 2)

Output: 

2

(f-recursive 3)

Output: 

4

(f-recursive 4)

Output: 

11

(f-recursive 5)

Output: 

25

(f-recursive 6)

Output: 

59

Here's an iterative implementation that keeps track of the values of f(n-1), f(n-2) and f(n-3) at each step: 

(define (f-iterative n)
  (define (iter-f n count f1 f2 f3)
    (if (> count n)
        f1
        (iter-f n
                (+ count 1)
                (+ f1 (* 2 f2) (* 3 f3))
                f1
                f2)))
  (if (< n 3)
      n
      (iter-f n 3 2 1 0)))

Tests: 

(f-iterative 0)

Output: 

0

(f-iterative 1)

Output: 

1

(f-iterative 2)

Output: 

2

(f-iterative 3)

Output: 

4

(f-iterative 4)

Output: 

11

(f-iterative 5)

Output: 

25

(f-iterative 6)

Output: 

59
Retrieved from "http://wiki.drewhess.com/wiki/SICP_exercise_1.11"
Personal tools