CODEWITHSUNDEEP
javarecursion
aarnaut
aarnaut

Reputation: 557

Converting recursive function with more calls to iterative function java

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.

Upvotes: 1

Views: 201

Answers (1)

khelwood
khelwood

Reputation: 59112

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;
}

Upvotes: 2

Related Questions