Recursion Disaster

Think you can’t get a StackOverflowError unless you have an recursive method that fails and undergoes infinite recursion?

Think again.

Try a working recursive method that is called iteratively.

The setup: I am trying to draw M implicitly defined curves by connecting N determined points on each curve. Many algorithms exist for determining points on an implicit function, but I’m using the  Bisection Method, slow but robust and easy to code. The runtime for drawing these curves is O(M*N*log(1/Ɛ)), where Ɛ is the error bound.

Here’s the iterative code for drawing a single curve (which in my case is known as a moist adiabat). I will do this M times (that code will not be shown here for brevity):

public Path2D getMoistAdiabat(double Teq, double fromP, double toP) {
pressureRangeCheck(fromP, toP);
double hiP = fromP;
double t0 = GeneralCalc.tempFromMoistAdiabat(Teq + 273.15, hiP) - 273.15;
double[] bottomPt = tempToCoord(t0, hiP);
Path2D isentrope = new GeneralPath();
isentrope.moveTo(bottomPt[0], bottomPt[1]);

int h = 25; //decrement interval
for (double p = hiP - h; p >= toP; p -= h) {
t0 = GeneralCalc.tempFromMoistAdiabat(Teq + 273.15, p) - 273.15;
double[] pt = tempToCoord(t0, p);
isentrope.lineTo(pt[0], pt[1]);
}
return isentrope;
}

public void graphMoistAdiabat(double Teq) {
graphMoistAdiabat(Teq, highestPres(), 200);
}

public void graphMoistAdiabat(double Teq, double fromP, double toP) {
graphics.draw(getMoistAdiabat(Teq, fromP, toP));
}

And here’s the key function tempFromMoistAdiabat(), which uses the Bisection Method to determine a point on a curve, “T”, from the variables “thE” and “pres”. I originally designed it to be recursive, as shown below:

public static double tempFromMoistAdiabat(double thetaW, double pres) {
//all variables already defined, this code actually in helper method called moistAdiab()
//but I deleted the method
double Tguess_mid = avg(Tguess1, Tguess2);
double thE_mid = psuEqPotentialTemp(Tguess_mid, pres);
if (MathUtils.equalsApprox(thE_target, thE_mid)) {
return Tguess_mid;
} else if (thE_target > thE_mid && thE_target < thE2) { return moistAdiab(thE_target, Tguess_mid, thE_mid, Tguess2, thE2, pres); } else if (thE_target > thE1) {
return moistAdiab(thE_target, Tguess1, thE1, Tguess_mid, thE_mid, pres);
} else if (thE_target > thE2) {
double newT = Tguess2 * 2;
double newThE = psuEqPotentialTemp(newT, pres);
return moistAdiab(thE_target, Tguess2, thE2, newT, newThE, pres);
} else if (thE_target < thE1) {
double newT = Tguess1 - Tguess1;
double newThE = psuEqPotentialTemp(newT, pres);
return moistAdiab(thE_target, newT, newThE, Tguess1, thE1, pres);
}
throw new ArithmeticException();
}

It would throw the error after about 3 curves. So after many trials and errors, I decided [intelligently] to rewrite this iteratively:

public static double tempFromMoistAdiabat(double thetaW, double pres) {
double thE_target = thetaE_thetaW(thetaW);
double Tlow = -150 + 273.15;
double thELow = psuEqPotentialTemp(Tlow, pres);
double Thigh = 150 + 273;
double thEHigh = psuEqPotentialTemp(Thigh, pres);
double Tmid = avg(Tlow, Thigh);
double thEMid = psuEqPotentialTemp(Tmid, pres);
while (!MathUtils.equalsApprox(thE_target, thEMid)) {
if (thE_target - thEMid < 0) { Thigh = Tmid; thEHigh = thEMid; } else if (thE_target - thEMid > 0) {
Tlow = Tmid;
thELow = thEMid;
}
Tmid = avg(Tlow, Thigh);
thEMid = psuEqPotentialTemp(Tmid, pres);
}
return Tmid;
}

And voila! Worked perfectly.

Moral of the story? Think and write iteratively especially when a method will be invoked M*N times. That way you won’t spend 30+ min debugging a working method.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s