遞歸問題

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