递归问题

Question

我在创建此递归方法时遇到问题。该方法需要将对象添加到堆栈。

备注： 这是一个路径查找器项目。

getNextBird()民意调查来自鸟类物体内的鸟类队列。如果队列是空的，它将返回null;如果它不是空的，它会返回队列中的下一只鸟。

我根本无法使用任何循环。 （如果可以的话，本来很容易。） 堆栈中的最后一个元素必须是Bird“end”。但是，如果代码工作正常，它应该递归地完成。

我的问题是，有一个边界情况下，支票撞墙getNextBird变为null（在这种情况下，对象鸟），我想从堆栈中弹出最新的对象。我将得到一个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; 
} 

import 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中; import 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但从未使用过。

递归的一个关键是有一个控制语句这将导致递归中断和返回正确的事情或什么都没有。您随机返回true和false（或者可能存在逻辑），它不会为您的执行路径添加任何值。

所以，让我们做一个不同的方式：

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; 
}