为什么我的递归不断抛出 StackOverflow 错误? [英] Why is my recursion keep throwing a StackOverflow error?

问题描述

我正在尝试生成一棵树，包含 8-N 问题，没有重复.我可以在纸上完成，但在代码中我不能.

I am trying to generate a tree, of all the possible states of the 8-N problem, with no duplicates. I can do it on paper but in code I can't.

这是我的递归函数:

......
...
..
        root = new TreeNode(startingState);
        visitedStates.add(root.getData().getStateValues());

        generateStateSpaceRecursive(root);
    }

public void generateStateSpaceRecursive(TreeNode node){

    List<TreeNode> nextStatesNodes = getNextStates(node);

    for (TreeNode childNode : nextStatesNodes){
        if(!stateVisited(childNode.getData().getStateValues())) {
            visitedStates.add(childNode.getData().getStateValues());
            node.addChild(childNode);
            generateStateSpaceRecursive(childNode);
        }
    }
}

为什么不停止?

另外，如果我正确理解问题，它会说，

Also if I understood the problem correctly it says,

实施以下类型的搜索来(尝试)解决这个问题问题:深度优先，广度优先，迭代深化，某种形式启发式搜索.

Implement the following types of search to (try to) solve this problem: depth first, breadth first, iterative deepening, some form of heuristic search.

但我首先需要状态空间，对吗?或者我可以直接应用算法并动态生成状态?

But I need the state space first right? Or I can just apply the algorithms and generate the states on the fly?

private List<TreeNode> getNextStates(TreeNode node) {

        List<TreeNode> nextStates = new ArrayList<>();

        if(agent.canMoveLeft(node)){
            nextStates.add(agent.moveLeft(node));
        }
        if(agent.canMoveRight(node)){
            nextStates.add(agent.moveRight(node));
        }
        if(agent.canMoveUp(node)){
            nextStates.add(agent.moveUp(node));
        }
        if(agent.canMoveDown(node)){
            nextStates.add(agent.moveDown(node));
        }

        return nextStates;
    }

推荐答案

您的状态太大，无法放入堆栈.测试你的算法:

Your state is too big to fit the stack. Test your algorithm:

• 使用较小的样本.
• 或增加堆栈大小(例如 java -Xss4m)

这篇关于为什么我的递归不断抛出 StackOverflow 错误?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！