Exercise 1.11

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

(define (fi n) 
    (f-iter 0 1 2 n))

(define (f-iter a b c count)
  (if (zero? count) 
      a
      (f-iter b 
              c  
              (+ c (* 2 b) (* 3 a))
              (sub1 count))))

9 thoughts on “Exercise 1.11”

1. I feel sorry but I don’t think the Iterative version is right.
   After modifying, it is as follows:

   (define (fun n)
   (define (fun-iter a b c count)
   (cond ((< n 3) n)
   ((zero? count) c)
   (else (fun-iter b
   c
   (+ c (* 2 b) (* 3 a))
   (sub1 count)))))
   (fun-iter 0 1 2 (- n 2)))

   1. Yes I made a mistake (if (zero? count) c …) should be (if (zero? count) a …) – which I’ve finally corrected thank you!

2. What if we just simplify the function to 6f(n -1) then define the recursive function as:

   (define (fr n)
   (if (< n 3) n
   (* 6 (fr (- n 1)))))

   and the iterative one as:

   (define (fi n)
   (fi-sub n 1)

   (define (fi-sub n c)
   (if (< n 3) (* n c)
   (fi-sub (- n 1) (* 6 c))))

   1. But f isn’t a constant value, it’s a function, so f(n-1) + 2f(n-2) + 3f(n-3) ≠ 6f(n-1)

      The first few terms are:
      0, 1, 2, 4, 11, 25, …

      Your solutions both give:
      0, 1, 2, 12, 72, 432, …

3. Oh what is sub1?

   1. It’s a built in Racket procedure which just subtracts 1. There’s also an add1. You don’t need them but those operations are so common that they’re actually very useful.
      (define (sub1 n) (- n 1))
      (define (add1 n) (+ n 1))

      1. thanks!

4. My solution was slightly different;

   (define (f-iter n counter a b c)
   (if (> counter n)
   a
   (f-iter n (1+ counter) (+ a (* 2 b) (* 3 c)) a b)))

   but required the use of one more variable than yours.

5. Another solution. It may help some people.

   (define (f-iter fn-3 fn-2 fn-1 counter max)

   (define fn (+ fn-1 (* 2 fn-2) (* 3 fn-3)))

   (cond
   ((< max 3) max)
   ((= counter max) fn)
   ((< counter max) (f-iter fn-2 fn-1 fn (+ counter 1) max))
   )

   )