Переполнение стека на рекурсии в алгоритме цепной дроби

Question

Переполнение стека на рекурсии в алгоритме цепной дроби

Рейтинг: -1Ответов: 1Опубликовано: 01.05.2015

Имеется рекурсивный код для вычисления цепной дроби:

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);
    }
}

Попробую объяснить свою логику: условие
(1/drobchast) - (Math.ceil(1/drobchast) - 1) == 0 предполагает, что если перевернуть дробь и у нее не останется остатка (например, перевернём 1/7 и получим 7), значит дошли до конечной точки.

Иначе нужно передать единицу, деленную на отрезанную от дроби целую часть, плюс единицу, деленную на перевернутую дробь.

Сейчас при запуске моего кода выводится ошибка стека.

java

Источник: Stack Overflow на русском

Answer 1

▲ 2

Функция cep завершится с крайне малой вероятностью, проще сказать, что она никогда не завершится и уйдёт в бесконечную рекурсию.

Проблема в том, что сравнивать дробное число с нулём некорректно из-за особенностей представления чисел с плавающей точкой в компьютерах. Точное равенство нулю вы не получите практически никогда.

Обычно для сравнения с нулём заводят число, меньше которого все дробные числа считаются нулём, например,

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

Из-за того, что в вашей функции используется некорректное сравнение дробного числа с нулём, у вас и происходит переполнение стека на бесконечных рекурсивных вызовах.

Способом более точно работать с дробями будет также создание класса, отдельно хранящего числитель и знаменатель как целые числа. В таком случае не возникнет потери точности при многочисленных операциях с дробью.

На основном сайте есть обсуждение реализации подобного класса

Переполнение стека на рекурсии в алгоритме цепной дроби

Ответы