CODEWITHSUNDEEP
recursionschemelisp
user50449
user50449

Reputation: 91

Defining a recursive function as iterative?

I have the following recursive function that I need to convert to iterative in Scheme

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

My issue is that I'm having difficulty converting it to iterative (i.e. make the recursion have linear execution time). I can think of no way to do this, because I just can't figure out how to do this.

The function is defined as follows:

f(n) = n if n<3 else f(n-1) + 2f(n-2) + 3f(n-3)

I have tried to calculate it for 5 linearly, like so

1 + 2 + f(3) + f(4) + f(5)

But in order to calculate say f(5) I'd need to refer back to f(4), f(3), f(2) and for f(4) Id have to refer back to f(3), f(2), f(1)

This is a problem from the SICP book.

Upvotes: 2

Views: 104

Answers (1)

jeffruan
jeffruan

Reputation: 294

In the book, authors have an example of formulating an iterative process for computing the Fibonacci numbers.

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
    b
    (fib-iter (+ a b) a (- count 1))))

The point here is that use two parameter a and b to memorise f(n+1) and f(n) during computing. The similar could be applied: we need a, b, c to memorise f(n+2), f(n+1) and f(n)

;; an interative process implementation                                                                                                                       
(define (f-i n)                                                                                                                                               
  ;; f2 is f(n+2), f1 is f(n+1), f0 is f(n)                                                                                                                   
  (define (interative-f f2 f1 f0 count)                                                                                                                       
    (cond                                                                                                                                                     
      ((= count 0) f0)                                                                                                                                         
      (else (interative-f                                                                                                                                      
              (+ f2 (* f1 2) (* f0 3))                                                                                                                          
              f2                                                                                                                                                
              f1                                                                                                                                                
              (- count 1)))))                                                                                                                                   
  (interative-f 2 1 0 n))

Upvotes: 1

Related Questions