Convert for loop into a recursive function

Question

this is a homework problem. I'm having trouble converting the following into a recursive function:

public class Integrate {
    public static double integrate(int  a, int b, int steps)
    {
        double sum=0;
        double delta = 1.0 * (b - a)/steps;
        double x = a;
        double f = 0.5*x*x + 3*x + 5;

        for (int i = 0; i< steps; i++)
        {
            x = x + delta;
            double fr = 0.5*x*x + 3*x + 5;
            double area = f * delta + 0.5*(fr - f)*delta;
            sum += area;
            f = fr;
        }
        return sum;
    }
    public static void main(String [] args)
    {
        int a, b, step;
        a = Integer.parseInt(args[0]);
        b = Integer.parseInt(args[1]);
        step = Integer.parseInt(args[2]);
        System.out.format("Integral is %f\n", integrate(a,b,step));
    }
}

This is what I have so far but the output is not the same as the original code. I can't figure out what is wrong

public class Integrate {

    public static double integrate(int a, int b, int steps) {
        double sum=0;
        int i=0;
        sum = rintegrate(a, b, steps, i, sum);
        return sum;
    }

    public static double rintegrate(int a, int b, int steps, 
            int i, double sum) {
        double delta = 1.0 * (b - a)/steps;
        double x = a;
        double f = 0.5*x*x + 3*x + 5;
        if (i<steps) {
            x = x + delta;
            double fr = 0.5*x*x + 3*x + 5;
            double area = f * delta + 0.5*(fr - f)*delta;
            sum += area;
            f = fr;
            i++;
            rintegrate(a, b, steps, i, sum);
        }
        return sum;
    }

    public static void main(String[] args) {
        int a, b, step;
        a = Integer.parseInt(args[0]);
        b = Integer.parseInt(args[1]);
        step = Integer.parseInt(args[2]);
        System.out.format("Integral is %f\n", integrate(a,b,step));
    }

}

what is the output from your original code? and what is the output from your new code? — Sam I am says Reinstate Monica
– Sam I am says Reinstate Monica, Commented May 13, 2013 at 16:11
Looks like you're not using the return value from your rintegrate recursively... — Luiggi Mendoza
– Luiggi Mendoza, Commented May 13, 2013 at 16:12
a = 1, b = 10, step=1000....... the original comes out to 360.000061 and mine outputs 0.076662 — user2378481
– user2378481, Commented May 13, 2013 at 16:15
Luiggi Mendoza, I don't understand. How do I use the return value recursively? — user2378481
– user2378481, Commented May 13, 2013 at 16:17
I think he means you're not using it from within rintegrate(). That's probably your problem right there. — Edward Falk
– Edward Falk, Commented May 13, 2013 at 16:26

Sam I am says Reinstate Monica · Accepted Answer · 2013-05-13 16:40:51Z

3

I'm not going to fully analyze the problem, but here are some observations that I have

    if (i<steps) {
        x = x + delta;
        double fr = 0.5*x*x + 3*x + 5;
        double area = f * delta + 0.5*(fr - f)*delta;
        sum += area;
        f = fr;
        i++;
        rintegrate(a, b, steps, i, sum);
    }
    return sum;

everything between sum += area; and return sum; is superfluous.

you're setting f to fr, but you never even use f after that. if you want f to be different next time, maybe you can pass it as a parameter to your recursive function
you're recursively calling rintegrate(...), but you're not doing anything with the value it returns. you might want to use that value.

You should think about recursion as using a smaller version of a problem to solve itself.

Here's some code for your problem assuming that you have a function: segment that just calculates the size of the first segment given a, and delta

rintegrate(a, b, steps)
{
    if(steps <= 1)
    {
        delta = b-a;
        return segment(a, delta)
    }
    else
    {
        delta = (b-a)/steps
        return segment(a, delta) + rintegrate(a+delta, b, steps-1)
    }
}

edited May 13, 2013 at 16:40

answered May 13, 2013 at 16:18

Sam I am says Reinstate Monica

31.3k12 gold badges74 silver badges101 bronze badges

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

9 Comments

user2378481 Over a year ago

With your example, is it calculating from steps and then going down? Is there a way to do it starting from 0?

Sam I am says Reinstate Monica Over a year ago

@user2378481 you're still thinking about the problem iteratively. Try thinking about the problem recursively. Your function needs to add one segment, to the sum of the rest of the segments, and return that value

user2378481 Over a year ago

It's still kind of hard to understand. Is it like carrying over everything from previous step? Sorry, recursion just looks like a loop to me.

Sam I am says Reinstate Monica Over a year ago

@user2378481 think of it this way. Suppose i called your iterative integrate function from the example instead of calling the recursive reintegrate function. Would the example make sense that way?

user2378481 Over a year ago

No, it won't. Is there a reason for recursion? It seems like it is more complicated and the output is less apparent when you rewrite this problem recursively.

|

flavian · Accepted Answer · 2013-05-13 17:11:10Z

1

Working version

Just copy paste and you will get the same output as your original method.

   public static void main(String[] args) {
        int a = 1, b = 10, step = 1000;
            double delta = 1.0 * (b - a) / step;
        double sum = integrate(a, b, step, 0, 0, 0, delta);
        double test = working(a, b, step);
        System.out.println("Integral is " + sum);
        System.out.println("Integral is " + test);
    }

The working recursive version:

    public static double integrate(double x, int b, int steps, int i,
            double sum, double f, double delta) { 
        f = 0.5 * x * x + 3 * x + 5;
        if (i < steps) {
            x = x + delta;
            double fr = 0.5 * x * x + 3 * x + 5;
            double area = f * delta + 0.5 * (fr - f) * delta;
            return integrate(x, b, steps, i + 1, sum + area, fr, delta);
        }
        return sum;
    }

Your original iterative method;

public static double working(int a, int b, int steps) {
    double sum = 0;
    double delta = 1.0 * (b - a) / steps;
    double x = a;
    double f = 0.5 * x * x + 3 * x + 5;

    for (int i = 0; i < steps; i++) {
        x = x + delta;
        double fr = 0.5 * x * x + 3 * x + 5;
        double area = f * delta + 0.5 * (fr - f) * delta;
        sum += area;
        f = fr;
    }
    return sum;
}

edited May 13, 2013 at 17:11

answered May 13, 2013 at 16:21

flavian

28.6k11 gold badges68 silver badges107 bronze badges

3 Comments

user2378481 Over a year ago

Hi, Thanks for your help. Your code is not giving the right output either. The hw problems said to call rintegrate from integrate which was why I had the rintegrate method in the first place.

user2378481 Over a year ago

I see. Yours works now. It's kinda not what I'm looking for but it's helpful to see what's wrong with mine. I don't get where do you calculate delta in your version?

user2378481 Over a year ago

Thanks, I've got a working solution now by declaring delta and x outside the recursive method. But why would they vary between calls if none of the variables associated with them are altered?

rcbevans · Accepted Answer · 2013-05-13 16:58:30Z

0

This is what you want ;)

public class Integrate{

    /**
     * @param args
     */
    public static void main(String[] args) {
        int a, b, step;
        a = Integer.parseInt(args[0]);
        b = Integer.parseInt(args[1]);
        step = Integer.parseInt(args[2]);
        System.out.format("Integral is %f\n",
                adaptiveSimpsons(a, b, step));

    }

    private static double f(double i) {
        return (0.5 * i * i + 3 * i + 5);
    }

    static double adaptiveSimpsons(double a, double b, // interval [a,b]
            int maxRecursionDepth) { // recursion cap
        double c = (a + b) / 2, h = b - a;
        double fa = f(a), fb = f(b), fc = f(c);
        double S = (h / 6) * (fa + 4 * fc + fb);
        return adaptiveSimpsonsAux(a, b, S, fa, fb, fc, maxRecursionDepth);
    }

    private static double adaptiveSimpsonsAux(double a, double b, double S, double fa,
            double fb, double fc, int bottom) {
        double c = (a + b) / 2, h = b - a;
        double d = (a + c) / 2, e = (c + b) / 2;
        double fd = f(d), fe = f(e);
        double Sleft = (h / 12) * (fa + 4 * fd + fc);
        double Sright = (h / 12) * (fc + 4 * fe + fb);
        double S2 = Sleft + Sright;
        if (bottom <= 0)
            return S2 + (S2 - S) / 15;
        return adaptiveSimpsonsAux(a, c, Sleft, fa, fc, fd, bottom - 1)
                + adaptiveSimpsonsAux(c, b, Sright, fc, fb, fe, bottom - 1);
    }
}

Tested and Working

Translated C code given here

answered May 13, 2013 at 16:58

rcbevans

9,1326 gold badges32 silver badges47 bronze badges

1 Comment

rcbevans Over a year ago

No, the integration you are trying to do recursively can be done recursively using simpsons algorithm and as such the methods are named that way. Did you even look at the code? It recursively integrates the function 0.5x^2 + 3x + 5 up to a given number of steps, as stated in OP. If you copy my code into eclipse and run it, you will see that it calculates, recursively, the integral wanted...

Collectives™ on Stack Overflow

Convert for loop into a recursive function

3 Answers 3

9 Comments

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

9 Comments

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related