Converting recursive function with more calls to iterative function java

Question

Is there a way to convert this recursive algorithm to iterative without using stacks?

public static float T1(int n, float y) {
    if (n == 0)
        return y;
    if (n == 1)
        return 1;

    return 2 * y * T1(n - 1, y) - T1(n - 2, y);
}

What keeps me confused is having two calls inside the recursion, and I'm not sure how to convert that using loops.

It looks like it should be perfectly possible with a single loop, keeping track of the result from the last two iterations to calculate the result for the current iteration. — khelwood
– khelwood, Commented May 15, 2016 at 14:54

khelwood · Accepted Answer · 2016-05-15 15:25:14Z

2

Here is a way to do the same calculation with a for loop.

public static float T1(int n, float y) {
    if (n==0) return y;
    if (n==1) return 1;
    float p1 = 1, p2 = y; // track the previous two values
    for (int i=2; i <= n; ++i) {
        float p = 2*y*p1 - p2; // calculate the result for this iteration
        p2 = p1; // update the previous values to be used in the next iteration
        p1 = p;
    }
    return p1;
}

edited May 15, 2016 at 15:25

answered May 15, 2016 at 15:15

khelwood

59.7k14 gold badges91 silver badges116 bronze badges

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

1 Comment

aarnaut Over a year ago

I was trying to do something with a while loop but wasn't really successful. Thing that confused me the most is two recursive calls. Thanks for clearing this up!

Collectives™ on Stack Overflow

Converting recursive function with more calls to iterative function java

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related