物有本末，事有始终，知所先后，则近道矣。-----题记。
今天小编跟大家探讨的是递归，递归的基本意思是不断调用自己实现逻辑，可减少代码量。它远看像一个穿短裙的美人，然而不管多看几眼，如若没有相关经验，恐怕这种美也只看到了十分之三。
我们从jvm，在字节码层面看看递归是到底是怎么回事，把那十分之七的灵魂之美补上，以后的江湖路上，可赏他人不知矣！
先看一段二叉树的insert方法的代码（二叉树有很多种，下面举的例子是一棵左节点<根节点<右节点的树）：
@SuppressWarnings("unchecked")
public BinaryTreeNode<Integer> insert(BinaryTreeNode<Integer> node,Integer data){
//如果当前节点的权值大于data，那么插入到左孩子节点上
if((int)node.data.toString()>data){
node.left=insert(node.left,data);
}
//如果当前节点的权值大于data，那么插入到左孩子节点上
if((int)node.data.toString()<data){
node.right=insert(node.right,data);
}
return node;
}
}
insert方法中涉及到递归，下面我们仔细研究一下哈：
0: aload_1
1: ifnonnull 13
4: new #1 // class tree/BinaryTreeNode
7: dup
8: aload_2
9: invokespecial #45 // Method "<init>":(Ljava/lang/Object;)V
12: areturn
13: aload_1
14: getfield #20 // Field data:Ljava/lang/Object;
23: aload_2
30: if_icmple 79
36: getfield #24 // Field left:Ltree/BinaryTreeNode;
39: aload_2
40: invokevirtual #53 // Method insert:(Ltree/BinaryTreeNode;Ljava/lang/Object;)Ltree/BinaryTreeNode;
43: putfield #24 // Field left:Ltree/BinaryTreeNode;
79: aload_1
80: areturn
上面是insert方法的jvm执行的指令，我摘抄了部分关键点说明一下递归是怎么做的：
insert函数栈中的局部变量表中的参数：第一个是当前树节点对象（暂且称为ref0），第二个是函数中传进来的node对象的引用（称为ref1），第三个是传进来的常量data（在常量池中#20）
0: aload_1 将第一个引用类型局部变量推送至栈顶，那个引用也就是insert方法中的node对象的引用（ref1）
1 : ifnonnull 13 如果ref1不为空，则跳到13行执行
4-12 : 如果是空，则此节点即是我们要插入的节点，调用它的构造函数<init>方法，将data值赋给它，然后areturn（将这个新生成的对象引用返回）
13 : aload_1 将ref1压入栈顶
14：getfield 将常量池中当前对象ref1的data的值压入栈顶
23：aload_2 将传入的data值压入栈顶
30：if_icmple 79，如果传入的data值小于ref1的权值，那么就跳到79执行
36：getfield #24 ，将常量池中#24，left压入栈中，即left常量的引用
39：aload_2 将data值压入栈中。实际上36、39两步的指令都是在为下面40行做准备，40行调用insert方法，传递给它需要的参数
40：invokevirtrual #53，调用insert方法，将36、39行准备的两个参数带过去
43：putfield #24 ，给当前实例ref1的left字段赋值
79：aload_1 ，将当前实例ref1压入栈中
80：areturn ，将栈顶的ref1返回
如果不太懂，我画了两张图，帮助理解：
image.png
假设找到了为空的左节点，new了一个D节点，并逐层返回：
image.png
栈帧3：B节点不具有左节点，new一个新的节点对象D，赋值data， 此时左子树的递归就结束了，字节码指令跳回到栈帧2的第43行， 执行putfield指令，也就是将栈帧3返回的节点对象D赋值给B节点的left属性。
栈帧继续返回对象引用，不断构建节点之间的关系，大家一定要能脑补出这段画面哦。
光说不练假把式，下面是小编自己写的二叉树及相关类，好好品味递归是怎么实现的吧：
一、二叉树类：
package tree;
/**
* 二叉树数据载体类
* @author tery
* @param <T>
*/
public class BinaryTreeNode<T> {
private T data;
private BinaryTreeNode<T> left;
private BinaryTreeNode<T> right;
public BinaryTreeNode(T data){
this.data=data;
left=right=null;
}
public T getData(){
return this.data;
}
public void setData(T data){
this.data=data;
}
public BinaryTreeNode<T> getLeft() {
return left;
}
public void setLeft(BinaryTreeNode<T> left) {
this.left = left;
}
public BinaryTreeNode<T> getRight() {
return right;
}
public void setRight(BinaryTreeNode<T> right) {
this.right = right;
}
/**
* 插入权值
* @param node
* @param data
* @return
*/
@SuppressWarnings("unchecked")
public BinaryTreeNode<T> insert(BinaryTreeNode<T> node,Integer data){
//如果当前节点的权值大于data，那么插入到左孩子节点上
if(Integer.valueOf(node.data.toString())>data){
node.left=insert(node.left,data);
}
//如果当前节点的权值大于data，那么插入到左孩子节点上
if(Integer.valueOf(node.data.toString())<data){
node.right=insert(node.right,data);
}
//相等抛异常
if(Integer.valueOf(node.data.toString())==data){
throw new IllegalArgumentException("the data:"+data+"is already exsist in the tree");
}
return node;
}
}
二、二叉排序树：
package tree;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* 二叉排序树（Binary Sort Tree）又称二叉查找树.它或者是一棵空树；或者是具有下列性质的二叉树：
* （1）若左子树不空,则左子树上所有结点的值均小于它的根结点的值；
* （2）若右子树不空,则右子树上所有结点的值均大于它的根结点的值；
* （3）左、右子树也分别为二叉排序树
*
* @author tery
*
* @param <T>
*/
public class BinarySearchTree<T extends Comparable> {
BinaryTreeNode<T> root;
public BinarySearchTree(BinaryTreeNode<T> root) {
this.root = root;
}
public BinaryTreeNode<T> getRoot() {
return this.root;
}
/**
* 最小值
* @return
*/
public T findMin() {
if (root == null) {
return null;
}
return findMin(root).getData();
}
private BinaryTreeNode<T> findMin(BinaryTreeNode<T> root) {
if (root == null) {
return null;
} else if (root.getLeft() == null) {
return root;
} else {
return findMin(root.getLeft());
}
}
/**
* 最大值
*
* @return
*/
public T findMax() {
if (root == null) {
return null;
}
return findMax(root).getData();
}
public BinaryTreeNode<T> findMax(BinaryTreeNode<T> root) {
if (root == null) {
return null;
} else if (root.getRight() == null) {
return root;
} else {
return findMax(root.getRight());
}
}
/*
* 获取高度
*/
public int height() {
return height(root);
}
private int height(BinaryTreeNode<T> node) {
if (node == null) {
return 0;
} else {
int leftHeight = height(node.getLeft());
int rightHeight = height(node.getRight());
if (leftHeight > rightHeight) {
return leftHeight + 1;
} else {
return rightHeight + 1;
}
}
}
/**
* 节点数
*
* @return
*/
public int size() {
return getSize(root);
}
private int getSize(BinaryTreeNode<T> node) {
if (node == null) {
return 0;
}
return getSize(node.getLeft()) + 1 + getSize(node.getRight());
}
/**
* 是否合法
*
* @return
*/
public boolean isValid() {
return isValid(root);
}
@SuppressWarnings("unchecked")
private boolean isValid(BinaryTreeNode<T> node) {
if (node == null) {
return true;
}
if (node.getLeft() != null && findMax(node.getLeft()).getData().compareTo(node.getData()) > 0) {
return false;
}
if (node.getRight() != null && findMin(node.getRight()).getData().compareTo(node.getData()) < 0) {
return false;
}
if (!isValid(node.getLeft()) || !isValid(node.getRight())) {
return false;
}
return true;
}
/**
* 删除节点数据
* @param t
*/
public void remove(T t) {
remove(t, root);
}
@SuppressWarnings("unchecked")
private BinaryTreeNode<T> remove(T t, BinaryTreeNode<T> node) {
if(node==null){
return node;
}
int result=t.compareTo(node.getData());
if(result>0){
remove(t,node.getRight());
}else if(result<0){
remove(t,node.getLeft());
}else{
if(node.getLeft()!=null && node.getRight()!=null){
node.setData(findMin(node.getRight()).getData());
//把右孩子做为根节点，执行删除逻辑后即可将值为t的元素删除
node.setRight(remove(node.getData(),node.getRight()));
}else{
//左右有一个为空，则直接赋值不为空的那个节点
node=node.getLeft()==null?node.getRight():node.getLeft();
}
}
return node;
}
/**
* 得到最小的那个公共祖先
*
* @param t1
* @param t2
* @return
*/
@SuppressWarnings("unchecked")
public T getLowestCommonAncestor(BinaryTreeNode<T> node,T t1, T t2) {
if(node==null){
return null;
}
//公共祖先在左孩子
if(t1.compareTo(node.getData())<0&&t2.compareTo(node.getData())<0){
//以左节点为根节点，一直找到右节点为空，函数栈中存留的那个节点即是要找的公共祖先。
//实际上下面这个语句在jvm编译后执行的是areturn(即返回一个reference类型数据）
return getLowestCommonAncestor(node.getLeft(), t1, t2);
//公共祖先在右孩子
}else if(t1.compareTo(node.getData())>0&&t2.compareTo(node.getData())>0){
//
return getLowestCommonAncestor(node.getRight(), t1, t2);
}else{
//当前节点的权值在t1和t2的之间，那当前节点即是公共祖先,拿到权值返回即可
return node.getData();
}
}
/**
* 返回所有满足下列条件的节点的值： n1 <= n <= n2 , n 为 该二叉查找树中的某一节点
*
* @param n1
* @param n2
* @return
*/
public List<T> getBetweenNode(T n1, T n2) {
List<T> elements=new ArrayList<>();
getBetweenNode(elements,root,n1,n2);
return elements;
}
@SuppressWarnings("unchecked")
public List<T> getBetweenNode(List<T> elements ,BinaryTreeNode<T> node,T n1, T n2){
if(node==null){
return null;
}
if(node.getData().compareTo(n1)>=0&&node.getData().compareTo(n2)<=0){
elements.add(node.getData());
}else if(node.getData().compareTo(n1)<0){
getBetweenNode(elements,node.getLeft(),n1,n2);
}else if(node.getData().compareTo(n2)>0){
getBetweenNode(elements,node.getRight(),n1,n2);
}
return elements;
}
/**
* 按层级遍历二叉树
*
* @return
*/
public List<T> getLevelList() {
List<T> result=new ArrayList<>();
if(root==null){
return result;
}
Queue<BinaryTreeNode<T>> queue=new LinkedList<>();
BinaryTreeNode<T> node=root;
queue.add(root);
while(!queue.isEmpty()){
result.add(node.getData());
queue.remove(node);
if(node.getLeft()!=null){
queue.add(node.getLeft());
}
if(node.getRight()!=null){
queue.add(node.getRight());
}
}
return result;
}
}
三、二叉树工具类：
image.png
1. 前根序遍历：先遍历根结点，然后遍历左子树，最后遍历右子树。（ABDHECFG）
2.中根序遍历：先遍历左子树，然后遍历根结点，最后遍历右子树。（HDBEAFCG）
3.后根序遍历：先遍历左子树，然后遍历右子树，最后遍历根节点（HDEBFGCA）
package tree;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class BinaryTreeUtil {
/**
* 用递归的方式实现二叉树的前序遍历
* @param root
* @return
*/
public static<T> List<T> preOrderVisit(BinaryTreeNode<T> root){
List<T> result=new ArrayList<>();
preOrderVisit(root,result);
return result;
}
private static<T> void preOrderVisit(BinaryTreeNode<T> node, List<T> result) {
//如果节点为空，返回
if(node==null){
return;
}
//不为空，则加入节点的值
result.add(node.getData());
//先递归左孩子
preOrderVisit(node.getLeft(),result);
//再递归右孩子
preOrderVisit(node.getRight(),result);
}
/**
* 用递归的方式实现二叉树的中序遍历
* @param root
* @return
*/
public static<T> List<T> inOrderVisit(BinaryTreeNode<T> root){
List<T> result=new ArrayList<T>();
inOrderVisit(root,result);
return result;
}
private static<T> void inOrderVisit(BinaryTreeNode<T> node, List<T> result) {
if(node==null){
return;
}
inOrderVisit(node.getLeft(),result);
result.add(node.getData());
inOrderVisit(node.getRight(),result);
}
/**
* 用递归的方式实现二叉树的后遍历
* @param root
* @return
*/
public static<T> List<T> postOrderVisit(BinaryTreeNode<T> root){
List<T> result=new ArrayList<T>();
postOrderVisit(root,result);
return result;
}
private static<T> void postOrderVisit(BinaryTreeNode<T> node, List<T> result) {
if(node==null){
return;
}
postOrderVisit(node.getLeft(),result);
postOrderVisit(node.getRight(),result);
result.add(node.getData());
}
/**
* 用非递归的方式实现前序遍历
* @param root
* @return
*/
public static<T> List<T> preOrderVisitWithoutRecursion(BinaryTreeNode<T> root){
List<T> result=new ArrayList<T>();
Stack<BinaryTreeNode<T>> stack=new Stack<>();
if(root!=null){
stack.push(root);
}
while(!stack.isEmpty()){
BinaryTreeNode<T> node=stack.pop();
result.add(node.getData());
if(node.getRight()!=null){
stack.push(node.getRight());
}
if(node.getLeft()!=null){
stack.push(node.getLeft());
}
}
return result;
}
/**
* 用非递归的方式实现中序遍历
* @param root
* @return
*/
public static<T> List<T> inOrderVisitWithoutRecursion(BinaryTreeNode<T> root){
List<T> result=new ArrayList<T>();
Stack<BinaryTreeNode<T>> stack=new Stack<>();
BinaryTreeNode<T> node=root;
while(node!=null || !stack.isEmpty()){
while(node!=null){
stack.push(node);
node=node.getLeft();
}
BinaryTreeNode<T> currentNode=stack.pop();
result.add(currentNode.getData());
node=currentNode.getRight();
}
return result;
}
public static void main(String[] args) {
BinaryTreeNode<Integer> tree=new BinaryTreeNode<Integer>(10);
tree.insert(tree,8);
tree.insert(tree,5);
tree.insert(tree,9);
}
}
关于递归，请各位再深入思考一下。里面涉及到了jvm函数调用层面的知识，如果不懂，建议大家去看看jvm的书，了解jvm怎么执行代码，那就可以轻轻松松地理解递归到底是怎么执行的了。
