当Java中的+=遇到递归时出现的问题及原因探究（字节码相关）

昨天收到了我的算法老师给我发的一封邮件，他的一个学生在使用Java写算法时遇到了一个比较奇怪的问题。因为老师平时的主力语言是C++，所以他调试后也觉得问题很奇怪，就抛给了我这个Javaer。

问题

问题代码大致如下，简略去了算法的大部分逻辑，只留下出问题的部分：

public class StrangeTest {

    int cnt;

    public int solve(int x){
        cnt = 0;
        dfs(x);
        return cnt;
    }

    private int dfs(int x){

        if(x == 0) return 1;

//        int t = dfs(x - 1);
//        cnt += t;

        cnt += dfs(x - 1);

        return 0;
    }

    public static void main(String[] args) {
        System.out.println(new StrangeTest().solve(3));
    }
}

他写了一个递归函数dfs ，在传入的参数 x 为 0 的时候，返回 1，否则返回 0。

cnt 在递归的过程中累加 dfs 的返回值。此处他用了一个类成员变量cnt ，来当做一个dfs过程的全局变量使用。

如果调用dfs(3)，道理上最后 cnt的结果为 1。因为只有在 x == 0 的时候，dfs返回了 1，其他时候都是 0。

这段代码如果是运行在C++中，那么最后的输出结果是正确的，即 cnt = 1 . 但是这段代码运行在Java中，最后显示的结果却是 cnt = 0 . 这也是我老师疑惑的地方，随后他把cnt += dfs(x - 1) 一句话拆成：int t = dfs(x - 1); cnt += t; 两句话（他之所以这么拆，是因为想单步跟踪每次 dfs的返回值），他发现拆分之后答案就正确了！cnt 变成了 1，这两种看上去逻辑等价的写法，结果却一个是错误的，一个是正确的，看上去确实很让人费解.

分析问题

我之前也没有遇到过这种问题，感觉挺神奇的，于是就做了一下分析.

首先我也跟老师一样debug跟踪了一下代码（cnt += dfs(x - 1)这种写法），发现一个很神奇的现象，那就是当我们执行到倒数第二次递归的时候，即dfs(x = 1)的时候，因为倒数第一次的dfs(x = 0)返回了1，所以此时的cnt是为1的，即此时的cnt的值是正确的 . 但是如果我们继续往下走，走到倒数第三次递归dfs(x = 2)的时候却发现cnt很神奇的又变成0，后面的递归也不用看了，cnt都变成了0 .

因吹斯听！

因为我并不确定这是编译期的问题还是运行时的问题，所以我首先看了一下前端编译器javac编译后的字节码指令，此处字节码指令比较多，我们只看核心的dfs()方法的字节码指令：

 0 iload_1		//可以理解为将存放在本地变量表中下标为1的变量推送到操作数栈顶（即推送x,下标为0的变量是this）
 1 ifne 6 (+5)		//当操作数栈栈顶元素不等于0时（即x != 0），跳转到第6行，否则继续往下走
 4 iconst_1		//不跳转时的逻辑（即栈顶元素为0）加载常数1到栈顶
 5 ireturn		//返回栈顶元素（4，5行加起来即return 1）  此dfs栈帧结束

 6 aload_0              //x = 0时的逻辑，此句是this相关  忽略
 7 dup                  //忽略
 8 getfield #2 <StrangeTest1.cnt>       //获取类的实例域并将其压入栈顶（即获取cnt）
11 aload_0              //this相关  忽略
12 iload_1              //将存放在本地变量表中下标为1的变量推送到操作数栈顶（即推送x）
13 iconst_1             //加载常数1到栈顶
14 isub                 //将栈顶的两个元素出栈，相减，将结果压入栈顶（即将x-1结果入栈，x与1都出栈）
15 invokespecial #3 <StrangeTest1.dfs>      //递归的调用dfs方法，新dfs栈帧销毁时返回return的值压入栈顶
18 iadd                 //上面dfs return的值（此时的操作数栈顶元素）与它下面的元素出栈相加，结果入栈    注意下面的元素是触发invokespecial dfs递归调用之前压入的cnt的值
19 putfield #2 <StrangeTest1.cnt>       //为指定类实例域赋值  （即将相加的结果赋给cnt）
22 iconst_0             //加载常数0到栈顶
23 ireturn              //返回栈顶元素 （即return 0） 此dfs栈帧结束

大家都知道JVM是一个基于栈的虚拟机，所以每个线程都会有一个虚拟机栈来存储栈帧（每次方法调用都会创建一个栈帧，方法结束后栈帧就会被销毁），每个栈帧都有自己的结构（局部变量表（Local Variable）、操作数栈（Operand Stack）等等）.

我将上述字节码指令做了一个注释，他的大概流程是这样的，首先我们第一次触发dfs方法的时候，虚拟机栈上创建了第一个dfs的栈帧:

此时的 x = 3 != 0，所以字节码指令跳转去了第6行，然后getfield #2 strangetest1.cnt 获取了类的实例域并将其压入栈顶（即获取此时cnt的值），此时的虚拟机栈结构大致如下：

然后字节码指令相继执行了

iload_1：将存放在本地变量表中下标为1的变量x推送到操作数栈顶压入

iconst_1：加载常数1到栈顶

isub：将栈顶的两个元素出栈，相减，将结果压入栈顶（即将x-1结果入栈，x与1都出栈）

如图所示：

然后继续执行invokespecial #3 strangetest1.dfs，此时递归的调用dfs方法，即又创建了新的dfs的栈帧（注意此时传入的是当前栈帧栈顶的元素，即新创建的栈帧传入的x为2）：

当然dfs(2)后续的执行步骤也和dfs(3)差不多，需要注意的是dfs(2)在getfield #2 strangetest1.cnt 获取cnt的值时也是获取的当前值0，此他时结构大致和dfs(3)的差不多：

然后就是套娃般的执行…

直到最后一个递归dfs(0)的执行,因为此时 x = 0,所以执行iconst_1、ireturn . 即dfs(0)销毁后ireturn返回了一个1给dfs(1)的栈帧并压入dfs(1)的操作数栈顶：

dfs(1)获取到invokespecial dfs(0)返回的值之后，继续执行第18行的指令 iadd，把之前dfs(0) return的值（此时的操作数栈顶元素1）与它下面的元素（即触发invokespecial dfs(0)递归调用之前存的cnt的值）出栈相加，结果入栈:

继续执行第19行指令putfield #2 strangetest1.cnt，为指定类实例域cnt赋值，即将相加的结果栈顶元素1赋给cnt，此时的cnt确实是正确的数值，也对应了我们之前debug时倒数第二次递归即dfs(x = 1)的时候看到的情形. 继续执行iconst_0、ireturn 将0 ireturn到之前的dfs栈帧，然后dfs(x = 1)栈帧销毁.

如果我们继续往下走逻辑，就会发现问题所在，我们在dfs(x = 2)中getfield获取cnt的值并压入操作数栈的操作是在我们 invokespecial 触发递归dfs(x = 1)之前，所以我们在dfs(x = 2)中存入的cnt的值是一个错误时效性的值，即我们此时存在操作数栈中cnt的值是之前的0而不是此时cnt正确的值1 . 如果我们在获取到dfs(x = 1)return的值之后，继续执行第18行的 iadd 指令：

继续执行第19行指令putfield #2 strangetest1.cnt，为指定类实例域cnt赋值0，好家伙，我们cnt之前正确的值1此刻就被变成了错误的值0 . 罪魁祸首找到了，看来这的确是一个编译期造成的问题 .

那么我们去查看下拆分后int t = dfs(x - 1); cnt += t; 这种写法的字节码指令：

 0 iload_1                //将存放在本地变量表中下标为1的变量推送到操作数栈顶（即推送x）
 1 ifne 6 (+5)            //当操作数栈栈顶元素不等于0时 跳转到第6行
 4 iconst_1               //不跳转时的逻辑（即栈顶元素为0）加载常数1到栈顶
 5 ireturn                //返回栈顶元素（4，5行加起来即return 1）  此栈帧结束
 6 aload_0                //x！=0时的逻辑  此时压入栈顶的是this（无需关心此步骤）
 7 iload_1                //将存放在本地变量表中下标为1的变量推送到操作数栈顶（即推送x）
 8 iconst_1               //加载常数1到栈顶
 9 isub                   //将栈顶的两个元素出栈，相减，将结果压入栈顶（即将x-1结果入栈，x与1都出栈）
10 invokespecial #3 <StrangeTest.dfs>     //递归的调用dfs方法（将栈顶的元素，即上一步的x-1传入，存入新的dfs的栈帧的局部变量表下标1的位置，因为下标0要存this）
13 istore_2               //将上一步递归中dfs栈帧ireturn的值存入本栈帧的局部变量表下标为2的位置
14 aload_0                //压this 忽略此步骤
15 dup                    //复制this，忽略此步骤
16 getfield #2 <StrangeTest.cnt>     //获取类的实例域并将其压入栈顶（即获取cnt）
19 iload_2                //将局部变量表下标为2的变量压入栈顶
20 iadd                   //将栈顶的两个元素出栈，相加，将结果压入栈顶
21 putfield #2 <StrangeTest.cnt>     //为指定类实例域赋值  （即将相加的结果赋给cnt）
24 iconst_0               //加载常数0到栈顶
25 ireturn                //返回栈顶元素 （即return 0）

为啥这种写法没有问题呢？很明显的，最核心的问题在于字节码指令的顺序，即invokespecial #3 strangetest1.dfs 与 getfield #2 strangetest1.cnt、putfield #2 strangetest1.cnt 的调用顺序上，当使用一个局部变量int t = dfs(x - 1);时，此时先触发了invokespecial，后续的 cnt += t；才触发了getfield与putfield操作cnt的行为，此时getfield取到的是正确时效性的、当前的cnt的值，所以最后的结果是没有错误的 .

原因探究

上面我们分析了两种写法的字节码指令，与他们为什么呈现出一个错误与一个正确的结果 . 但是我还是不禁陷入思考，这只是表面原因，那么到底是什么根本原因或者说原则导致了invokespecial #3 strangetest1.dfs与getfield #2 strangetest1.cnt、putfield #2 strangetest1.cnt触发循序的不同呢？

我吭哧吭哧去翻阅了JLS（Java Language Specification 即Java的语言规范），在15.26.2. Compound Assignment Operators （复合赋值操作符）中，我发现了如下规定：

A compound assignment expression of the form E1 op= E2 is equivalent to E1 = (T) ((E1) op (E2)), where T is the type of E1, except that E1 is evaluated only once.

At run time, the expression is evaluated in one of two ways.

If the left-hand operand expression is not an array access expression, then:

First, the left-hand operand is evaluated to produce a variable. If this evaluation completes abruptly, then the assignment expression completes abruptly for the same reason; the right-hand operand is not evaluated and no assignment occurs.

Otherwise, the value of the left-hand operand is saved and then the right-hand operand is evaluated. If this evaluation completes abruptly, then the assignment expression completes abruptly for the same reason and no assignment occurs.

Otherwise, the saved value of the left-hand variable and the value of the right-hand operand are used to perform the binary operation indicated by the compound assignment operator. If this operation completes abruptly, then the assignment expression completes abruptly for the same reason and no assignment occurs.

Otherwise, the result of the binary operation is converted to the type of the left-hand variable, subjected to value set conversion (§5.1.13) to the appropriate standard value set (not an extended-exponent value set), and the result of the conversion is stored into the variable.

Java对于复合赋值操作符是这么规定的，在进行E1 op = E2的复合赋值操作时，等价于 E1 = (T) ((E1) op (E2)) ,用+=举例就是：a += b 等价于 a = a + b.

整个表达式的计算要遵循以下逻辑（非数组时），简单的说，就是我们要先对左操作数E1进行一个计算，产生一个变量，然后保存这个值；然后才能对右操作数E2进行计算.

看一个简单的实例，在java中，如果运行int k = 1; k += (k = 4) * (k + 2);,那么顺序是这样的，k = k + (k = 4) * (k + 2)，先计算E1（即k）的值，然后保存该值，再计算E2（即(k = 4) * (k + 2)）的值，所以最后 k = 1 + 4 * 6 = 25 ; 这与C/C++的计算顺序逻辑是完全不同的，C是按照运算符的运算顺序来进行计算，所以在C中先算乘法,即最后是 k = 4 + 4 * 6 = 28 .

So,正是因为JLS中这种规定，所以在我们使用cnt += dfs(x- 1);时，编译器才会先去getfield去获取E1（即cnt）的值，然后把它保存在操作数栈中，然后才对右操作数E2（即dfs(x- 1)）进行计算，才触发了invokespecial等后续操作，这就造成了我们之前提到的表因(三条指令触发的顺序不对)。