我正在尝试编写一个程序,当给定一个函数和一个高值和低值时,它会找到高值和低值之间的零。我以二分搜索的方式递归地编写了它。当我运行 JUnit 测试时,除非我给出基本情况,否则它会给我一个堆栈溢出错误。这是我正在使用的代码。 功能代码:
public class Function implements FunctionInterface{
public static double f(double x){
return x*x-4;
}
}
查找零的代码:
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;
}
}
测试代码:
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);
}
}
我使用的函数是x*x-4,最高为100.0,最低为0.0。我希望我错过了一些非常简单的东西并且没有看到它。
最佳答案
我发现三个问题。
在递归调用中,
l
和h
看起来是向后的,因此您在错误的间隔上进行递归。因此,你永远找不到根,它会一直尝试,直到你用完堆栈空间。该算法假设被测试的函数在给定的时间间隔内“向上且向右”。如果您的函数在该范围内减小(例如,
F(x) = -x
),那么这将不起作用。这就是为什么Newton-Raphson iteration ,这是该算法的稍微复杂的版本,需要函数的导数。最后,每个人都在评论中看到:浮点表示通常是近似值。
f(x)
恰好为 0 的x
可能无法精确表示。在这种情况下,低、高和中可能都会收敛到非常接近期望值的值,但结果不会恰好为 0,因此它将继续递归而不会取得更多进展。这通常是通过测试小范围和/或在间隔非常小时停止递归来处理的。
关于java - 递归期间堆栈溢出,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46226865/