如何在Java中让递归和for循环一起工作？

Question

我需要递归地创建一个树结构。在树中，每个节点都有不同数量的子节点，因此我认为我需要在 for 循环中递归调用该方法。 for 循环的循环次数与当前节点有子节点的次数相同。

该函数首先创建深度 d 中最左边的子级，然后返回（或应该返回）到前一个深度并创建另一个深度，依此类推。我相信你知道我在这里的意思。所以我试图以这种方式创建整棵树。我设置了一个基本情况，以便如果满足基本情况的条件，则不再递归调用该方法。问题是我的程序以某种方式设法克服了这些条件并继续递归调用该方法，尽管它不应该这样做。

代码如下：

    private void makeTree(GameState prevState, Vector moves, Node parentNode, int index, int depthLimit) {

    if(prevState.getPossibleMoveCount(index) != 0){

        for(int i = 0; i < moves.size(); i++){

            Move thisMove = (Move)moves.get(i);
            GameState newState = prevState.getNewInstance(thisMove);
            Node child = new Node(newState, thisMove);
            parentNode.addChild(child);
            child.setParent(parentNode);

            if((child.getDepth() + 1) < depthLimit){

                int newIndex = switchIndex(index);
                Vector newMoves = newState.getPossibleMoves(newIndex);
                makeTree(newState, newMoves, child, newIndex, depthLimit);

            }else{

                child.setScore(newState.getMarkCount(index));
            }
        }
    }
}

这里的 Node 类不是 Java 默认的 Node 类，而是属于该接口的类。我知道不应该创建一个与某些默认 Java 类同名的类，但这个接口不是我的。我只需要实施它。 Node 类不会与 Java Node 类冲突。所以我认为这不会造成任何问题。

真正的问题是 if((child.getDepth() + 1) < heightLimit) 似乎对程序没有任何影响。程序每次都会继续递归调用该方法，直到达到深度 61，此时内存耗尽。深度限制设置为 5，但正如我所说，这似乎并不重要。

要点是，当程序处于深度“深度限制-1”时，它应该停止递归调用，并为当前节点的子节点设置分数，然后继续为当前节点执行所有这些操作。恰好依次出现的下一个元素。因为这个方法不返回任何东西（void方法），所以不需要任何返回调用，对吗？

我希望你明白我正在尝试做什么以及出了什么问题。任何帮助表示赞赏。如果您需要更多信息，请直接询问，我会尽力更仔细地解释这一点。

提前致谢。

E：方法中的深度限制参数在第一次调用之前给出，并且在树创建过程中不会改变。

Answer 1

您的问题不在于您发布的部分。

我为您的方法中使用的所有类和方法添加了虚拟实现，并且它运行得很好，在级别 6 处停止。

package de.fencing_game.paul.examples;

import java.util.*;

public class RecursionAndLoop {


    private static class Move {
        private String id;
        public Move(String type) {
            this.id = type;
        }
        public String toString(){
            return "Move(" + id + ")";
        }

    }


    private static class GameState {
        private static int nextID;

        private int id;

        GameState() {
            this.id = nextID++;
        }

        public GameState getNewInstance(Move move) {
            return new GameState();
        }

        public int getPossibleMoveCount(int index) {
            return 5;
        }

        public Vector<Move> getPossibleMoves(int index) {
            Vector<Move> v = new Vector<Move>();
            for(int i = 0; i < 5; i++) {
                v.add(new Move(index + "×" + i));
            }
            return v;
        }

        public int getMarkCount(int index) {
            return 20 + index;
        }

        public String toString() {
            return "GameState[" + id + "]";
        }
    }

    private static class Node {
        private GameState state;
        private Move move;

        private List<Node> children;
        private Node parent;
        private int score;

        public Node(GameState s, Move m) {
            this.children = new ArrayList<Node>();
            this.state = s;
            this.move = m;
        }

        public void addChild(Node child) {
            children.add(child);
        }

        public void setParent(Node node) {
            parent = node;
        }

        public void setScore(int neu) {
            this.score = neu;
        }

        public int getDepth() {
            if(parent == null) {
                return 0;
            }
            return 1 + parent.getDepth();
        }

        /**
         * prints a simple tree view of this ZipNode and its descendants
         * on {@link System.out}.
         * @param prefix a prefix string to add before all lines.
         * @param self a prefix string to add before the line of this node
         *    itself (after the general prefix).
         * @param sub a prefix string to add before the line of all subnodes
         *    of this node (after the general prefix).
         */
        private void printTree(String prefix,
                               String self,
                               String sub) {
            System.out.println(prefix + self + state + " - " + move +
                               " - " + score);
            String subPrefix = prefix + sub;
            // the prefix strings for the next level.
            String nextSelf = " ├─ ";
            String nextSub =  " │ ";
            Iterator<Node> iterator =
                this.children.iterator();
            while(iterator.hasNext()) {
                Node child = iterator.next();
                if(!iterator.hasNext() ) {
                    // last item, without the "|"
                    nextSelf = " └─ ";
                    nextSub =  "   ";
                }
                child.printTree(subPrefix, nextSelf, nextSub);
            }
        }



    }


    int switchIndex(int index) {
        return index + 1;
    }



    private void makeTree(GameState prevState, Vector<Move> moves, Node parentNode, int index, int depthLimit) {

        if(prevState.getPossibleMoveCount(index) != 0){

            for(int i = 0; i < moves.size(); i++){

                Move thisMove = moves.get(i);
                GameState newState = prevState.getNewInstance(thisMove);
                Node child = new Node(newState, thisMove);
                parentNode.addChild(child);
                child.setParent(parentNode);

                if((child.getDepth() + 1) < depthLimit){

                    int newIndex = switchIndex(index);
                    Vector<Move> newMoves = newState.getPossibleMoves(newIndex);
                    makeTree(newState, newMoves, child, newIndex, depthLimit);

                }else{

                    child.setScore(newState.getMarkCount(index));
                }
            }
        }
    }


    public static void main(String[] params) {
        GameState start = new GameState();
        Vector<Move> m = new Vector<Move>();
        m.add(new Move("start"));
        Node root = new Node(start, null);
        int index = 7;
        int depthLimit = 6;
        new RecursionAndLoop().makeTree(start, m, root, index, depthLimit);
        root.printTree("", " ", "");
    }

}

（我对泛型类型进行了一些更改以避免编译器警告。）

以下是深度限制 = 4 的输出：

GameState[0] - null - 0
└─ GameState[1] - Move(start) - 0
   ├─ GameState[2] - Move(8×0) - 0
   │  ├─ GameState[3] - Move(9×0) - 29
   │  ├─ GameState[4] - Move(9×1) - 29
   │  ├─ GameState[5] - Move(9×2) - 29
   │  ├─ GameState[6] - Move(9×3) - 29
   │  └─ GameState[7] - Move(9×4) - 29
   ├─ GameState[8] - Move(8×1) - 0
   │  ├─ GameState[9] - Move(9×0) - 29
   │  ├─ GameState[10] - Move(9×1) - 29
   │  ├─ GameState[11] - Move(9×2) - 29
   │  ├─ GameState[12] - Move(9×3) - 29
   │  └─ GameState[13] - Move(9×4) - 29
   ├─ GameState[14] - Move(8×2) - 0
   │  ├─ GameState[15] - Move(9×0) - 29
   │  ├─ GameState[16] - Move(9×1) - 29
   │  ├─ GameState[17] - Move(9×2) - 29
   │  ├─ GameState[18] - Move(9×3) - 29
   │  └─ GameState[19] - Move(9×4) - 29
   ├─ GameState[20] - Move(8×3) - 0
   │  ├─ GameState[21] - Move(9×0) - 29
   │  ├─ GameState[22] - Move(9×1) - 29
   │  ├─ GameState[23] - Move(9×2) - 29
   │  ├─ GameState[24] - Move(9×3) - 29
   │  └─ GameState[25] - Move(9×4) - 29
   └─ GameState[26] - Move(8×4) - 0
      ├─ GameState[27] - Move(9×0) - 29
      ├─ GameState[28] - Move(9×1) - 29
      ├─ GameState[29] - Move(9×2) - 29
      ├─ GameState[30] - Move(9×3) - 29
      └─ GameState[31] - Move(9×4) - 29

Answer 2

当您在 if 语句内部调用时，

makeTree(newState, newMoves, child, newIndex, depth);

您期望深度来自哪里？看起来您正在将深度传递给 makeTree 例程，但期望它是当前节点的深度（也许是 this.depth ？）