递归函数的调用深度理解

学过函数后基本上不久就会接触到递归，对于刚接触递归或者没有很深入理解递归的时候对递归的调用是模糊的，是含混不清且自以为已经懂了的，但是遇到自己需要用到递归或者看到别人的递归的时候理解起来可能就没有那么轻松了，所有深度理解递归还是很有必要的。

要理解递归函数根本在于要理解递归函数的调用，画图有助于我们理解，以二叉树的中序遍历为例，我们来画图理解这个递归的调用顺序：

先看看下面这个中序遍历的代码：

void inorder(){

       recr(root);

}

Void recr(Node r){

       If(r == null)

              Return;

       Recr(r.left);

       System.out.println(r.key);

       Recr(r.right);

}

上面的函数省略了节点类和树类的部分，节点还是和普通的二叉树一样有key，和right,left节点，树类里有根节点和节点类；

不难看出首先我们会从根节点开始将recr（10）压入堆栈，接着是recr（10.left==8），recr(8.left==5),直到recr(5.left==null)我们不会有函数压入堆栈，因此到此执行println（5）；

然后recr(5.right)会调用一下，因为也是空，所以不会入栈，因此pop完5的部分，再继续pop函数栈里的8的部分，先看8的left已经pop了，再打印8，再打印8.right==9,以此类推，这是很简单的函数递归的调用，但是有时候理解起来也确实费劲，画图是个好办法。