Recursion stack overflow in continued fractional algorithm

Question

There is a recursive code for calculating a continued fraction:

import java.math.*; import java.io.*; import java.util.*; public class ContinuedFraction { public static void main(String args[ ]) { double z= cep(1071/462); System.out.println(z); } public static double cep(double drobchast) { if((1/drobchast) - (Math.ceil(1/drobchast) - 1) == 0) { return 1/drobchast; } double celchast = Math.ceil(1/drobchast) - 1; drobchast = 1/(celchast + (1/drobchast)); return cep(drobchast); } }

I will try to explain my logic: condition
(1/drobchast) - (Math.ceil(1/drobchast) - 1) == 0 assumes that if you turn the shot and it does not have a residue (for example, we turn 1/7 and get 7), then we have reached the end point .

Otherwise, you need to transfer the unit divided by the integer part cut off from the fraction, plus the unit divided by the inverted fraction.

Now when I run my code, a stack error is displayed.

For greater clarity, you can make a comment in the question, as well as describe the problem in more detail.
In a state in which there was a question before the change, it would most likely be mined and closed.

Community spirit ♦ one · Answer 1 · 2015-04-30T23:32:53

The cep function will end with an extremely low probability, it is easier to say that it will never end and will go into infinite recursion.

The problem is that comparing a fractional number with zero is incorrect due to the peculiarities of the representation of floating-point numbers in computers. Exact equality to zero, you almost never get.

Usually, for comparison with zero, you get a number, below which all fractional numbers are considered zero, for example,

 EPSILON = 1e-6 if (Math.abs(value) < EPSILON) { // считаем здесь, что value == 0 }

Due to the fact that your function uses an incorrect comparison of a fractional number with zero, you have a stack overflow on endless recursive calls.

The way to more accurately work with fractions will also be the creation of a class that separately stores the numerator and denominator as integers. In this case, there will be no loss of accuracy in multiple operations with the fraction.

The main site has a discussion about the implementation of this class.

I understood this and so that with zero this trick will not pass, but how now to fix it?
You can either enter EPSILON or use the second part of my answer.

Recursion stack overflow in continued fractional algorithm

1 answer 1

More articles: