Проблемы с рекурсией

Question

У меня возникли проблемы с созданием этого рекурсивного метода. Метод должен добавить объекты в стек.

Примечания: Это проект поиска пути.

getNextBird() опросы из очереди птиц внутри объекта птицы. Если очередь пуста, она возвращает null; если он не пуст, он вернет следующую птицу внутри очереди.

Я не могу использовать какие-либо петли вообще. (Это было бы легко, если бы я мог.) Последний элемент в стеке должен быть «конец» птицы. Но если код работает нормально, это должно быть сделано рекурсивно.

Моя проблема в том, что есть чехол, где чеки попадают в стену, где getNextBird становится нулевым (в данном случае птица объекта), и я хочу вытащить новейший объект из стека. Я получу ошибку StackOverflow или ошибку EmptyCollection.

private static boolean recurse(Stack<Bird> path, Bird current, Bird end) 
{ 
    Bird bird = null; 
    if (current != null) { 
     bird = current.getNextBird(); 
     if (bird != null) { 
      path.push(current); 
      recurse(path, bird, end); 
      return true; 
     } 
    } 
    return false; 
} 

импорт java.util.Stack;

public class Solve2 
{ 
    public static void main(String [] args) 
    { 
    // create the maze to solve 
    Maze maze = new Maze(); 

    // create a Stack of Bird objects named path here 
    Stack<Bird> path = new Stack<Bird>(); 

    // call recursive method to solve the maze and print the path 
    recurse(path, maze.getStart(), maze.getEnd()); 
    print(path); 
    } 


    private static boolean recurse(Stack<Bird> path, Bird current, Bird end) 
    { 
     Bird bird = null; 
     if (current != null) { 
      bird = current.getNextBird(); 
      if (bird != null) { 
       path.push(current); 
       recurse(path, bird, end); 
       return true; 
      } else { 
       path.pop(); 
       recurse(path, path.peek(), end); 
       return false; 
      } 
     } 
     return false; 
    } 


    private static void print(Stack<Bird> stack) 
    { 
    // write your code for recursively printing the stack here 
System.out.println(stack.pop()); 
print(stack); 

    } 

} 

Птица Класс:

public class Bird 
{ 
    public static final int N = 0; 
    public static final int NE = 1; 
    public static final int E = 2; 
    public static final int SE = 3; 
    public static final int S = 4; 
    public static final int SW = 5; 
    public static final int W = 6; 
    public static final int NW = 7; 

    private static final String [] directions = {"N ", "NE", "E ", "SE", "S ", "SW", "W ", "NW"}; 

    private String name; 
    private int direction; 
    private Queue<Bird> queue; 

    public Bird(int row, int column, int direction) 
    { 
    this.name = "Row/Column [" + row + "][" + column + "]"; 
    this.direction = direction; 
    } 

    public void setBirdQueue(Queue<Bird> queue) 
    { 
    this.queue = queue; 
    } 

    public String toString() 
    { 
    return "Location: " + name + ", Direction: " + directions[direction]; 
    } 

    public int getDirection() 
    { 
    return this.direction; 
    } 
    public Bird getNextBird() 
    { 
    // write code to return the next Bird from the queue or null if no Birds left. 
     return queue.poll(); 
    } 
} 

импорт java.util.LinkedList; импорт java.util.Queue;

public class Maze 
{ 
    private Bird start; 
    private Bird end; 

    public Maze() 
    { 
    // construct the diagrammed maze 
    int MAX_ROW = 5; 
    int MAX_COL = 7; 
    Bird [][] maze = new Bird[MAX_ROW][MAX_COL]; 

    // row 0 
    maze[0][0] = new Bird(0, 0, Bird.S); 
    maze[0][1] = new Bird(0, 1, Bird.SW); 
    maze[0][2] = new Bird(0, 2, Bird.S); 
    maze[0][3] = new Bird(0, 3, Bird.SE); 
    maze[0][4] = new Bird(0, 4, Bird.SW); 
    maze[0][5] = new Bird(0, 5, Bird.SW); 
    maze[0][6] = new Bird(0, 6, Bird.SW); 

    // row 1 
    maze[1][0] = new Bird(1, 0, Bird.S); 
    maze[1][1] = new Bird(1, 1, Bird.W); 
    maze[1][2] = new Bird(1, 2, Bird.SW); 
    maze[1][3] = new Bird(1, 3, Bird.S); 
    maze[1][4] = new Bird(1, 4, Bird.N); 
    maze[1][5] = new Bird(1, 5, Bird.S); 
    maze[1][6] = new Bird(1, 6, Bird.W); 

    // row 2 
    maze[2][0] = new Bird(2, 0, Bird.NE); 
    maze[2][1] = new Bird(2, 1, Bird.NW); 
    maze[2][2] = new Bird(2, 2, Bird.N); 
    maze[2][3] = new Bird(2, 3, Bird.W); 
    maze[2][4] = new Bird(2, 4, Bird.SE); 
    maze[2][5] = new Bird(2, 5, Bird.NE); 
    maze[2][6] = new Bird(2, 6, Bird.E); 

    // row 3 
    maze[3][0] = new Bird(3, 0, Bird.SE); 
    maze[3][1] = new Bird(3, 1, Bird.NE); 
    maze[3][2] = new Bird(3, 2, Bird.E); 
    maze[3][3] = new Bird(3, 3, Bird.NW); 
    maze[3][4] = new Bird(3, 4, Bird.NW); 
    maze[3][5] = new Bird(3, 5, Bird.E); 
    maze[3][6] = new Bird(3, 6, Bird.W); 

    // row 4 
    maze[4][0] = new Bird(4, 0, Bird.N); 
    maze[4][1] = new Bird(4, 1, Bird.NE); 
    maze[4][2] = new Bird(4, 2, Bird.N); 
    maze[4][3] = new Bird(4, 3, Bird.N); 
    maze[4][4] = new Bird(4, 4, Bird.NE); 
    maze[4][5] = new Bird(4, 5, Bird.W); 
    maze[4][6] = new Bird(4, 6, Bird.N); 

    start = maze[2][0]; 
    end = maze[2][6]; 

    // write your code here 
    /*snipped the logic for adding the birds in the queue, but I do know that this part is 100% functional on my end*/ 
    } 

    public Bird getStart() 
    { 
    return this.start; 
    } 

    public Bird getEnd() 
    { 
    return this.end; 
    } 

} 

Answer 1

Хорошо, одна вещь, которую я вижу, что вы прошли параметр end в рекурсии, но никогда не использовал это.

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

Итак, давайте сделаем это по-другому:

1. Ничего не пихать в стеке, если вам это нужно, так что вы должны совать только тогда, когда вы печатаете. Первой птицей, которую нужно нажать в стек, является финишная птица, соответствующая выражению (current == end).
2. Если у птицы нет возврата к предыдущей птице, указывающей, что путь заблокирован. Теперь, чтобы соответствовать этому, с шагом 1, если (current == end) вернет что-то предыдущей птице, указав, что конечная птица найдена и передается с каждой птицей в цепочке первой птице.

псевдокод:

recursive(stack, current, end) 
{ 
    if(current == end){ 
     stack.push(current); //push the final bird 
     return true; //indication that final is found 
    } 
    else if(current.getNext() != null){ 
     result = recurse(stack, current.getNext(), end); //recurse 
     if(result == true) 
      stack.push(current); // using indication from the chain 

     return result; 
    } 

    return false; 
}