Java recursions, help

[nfm]

I need help with recursion within this code, this is a Bisection Method which finds zero of a function between two numbers which their product is < 0. I could use "for" to loop division between 2 points but I can't use that, recursion has to be done. This is a homework which I cannot finish and can't get help from teacher, they expect us to get it work by ourselves. Any help will be greatly appreciated, and I'll more than happy understand recursions better.

I hope somebody understands this because I really don't, I can do this on piece of paper but not in java :(

Solved: See post #5 for working code :)

[mtzki]

So if i got it right, you should be programming the bisection method to find a zero of the function f, with the example f(x)=x-2 used here.

The bisection method is based on the idea that if f is continous on an interval [a,b] and we have f(a)*f(b)<0, then f must have a zero in the interval (Bolzano's theorem).

I'll try to point the crucial mistakes in the above code.



if (lo * mi == 0) return mi;
if (lo * mi < 0)

You should be testing the values of f here at lo and mi.



if (lo * mi < 0)
{
hi = mi; // root lies between x lo and mi
if (abs(f(mi)) < tolerance) return mi;
return mi;
}

The recursion should happen here. You must call root(lo,mi) in the last line, not return mi.



if (lo * mi > 0)
{
lo = mi; // root lies between x hi and mi
if (abs(f(mi)) < tolerance) return mi;
return mi;
}
return mi;

The same changes here, now testing the values of f at mi and hi. Check the direction of the inequality.



double x = root(4, -1); // feeding in two numbers

Also (for readability only, should work without this) -1 and 4 should be swapped here, or lo and hi in the definition of root.

Hope this helps.

[nfm]

good day mtzki,

Now I know that the recusions has to happen in "root" method, before know ing that I was trying to run recursion from "f" method in "root" method which doesn't make sense :p:

As for now, I not sure about "if (f(lo) * f(mi) < 0)" and why "f" function has mid - 2. Thank you very much ;)


public class BisectionMethod
{
public static void main(String[] args)
{
root(-1, 4); // feeding in two numbers
}

private static double root(double lo, double hi)
// Pre any two numbers
// Post returns root
{
double tolerance = 0.0001; // precision
double mi = (lo + hi) / 2; // finding out midpoint

if (lo * mi == 0) System.out.println(mi);
if (f(lo) * f(mi) < 0)
{
hi = mi; // root lies between x lo and mi
if (abs(f(mi)) < tolerance) System.out.println(mi);
return root(lo, mi);
}
if (f(lo) * f(mi) > 0)
{
lo = mi; // root lies between x hi and mi
if (abs(f(mi)) < tolerance) System.out.println(mi);
return root(hi, mi);
}
return mi;
}

private static double abs(double n)
// Pre accepts any double
// Post returns an absolute value
{
if (n > 0) return n;
return (-1 * n);
}

private static double f(double mi)
{
return (mi - 2);
}
}

This is the result I get when I run this piece of code:

2.000030517578125
1.9999542236328125
1.9999923706054688
2.000011444091797
2.000001907348633
1.9999971389770508
1.9999995231628418
2.0000007152557373
2.0000001192092896
1.9999998211860657
1.9999999701976776
2.0000000447034836
2.0000000074505806
1.999999988824129
1.9999999981373549
2.0000000027939677
2.0000000004656613
1.999999999301508
1.9999999998835847
2.000000000174623
2.000000000029104
1.9999999999563443
1.999999999992724
2.000000000010914
2.000000000001819
1.9999999999972715
1.9999999999995453
2.000000000000682
2.0000000000001137
1.9999999999998295
1.9999999999999716
2.0000000000000426
2.000000000000007
1.9999999999999893
1.9999999999999982
2.0000000000000027
2.0000000000000004
1.9999999999999993

[mtzki]

If f(lo)*f(mi)<0, then f(lo) and f(mi) have different signs and f must have the value 0 somewhere in [lo,mi].

Using 'mi' as an argument of f is confusing. It could be e.g.



private static double f(double arg) {
return arg-2;
}


So it's the function for which you're searching a zero. Defined as above it is f(x)=x-2. I'm not sure if that is what it should be, seems a little boring for an example. With this you should be getting a value close to 2 at the end.



if (lo * mi == 0) System.out.println(mi);

You should be testing the values of f, not checking if lo or mi is 0.



if (f(lo) * f(mi) < 0)
{
hi = mi; // root lies between x lo and mi
if (abs(f(mi)) < tolerance) System.out.println(mi);

We go into an endless loop. You should return mi (as in the first version).



if (f(lo) * f(mi) > 0)
{
lo = mi; // root lies between x hi and mi
if (abs(f(mi)) < tolerance) System.out.println(mi);
return root(hi, mi);
}
return mi;
}

The inequality has wrong direction. The execution never gets to the last line where you are trying to return mi.

[nfm]

oh man, now that i finally understand this concept, i wrote this:


//need.for.mhz
//This program finds the root

public class BisectionMethod
{
public static void main(String[] args)
{
root(-1, 4); // feeding in two numbers
}

private static float root(float lo, float hi)
// Pre any two numbers
// Post returns root
{
float tolerance = (float)0.001; //Precision
float mi = (lo + hi) / 2; //Finding out midpoint

//if (f(lo) * f(mi) == 0) System.out.println(mi);
if (f(lo) * f(mi) < 0) return root(lo, mi);
if (f(lo) * f(mi) > 0) return root(mi, hi);
if (abs(f(mi)) < tolerance) System.out.println("Root: " + mi);
return 0;
}

private static float abs(float n)
//Pre accepts any float
//Post returns an absolute value
{
if (n > 0) return n;
return (-1 * n);
}

private static float f(float n)
//Function, type any equation you need, e.g (x^3) + (x^2) +4
{
return (n - 3);
}
}

it returns root 3.0, which is what we want ;)

[mtzki]

Good. :)

The tolerance check should be before the other two if sentences in root. Something like this:



private static float root(float lo, float hi)
// Pre any two numbers
// Post returns root
{
float tolerance = (float)0.001; //Precision
float mi = (lo + hi) / 2; //Finding out midpoint

if (abs(f(mi)) < tolerance) {
System.out.println("Root: " + mi);
return mi;
}
if (f(lo) * f(mi) < 0) return root(lo, mi);
else return root(mi, hi);
}

[VisiV]

heh, was this out of a book or something they gave to you. And if it's a book, which book. I would say what mine is, but I dont remember off the top of my head, all I know is it's a big piece of crap.