详解递归时栈的调用

Posted by DH on August 1, 2017

递归与栈

之前很多算法都是用递归解决的,也知道递归的是对栈的调用,但是并没有仔细的了解具体是怎么工作的,乘着上一篇文章也用了递归,就根据上一篇文章中的 算法,详细的看看栈中是怎么变化的,因为是自己画图,有不严谨的地方,请联系我,感谢!

函数调用,栈中要做什么?

函数调用是指一个函数在函数体内调用另一个函数,那么这个过程中,会做些什么呢?

(1)运行时系统,将调用者的所有实参和返回地址压栈,这个过程中最后入栈的是调用者的返回地址;

(2)为被调用者分配空间,也就是将被调用者压栈;

(3)将控制权给被调用者;

接着,被调用的函数执行,出栈之前会做三件事:

(1)保存被调函数的计算结果;

(2)释放被调函数的数据区;

(3)依照被调函数保存的地址将控制权转移给调用函数。

递归调用

知道了函数调用的方式,那么递归就是函数自己调用自己,道理是一样的。 下面,举例说明:

举例说明

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    int index = -1;
	// 前序遍历
	String Serialize(TreeNode root) {
        StringBuffer buffer = new StringBuffer();
		if (root == null) {
			buffer.append("#,");
			return buffer.toString();
		}
		buffer.append(root.val +",");
		// 递归的前序遍历
		buffer.append(Serialize(root.left));
		buffer.append(Serialize(root.right));
		
		return buffer.toString();
	  }
	
}		

函数String Serialize(TreeNode root)是一个递归调用的函数。我们开看看栈中的变化:

我们一步步分析: 从第一步到第三步不涉及到出栈操作,很容易理解。

当执行到第三步时,这时候不会再有函数进行压栈,就要进行出栈了:

第一次弹出栈顶:

接着,会继续调用函数:

这个时候,叶子节点4的两个空的孩子节点都调用完毕了。就要弹出叶子节点4了。如下图所示:

接着继续调用buffer.append(Serialize(null);进行压栈:

然后出栈,已经来到根节点:

这个时候buffer.append(Serialize(2));已经递归完毕,接着调用函数buffer.append(Serialize(3));

接着继续调用buffer.append(Serialize(5);紧接着调用buffer.append(Serialize(null);如下图所示:

这个时候就要开始出栈了,出站后会继续调用buffer.append(Serialize(null):

接下来,进行出栈,节点5的递归完毕:

开始调用节点6的递归:

接上一步:

开始一步步全部弹出:

最终返回结果:1,2,4 ,#,#,# ,3,5,#,#,6,#,#

至此递归结束!