java - Java中具有全局变量的递归调用

Question

我有一棵树，想计算每个左节点和右节点的总和。
树的布局是

 3  
/ \  
1  8  
  / \  
 6  15  
    / \  
   9   20  
      /  \  
     16  25  

public class BinarySearchTree {
    public int left_sum = 0;
    public int right_sum = 0;

    public int count_sum(Node x) {
        if (x == null) return 0;

        left_sum += count_sum(x.left);
        right_sum += count_sum(x.right);

        System.out.printf("left_sum = %d right_sum=%d\n", left_sum, right_sum);
        return x.data;
    }
}

但是right_sum不正确。该值只是节点值。

left_sum = 0 right_sum=0  
left_sum = 1 right_sum=0  
left_sum = 7 right_sum=0  
left_sum = 16 right_sum=0  
left_sum = 32 right_sum=0  
left_sum = 32 right_sum=25  
left_sum = 32 right_sum=20  
left_sum = 32 right_sum=15  
left_sum = 32 right_sum=8  

如果我在count_sum（）中添加一个局部变量'int right'并修改为

public int count_sum(Node x) {
    int right;

    if (x == null) return 0;

    left_sum += count_sum(x.left);
    right = count_sum(x.right);
    right_sum += right;

    System.out.printf("left_sum = %d right_sum=%d\n", left_sum, right_sum);
    return x.data;
}

left_sum = 0 right_sum=0  
left_sum = 1 right_sum=0  
left_sum = 7 right_sum=0  
left_sum = 16 right_sum=0  
left_sum = 32 right_sum=0  
left_sum = 32 right_sum=25  
left_sum = 32 right_sum=45  
left_sum = 32 right_sum=60  
left_sum = 32 right_sum=68  

结果现在是正确的。为什么呢

Answer 1

很难说是怎么回事。但是，我可以告诉您为什么这两段代码的行为不同。当你说

right_sum += count_sum(x.right);

这和

right_sum = right_sum + count_sum(x.right);

代码以这种方式对其进行评估：


读取right_sum的值
调用count_sum（这会更改right_sum的值）
使用在步骤1中获得的值将right_sum添加到count_sum返回的值中


相比之下：

right = count_sum(x.right);
right_sum += right;

这与

right = count_sum(x.right);
right_sum = right_sum + right;

以不同的顺序执行操作：


调用count_sum（这会更改right_sum的值）
读取right_sum的值，该值是right_sum已更改的count_sum新值。
读取right的值（count_sum方法的结果）
加两个


因此，您可以了解为什么结果会有所不同。

我认为这里的道理是在编写递归方法时绝对不要使用全局变量。几乎不可能弄清楚代码在做什么，因为您正在使用全局变量，并以更改全局变量的方式递归调用该方法。 （根据经验，我对此非常熟悉。我以前从事过编译器工作，而编译器本质上具有很多树和递归代码。
 我有很多偏头痛试图调试代码，这些代码中有人在递归例程中使用了全局变量。）因此，您无法确定您使用的值以及何时使用。我要说明的一个例外是，您可以拥有某种全局集合（例如List或Set），并编写添加到此集合的递归方法，但从不读取它。那很安全。

那么如何在不使用全局变量的情况下编写此代码？您必须考虑如何编写返回所有所需信息的递归帮助器方法。因此，在这里，您可能有一个countLeftAndRight方法，该方法返回具有两个字段的对象，其中一个是左节点的总和，一个是右节点的总和。您可以这样声明一个内部类：

private static class LeftAndRightSum {
    public int leftSum;
    public int rightSum;
    public LeftAndRightSum(int l, int r) { leftSum = l; rightSum = r; }
}

因此，countLeftAndRight(t)将返回一对{L，R}，其中L是左节点的总和，R是右节点的总和，并且根中的值都不计入两个和。在使用递归时，对递归方法的作用进行非常精确的定义会有所帮助。 （实际上，它对每个程序中的每个方法都有帮助，但是对于递归尤为重要。）

那么countLeftAndRight将如何工作？


在左侧子树上递归调用countLeftAndRight，返回{L1，R1}。
在右侧子树上递归调用countLeftAndRight，返回{L2，R2}。
请记住，countLeftAndRight不会在其中添加根的值，这意味着您尚未添加左节点（左子树的根）或右节点的值。因此，现在您的结果将是{L1 + L2 + left.value，R1 + R2 + right.value}。


您需要对空子树进行一些明显的调整。

如果没有全局变量，以这种方式进行操作将使代码更容易理解，并且您将更有把握地保证它是正确的。

更多：我想到了另一个道理：如果您有修改全局变量的方法，请不要在其他地方使用相同全局变量的表达式中调用该方法。 （因此，即使在非递归情况下，也应避免使用left_sum += count_sum(x.left)，因为count_sum会修改left_sum。）在Java中，至少行为是明确定义的，但会使程序难以理解。在其他语言（如C ++）中，这会产生非常讨厌的结果，因为语言规则允许编译器在评估事物的顺序方面有一定的自由度，这意味着使用不同的编译器可以获得不同的结果。很坏。不惜一切代价避免这种情况。