Note: this wiki is now retired and will no longer be updated!

The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.

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
Personal tools