Exercise 1.11 of SICP

Exercise 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 that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.

The idea is to use a triple of integers a,b,c initialized to f(2) = 2 f(1) = 1 and f(0) = 0, and to repeatedly apply the simultaneous transformations
a \leftarrow a + 2b + 3c
a is now f(n)
b \leftarrow a
b is now f(n-1)
c \leftarrow b
c is now f(n-2)

This is nothing but a slightly more complex Fibonacci iteration example from earlier.
F(n) = F(n-1) + F(n-2) where F(n) = n if n<2 [latex]F_n = F_{n-1} + F_{n-2}[/latex] [latex]a \leftarrow a + b [/latex] a is now F(n) [latex]b \leftarrow a [/latex] b is now F(n-1) Recursive implementation of f(n) is straightforward:

> (f-rec 1)
1
> (f-rec 3)
4
> (f-rec 6)
59
> (f-rec 8)
335

Iterative implementation of f(n)

> (f 1)
1
> (f 3)
4
> (f 6)
59
> (f 8)
335

Leave a Reply