Получение ошибки StackOverFlow (Java.lang.StackOverFlowError) в рекурсии

Question

Я борюсь со следующим кодом и тестовыми примерами для прохождения.Но получение ошибки переполнения стека из-за рекурсивных вызовов из файла Link.java.

Я уже пытался увеличить размер стека JVM, как предлагалось в некоторых публикациях из переполнения стека, но это не помогло.

Может кто-нибудь дать мне какое-нибудь решение для решения всех тестовых случаев из файла LinkTest.java?

Link.java

public class Link {
    private HashSet<Link> links = new HashSet<Link>();

    public void linkTo(Link link) {
        links.add(link);
    }

    public Boolean isLinkedTo(Link to) {
        Link link;

        while (!links.isEmpty()) {
            link = links.iterator().next();


            if (link == to || link.isLinkedTo(to) == true) {
                if (link == to) {
                    return true;
                } else if (link != to && link.isLinkedTo(to) == true) {
                    return true;
                } else if (link != to && link.isLinkedTo(to) == false) {
                    return false;
                } else {
                    return true;
                }
            } else if (link != to || link.isLinkedTo(to) == false) {
                if (link == to) {
                    return true;
                } else if (link.isLinkedTo(to) == true) {
                    return true;
                } else {
                    return false;
                }
            } else {
                return true;
            }
        }


        return false;
    }
}

LinkTest.java

public class LinkTest extends TestCase
{
    @org.junit.Test
    public void testItCanLinkToItself()
    {
        Link foo = new Link();
        foo.linkTo(foo);
        assertTrue(foo.isLinkedTo(foo));
    }

    public void testItDoesNotLinkToItself()
    {
        Link foo = new Link();
        assertFalse(foo.isLinkedTo(foo));
    }


    public void testUnidirectionalLinkToNeighbour()
    {
        Link foo = new Link();
        Link bar = new Link();
        bar.linkTo(foo);
        assertTrue(bar.isLinkedTo(foo));
        assertFalse(foo.isLinkedTo(bar));
    }

    public void testNeighboursWithConnectionsToThemselves()
    {
        Link foo = new Link();
        Link bar = new Link();
        Link baz = new Link();

        // Connect the Objs to themselves.
        foo.linkTo(foo);
        bar.linkTo(bar);
        baz.linkTo(baz);

        // Connect baz => bar => foo.
        baz.linkTo(bar);
        bar.linkTo(foo);



        assertTrue(baz.isLinkedTo(foo));
        assertTrue(baz.isLinkedTo(bar));
        assertTrue(bar.isLinkedTo(foo));
        assertFalse(bar.isLinkedTo(baz));
    }

    public void testCyclicGraph()
    {
        Link foo = new Link();
        Link bar = new Link();
        Link baz = new Link();

        // Connect the nodes baz => bar => foo => baz.
        baz.linkTo(bar);
        bar.linkTo(foo);
        foo.linkTo(baz);

        assertTrue(baz.isLinkedTo(foo));
        assertTrue(baz.isLinkedTo(bar));
        assertTrue(baz.isLinkedTo(baz));
    }

    public void testItCanHaveNeighboursInCyclicGraph()
    {
        Link foo = new Link();
        Link bar = new Link();
        Link baz = new Link();

        // Connect the nodes baz => bar <=> foo.
        baz.linkTo(bar);
        bar.linkTo(foo);
        foo.linkTo(bar);

        assertTrue(baz.isLinkedTo(foo));
        assertTrue(baz.isLinkedTo(bar));
        assertFalse(baz.isLinkedTo(baz));

    }

    public void testCanHaveACycleOfMoreThanTwo()
    {
        Link foo = new Link();
        Link bar = new Link();
        Link baz = new Link();
        Link qux = new Link();

        // Connect the nodes baz => bar => foo => qux => bar.
        baz.linkTo(bar);
        bar.linkTo(foo);
        foo.linkTo(qux);
        qux.linkTo(bar);

       assertFalse(qux.isLinkedTo(baz));
        assertTrue(baz.isLinkedTo(foo));
        assertTrue(baz.isLinkedTo(bar));
        assertTrue(baz.isLinkedTo(qux));
       assertFalse(baz.isLinkedTo(baz));

    }

}

Answer 1

Полагаю, это сработает, как описывают ваши тесты.

public boolean isLinkedTo(Link to) {
    // start recursion with no currently checked links
    return isLinkedTo(to, new HashSet<>());
}

private boolean isLinkedTo(Link to, Set<Link> linksChecked) {
    // this link is linked to 'to'
    if (links.contains(to)) {
        return true;
    }
    // this link not linked to 'to' so add it to the checked links
    linksChecked.add(this);
    // check all links to see if the links are linked to 'to'
    for (Link link: links) {
        // current link not checked yet and current link is linked to 'to'
        if (!linksChecked.contains(link) && link.isLinkedTo(to, linksChecked)) {
            return true;
        }
    }
    // no links or sub-links are linked to 'to'
    return false;
}

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

Как сказано выше в комментарии Эллиотта, при использовании хэш-набора объектов вы хотите переопределить методы равенства и хэш-кода класса, чтобы гарантировать, что хэш-набор работает должным образом. Большинство идентификаторов могут автоматически сгенерировать для вас действительный хеш-код equals, просто как примечание.