问题要从一本书 Principles of computer organization and Assembly language : using the Java virtual machine
（by Juola, Patrick）说起，这本书用非常简介的语言通过Java虚拟机对汇编语言进行了简要介绍，除了涉及普通命令之外，作者还介绍了if选择结构和while、for循环结构。循环结构的汇编语言表达是在subroutine结尾加入是否要进行循环的判断以及在需要循环的情况下的goto让命令回到subroutine开头。
于是我对recursion（递归）的底层——汇编语言的表达产生了兴趣，但由于精力和相关储备知识有限和对汇编语言的关注限于一些基本问题，这个问题一时不太清楚，转而询问了Udemy上Java课程的Andrew老师，得到的答复是：递归本质上是对方法体本身的调用，体现在程序里是对应用程序的压栈（push），压栈的对象是该方法本身。
根据我的了解，在汇编语言级别，封装的方法形如一个object（对象）也不是每一次递归都全部执行，因为方法的出口是唯一的，但实际情况到底如何呢？以下为探究的尝试。
根据Streib第8章Binary Tree的BinarySearchTree和它的主程序，创建一个二叉树并插入一些数据节，然后删除个别数据节。主类和主程序都比较长，完整的代码作为附件供参考。
首先关注的是insert（）和remove（）方法，它们在主类中而不是主程序中被调用，这里涉及一个每次插入或移除后root的变化
public void insertBST(int num){
root=insert(num,root);
}
public void removeBST(int num){
root = remove(num,root);
}
我一度不理解为什么每次都要调整root，后来根据代码本身理解到对于insert（）是解决空的树的第一个node（也是root），而对于remove（）则是考虑到删除的node是root的情况。我试图通过（一级调用的）method运行返回值来佐证，对这个问题的探索直接引发了后面对method递归过程的分析。
上代码：
private Node insert(int num, Node p){
if (p==null)
p=new Node(num);
else{
if (num<p.data)
p.left=insert(num,p.left);
else
if (num>p.data)
p.right=insert(num, p.right);
else
System.out.println("Item in the tree and not inserted");}
System.out.println("Returned value "+p.data);//**加入的中间输出
return p;
}
以及
private Node remove(int num,Node p){
if (p!=null)//start locating the node in non-empty tree
if (num<p.data)
p.left=remove(num,p.left);
else
if (num>p.data)
p.right=remove(num,p.right);
else//case 1: node found at terminal location
if (p.left==null&&p.right==null)
p=null;
else//case 2&3: node found at non-terminal location
but only one subnode exists hereafter.
if (p.left==null)
p=p.right;
else
if (p.right==null)
p=p.left;
else {//case 4: two sub-nodes (with possibly further sub-nodes) underneath
and the smallest number of right sub-node (including all sub-nodes) replaces the node to be removed
Node t=findMin(p.right);
p.data=t.data;
p.right=remove(p.data,p.right);
}
else{//case 5: empty or item not found
System.out.println("Item not in tree and not removed");}
//intermediate output
if(p!=null)
System.out.println("Returned value2 "+p.data);
else
System.out.println("Returned value2 null");//**
return p;
}
二级调用的findMin
private Node findMin(Node p){
if (p!=null){
while (p.left!=null)
p=p.left;}
System.out.println("Returned value3 "+p.data);//**
return p;
}
在试验过程中，insert的中间输出没有问题，而remove发生了NullPointerException，为了全面了解中间过程以及区分insert、remove和remove调用（主程序中二级调用的）findMin（），我把他们的输出加以区分成value、value2和value3
没有中间输出过程的运行结果是这样的
Enter a positive integer to insert or a negative integer to stop: 5
The tree is: 5
Enter a positive integer to insert or a negative integer to stop: 4
The tree is: 4 5
Enter a positive integer to insert or a negative integer to stop: 8
The tree is: 4 5 8
Enter a positive integer to insert or a negative integer to stop: 6
The tree is: 4 5 6 8
Enter a positive integer to insert or a negative integer to stop: 9
The tree is: 4 5 6 8 9
Enter a positive integer to insert or a negative integer to stop: -1
Enter a positive integer to remove or a negative integer to quit: 6
The tree is: 4 5 8 9
Enter a positive integer to remove or a negative integer to quit: -1
End of Program
在返回命令之前加上输出返回值（类型Node）的所包含的数据之后，「注意不能加在返回后面因为这样的话方法运行已随着返回值的返回而结束，该命令无法执行」输出结果中包含了insertBST(int num)和removeBST调用 insert(int num, Node p)和 remove(int num, Node p)的过程：
------------------------------------------------
Enter a positive integer to insert or a negative integer to stop: 5
Returned value 5
The tree is: 5
Enter a positive integer to insert or a negative integer to stop: 4
Returned value 4
Returned value 5
The tree is: 4 5
Enter a positive integer to insert or a negative integer to stop: 8
Returned value 8
Returned value 5
The tree is: 4 5 8
Enter a positive integer to insert or a negative integer to stop: 6
Returned value 6
Returned value 8
Returned value 5
The tree is: 4 5 6 8
Enter a positive integer to insert or a negative integer to stop: 9
Returned value 9
Returned value 8
Returned value 5
The tree is: 4 5 6 8 9
Enter a positive integer to insert or a negative integer to stop: -1
Enter a positive integer to remove or a negative integer to quit: 6
Returned value2 null
Returned value2 8
Returned value2 5
The tree is: 4 5 8 9
Enter a positive integer to remove or a negative integer to quit: 9
Returned value2 null
Returned value2 8
Returned value2 5
The tree is: 4 5 8
Enter a positive integer to remove or a negative integer to quit: 5
Returned value3 8
Returned value2 null
Returned value2 8
The tree is: 4 8
Enter a positive integer to remove or a negative integer to quit: -1
End of Program
Process finished with exit code 0
（生成和改变过程中的二叉树由于时间和技术水平有限我就不画了，请看到的朋友自行想象并画图。）
先看插入。这里可以看到：Returned value后面的p的值在插入期间全部是按照首先插入项自己然后依次回到root的顺序输出的，正好是插入过程根据每个node数值大小进行搜索过程的逆过程。说明形成了一个栈（stack）！
有趣的是每一次递归都返回了一个（Node） p，这非常揭示递归的过程：在“ if (num<p.data) p.left=insert(num,p.left); ”这里，参数p.left视为方法签名中 insert(int num, Node p)的“Node p”，所以加入输出p命令后每一次递归都输出运行中途的“p”。
而方法递归的内部过程由此也得到显示：System.out.println("Returned value "+p.data)由于之前的参数递归部分本身无法运行，只有等到第一轮递归结束（p的最终位置确定，一个新的node创建），挤压依旧的println命令倒着依据方法体的压栈依次出栈（pop）。
再看删除。删除6和9时，删除位置都是终端节点，不涉及任何subroot的更改，程序按照返回root的顺序以此输出中间数值。然而，第一次输出的p数值都是null，之后的8和5是返回root的次序。
remove过程中首先输出的null（对应最后一次递归），因为null的产生是node移除导致的，而移除根据前面代码发生在递归的最后一次，即程序发现了要移除项的位置并移除了该node。所以接下来println（）无法输出已经移除的p值了。
再后面移除5——tree的root时候，首先输出的是value3的值8,也就是findMin在非终端节点的右边查找最小值，随后value2（来自remove）输出的null和8引起了我的注意，因为这似乎和递归过程不符：我们倒着看，要移除5而5正好是root，第一个p值（最后输出）应该是5而不是8；然后由于5的下面有两个node，findMin在右侧查找最小值，findMin的参数是数值为8的节点，而程序则输出null；最后一个递归是p.right=remove(p.data,p.right)，p值对应当时的p.right是8,但8已经从原来位置移除转移到root上，此时应该输出null。
null「value2」、8「value3」、5「value2」变成了8「value3」、null「value2」、8「value2」 。
此时打开Flow，记录的运行过程与描述的一样，顺序是remove、findMin和remove。
如何导致程序中间过程的输出顺序发生颠倒暂时不清楚，但两次remove中间值为8和null却给我一个线索：8是删除5后新的root，remove的参数正好一次是root一次是后来被删除的原来8的位置。也就是说，很可能返回中间值的操作全部基于所有递归结束后的内存状态。
换句话说，我猜测Java虚拟机不储存递归结束前的中间内存状态。
为了验证这个猜测，我进行了一个复杂一些的实验，这次不先删除任何终端节点，直接删除一个root下的subroot。
复杂一些的删除案例如下：
------------------------------------------------
Enter a positive integer to insert or a negative integer to stop: 5
Returned value 5
The tree is: 5
Enter a positive integer to insert or a negative integer to stop: 3
Returned value 3
Returned value 5
The tree is: 3 5
Enter a positive integer to insert or a negative integer to stop: 2
Returned value 2
Returned value 3
Returned value 5
The tree is: 2 3 5
Enter a positive integer to insert or a negative integer to stop: 7
Returned value 7
Returned value 5
The tree is: 2 3 5 7
Enter a positive integer to insert or a negative integer to stop: 6
Returned value 6
Returned value 7
Returned value 5
The tree is: 2 3 5 6 7
Enter a positive integer to insert or a negative integer to stop: 9
Returned value 9
Returned value 7
Returned value 5
The tree is: 2 3 5 6 7 9
Enter a positive integer to insert or a negative integer to stop: -1
Enter a positive integer to remove or a negative integer to quit: 7
Returned value3 9
Returned value2 null
Returned value2 9
Returned value2 5
The tree is: 2 3 5 6 9
Enter a positive integer to remove or a negative integer to quit: -1
End of Program
----------------------
Process finished with exit code 0
依次插入5、3、2、7、6、9，根往下第一级的二叉树的右半枝的根是7，再往下左边6右边9。这里要删除7。中间值输出了两次9一次5一次null。倒着看：5是第一次递归的p即root，第二次递归p是7输出却是9, 然后根据Flow第三次调用findMIn「见图」，就算顺序跟随之而来的remove掉过来，也应该是6而不是9，9是待删除节点7右侧的最大值而不是最小值；value2是null可以理解成已经被删除的node（6）。
（鼠标位置是remove下面两个无文字小方柱的左侧那个）
所以两次9是什么？第二次递归的命令是“ p.right=remove(num,p.right);”这里括号里参数p.right在u运行过程中是7,递归结束后是6,于是我产生了新的猜想： 输出中间p虽然程序把p.right视为“p”，但依据变量字面名称输出人p的right。「此处涉及参数的lexical scope<词法作用域>问题，应有确定答案」
而9如果p.right对应的p正好是6——递归结束后的内存状态，6在5的右下侧，这样在允许value3和value2调换顺序情况下，迭代结束后程序根据当时内存状态索引p，最后一次（第三次）递归经历了p的两次right，5变成了9；第一次迭代的是5没有变化，第二次迭代的p变成了6但p.right是9，在终端节点9进行findMin得到的也是9。然而remove返回的value2是null，此时null一个是原来6的位置一个是9的左边或右边，根据刚才的猜想p.right是null的只能是9，也就是说明9从刚才的p.right被重新当成p了。
问题没有得到解决。
总结一下未解决的问题是：
1 方法递归过程中加入的中间输出值是否全部返回到调用它的方法/主程序中？是主程序接受最后一次返回的内容还是Java虚拟机对这个过程中进行控制只返回最后一次？
2 Private Node remove(int num,Node p)方法体中的 p.right=remove(int num,Node p.right) 的参数p.right是作为方法签名里的“p”还是另一个变量？
3 Java虚拟机是否储存递归结束前的中间内存状态？
完整代码：
https://paste.ee/p/dzxjx