递归与栈
之前很多算法都是用递归解决的,也知道递归的是对栈的调用,但是并没有仔细的了解具体是怎么工作的,乘着上一篇文章也用了递归,就根据上一篇文章中的 算法,详细的看看栈中是怎么变化的,因为是自己画图,有不严谨的地方,请联系我,感谢!
函数调用,栈中要做什么?
函数调用是指一个函数在函数体内调用另一个函数,那么这个过程中,会做些什么呢?
(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,#,#
至此递归结束!