0

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.

Improve this question

1 Answer 1

Reset to default
2

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks for your help. I didn't have time to get back to this yet, but I can see from what you wrote how to think about the iteration.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.