Stack Overflow during Recursion

Question

I am trying to write a program that when given a function and a high and low value, it finds the zero between the high and low. I have written it recursively in a binary search style. When I run a JUnit test, it gives me a stack overflow error unless I give it the base case. Here is the code I am using. Function code:

public class Function implements FunctionInterface{

    public static double f(double x){
        return x*x-4;
    }
}

Code to find zero:

   public class NumericalAnalysis {
    public double solveForZero(Function f, double low, double high) {
        double h = high;
        double l = low;
        double mid = (h+l)/2;
        double x = Function.f(mid);
         if(x == 0.0) {
             return mid;
         }else if(x < 0.0){
             l = mid;
             return solveForZero(f, h, l);
         }else if (x > 0.0){
             h = mid;
             return solveForZero(f, h, l);
         }
         return mid;
    }
}

Test Code:

import static org.junit.Assert.*;
import org.junit.Test; 
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.After;
import org.junit.AfterClass;

public class TestNumericalAnalysis{
    private NumericalAnalysis myAnalyzer;
    @Before
    public void setUp(){
        myAnalyzer = new NumericalAnalysis();
    }
    @Test
    public void testSolveForZero(){
        double ans = myAnalyzer.solveForZero(new Function(), 0.0, 100.0);
        assertEquals(4.0, ans, 0.001); 
    }
}

The function that I am using is x*x-4, the high is 100.0, and the low is 0.0. My hope is that I am missing something incredibly simple and not seeing it.

Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation. [Minimal, complete, verifiable example](http://stackoverflow.com/help/mcve) applies here. We cannot effectively help you until you post your MCVE code and accurately describe the problem. We should be able to paste your posted code into a text file and reproduce the problem you described. Specifically, your given code merely defines a function and quits. Post a *full* MCVE, and stick in a couple of debugging **print** statements. — Prune, Sep 14 '17 at 19:47
Floating point numbers aren't exact, for most cases you'll not find zero this way - better make it find something "close enough to zero". — Vilx-, Sep 14 '17 at 20:00
In other words: x == 0 is never fulfilled. See also https://stackoverflow.com/questions/1088216/whats-wrong-with-using-to-compare-floats-in-java — David Tonhofer, Sep 14 '17 at 20:01

score 2 · Answer 1 · answered Sep 14 '17 at 22:00

I see three problems.

In the recursive calls, it looks like l and h are backwards, so you're recursing on the wrong interval. Thus you'll never find the root, and it'll keep trying until you run out of stack space.
The algorithm assumes that the function being tested is "up and to the right" over the given interval. That won't work if your function decreases over the range (e.g., F(x) = -x). This is why Newton-Raphson iteration, which is a slightly more sophisticated version of this algorithm, requires the derivative of the function.
Lastly, the thing everyone saw in the comments: Floating point representations are typically an approximation. The x for which f(x) is exactly 0 may not be precisely representable. In that case, low, high, and mid may all converge on a value very close to the desired value, but the result won't be exactly 0, so it'll keep recursing without making more progress. This is generally handled by testing for a small range and/or by stopping the recursion when the interval is very small.

Stack Overflow during Recursion

1 Answers1