Scheme: change recursive process to iterative one

Question

This is the recursive procedure for a function f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n ≥ 3

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

The problem set is to change it to an iterative recursion. I came up with this:

(define (g n)
  (if (< n 3)
      n
      (g-helper n)))

(define (g-helper n)
  (if (< n 3)
      n
      (+ (basemaker 0 1 (- n 1))
         (g-helper (- n 1))
         (* 2 (basemaker 0 2 (- n 2))
            (g-helper (- n 2)))
         (* 3 (basemaker 0 3 (- n 3))
            (g-helper (- n 3))))))

(define (basemaker counter constant n)
  (cond ((= 2 n) 2)
        ((= 1 n) 1)
        ((= 0 n) 0)
        (else
            (basemaker (+ counter constant) constant (- n constant)))))

Something is wrong:

 > (f 3)
4
> (f 4)
11
> (f 5)
25
> (g 3)
6
> (g 4)
19
> (g 5)
45
>

Spent hours on this, but I can't see what I'm doing wrong. I know the code is repetitive and clunky, but I would like to see what I have not understood about the process before I refine the syntax.

Thanks.

Answer 1

A part from the error, the problem with your code is that only the function basemaker is tail-recursive, but not g-helper, since inside its body the “last” call is that of +, not to g-helper itself.

To write a recursive function in a tail-recursive way, usually one transform the function by adding a parameter that “accumulates” the partial result during the computation, and which is returned at the end. In this case, however we need three additional parameters that keep tracks of three results of the function during its computation, since, to calculate the function at a value n, it is necessary to use the three previous values. So here is a possible solution

(define (g n)
  (define (aux n fn1 fn2 fn3)
    (if (< n 3)
        fn1
        (aux (- n 1) (+ fn1 (* 2 fn2) (* 3 fn3)) fn1 fn2)))
  (if (< n 3)
      n
      (aux n 2 1 0)))

Initially, the parameters are assigned the values of the function for n=2, n=1, and n=0 respectively, and during the computation a new value for the function is calculated from the previous three values, and it is passed to the next iteration by “shifting” the other two values. The process terminates when we reach a value less than 3 (that is 2), and the result is the previous result of the function.