java - 递归问题

Question

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

注释:这是一个路径查找器项目。

getNextBird() 从鸟对象内的鸟队列中进行轮询。如果队列为空则返回null；如果它不为空，它将返回队列中的下一只鸟。

我根本无法使用任何循环。 (如果我能的话，那就很容易了。)堆栈中的最后一个元素必须是 Bird“end”。但如果代码工作正常，则应该递归地完成。

我的问题是，存在一种边缘情况，即检查碰壁，其中 getNextBird 变为 null(在本例中为对象 Bird)，并且我想从堆栈中弹出最新的对象。我将收到 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 但从未使用过它。

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

那么，让我们用不同的方式来做:

1. 除非需要，否则不要将任何内容压入堆栈，这样只有在打印时才需要弹出。您需要插入堆栈的第一只鸟是与表达式(current == end)匹配的finalbird。
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;
}