java - 递归——如何只在最后执行一个操作

Question

我有一个二叉搜索树，其中每个节点(GameEntry 类)代表一个“游戏玩法”(名称/分数对)。该树按名称(而不是分数)组织。我正在尝试为树编写一种方法来打印其前十名分数的列表(带有相应的名称)。我想到递归地遍历树，当(且仅当)它是高分时，将节点放入数组(ScoreBoard 类)中。它有效，但我的问题是记分板会打印递归中的每一步。

public void printTopTen()
{
    ScoreBoard board = new ScoreBoard(10); // new scoreboard with capacity of 10
    printTopTenRecur(this.root, board);
}

// Auxillary method for printTopTen()
private void printTopTenRecur(GameEntry node, ScoreBoard board)
{
    if (node == null)
        {
            return;
        }
    printTopTenRecur(node.getLeft(), board);
    board.add(node); // adds the node to the scoreboard if it's a high score
    System.out.println(board);
    printTopTenRecur(node.getRight(), board);
}

我唯一能想到的是在类上创建一个属性(称为board)，然后在递归完成后打印出该属性。但我收到编译时错误 void 无法转换为 String。我不知道还能怎么做。

public String printTopTen()
{
    ScoreBoard board = new ScoreBoard(10); // new scoreboard with capacity of 10
    printTopTenRecur(this.root, board);
    return System.out.println(this.board);
}

// Auxillary method for printTopTen()
private void printTopTenRecur(GameEntry node, ScoreBoard board)
{
    if (node == null)
        {
            return;
        }
    printTopTenRecur(node.getLeft(), board);
    board.add(node); // adds the node to the score board if it's a high score
    this.board = board; // assign local board to the board on the tree
    printTopTenRecur(node.getRight(), board);
}

Answer 1

我不太喜欢递归，尤其是java，主要原因是如果递归太深，就会面临堆栈溢出的风险。其他语言处理这个问题，允许尾部调用隐式转换为 while 循环(例如 scala)。

话虽如此，没有返回值的递归对我来说听起来真的很奇怪，而 Moondaisy 的建议解决了你的问题，我宁愿返回分数而不是依赖于字段。

private ScoreBoard printTopTenRecur(GameEntry node, ScoreBoard board){
  if(node == null )
    return board;

  board.add(node);
  ScoreBoard leftBoard = printTopTenRecur(node.getLeft(), board);
  ScoreBoard rightBoard = printTopTenRecur(node.getRight(), leftBoard);

  return rightBoard;
}

public void printTopTen(){
    ScoreBoard board = new ScoreBoard(10); // new scoreboard with capacity of 10
    // No need to return anything if you want to just print the result
    System.out.println(printTopTenRecur(this.root, board));
}

附注:ScoreBoard leftBoard = printTopTenRecur(...) 像这样毫无用处，board 是可变的，所以传递它就足够了。

当我认为递归时，我也认为不可变，所以我宁愿喜欢ScoreBoard newBoard = board.update(node);返回一个新的更新的记分板，如下所示:

  ScoreBoard currentBoard = board.update(node);
  ScoreBoard leftBoard = printTopTenRecur(node.getLeft(), currentBoard);
  ScoreBoard rightBoard = printTopTenRecur(node.getRight(), leftBoard);

这样 printTopTenRecur 是一个没有副作用的函数，因此是一个正确的函数。