Как получить рекурсию и совместную работу в Java?

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 - это не класс Node по умолчанию для Java, а класс, принадлежащий этому интерфейсу. Я знаю, что нельзя создавать класс с тем же именем, которое уже дано некоторому классу Java по умолчанию, но этот интерфейс не мой. Я просто должен это реализовать. Класс Node не конфликтует с классом Java Node. Поэтому я не думаю, что это вызывает какие-либо проблемы.

Реальная проблема заключается в том, что if ((child.getDepth () + 1) , похоже, не влияет на программу. Программа продолжает вызывать метод рекурсивно каждый раз, пока он не достигнет глубины 61, в которой память заканчивается. Ограничение глубины установлено на 5, но, как я уже сказал, это не имеет значения.

Дело в том, что когда программа находится в глубине "deepLimit -1" , она должна прекратить рекурсивный вызов и вместо этого установить оценки для дочерних элементов текущего узла, а затем продолжить делать все эти вещи для следующего элемента, который оказывается в очереди. Поскольку этот метод ничего не возвращает (метод void), не требуется никаких обратных вызовов, верно?

Надеюсь, вы поняли, что я пытаюсь сделать и что идет не так. Любая помощь приветствуется. А если вам нужна дополнительная информация, просто спросите, и я постараюсь объяснить это более внимательно.

Заранее спасибо.

E: Аргумент deepLimit в методе перед первым вызовом не изменяется при создании дерева.

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("", " ", "");
    }

}

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

Вот вывод для deepLimit = 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

при звонке

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

в вашем утверждении if, откуда вы ожидаете глубины? Похоже, что вы переходите в глубину к подпрограмме makeTree, но ожидаете, что она будет глубиной текущего узла (this.depth возможно?)