在递归中获取 StackOverFlow 错误 (Java.lang.StackOverFlowError)

Question

我正在努力使以下代码和测试用例通过。但是由于来自 Link.java 文件的递归调用而出现堆栈溢出错误。

我已经尝试增加 JVM 的堆栈大小，因为一些 post 来自堆栈溢出的建议，但它无济于事。

谁能给我一些解决方案来解决 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;
}

要在没有无限递归的情况下递归检查自链接链接，您必须跟踪您已经检查过的链接以避免无限地检查相同的链接。这就是为什么我添加了一个跟踪检查链接的辅助方法。

正如 Elliott 上面的评论所说，当使用对象的哈希集时，您需要覆盖 class 的 equals 和 hashcode 方法以确保哈希集按预期工作。大多数 IDE 都可以为您自动生成 class 的有效等号哈希码，作为旁注。

在递归中获取 StackOverFlow 错误 (Java.lang.StackOverFlowError)

Getting StackOverFlow Error (Java.lang.StackOverFlowError) in recursion

java

recursion

junit

hashset

junit4