## **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

## Problem

A function *f* is defined by the rule that

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