读《一个递归引发的思考》有感
——“码小农”第一期
首先，我想向阿里的凡提前辈表达诚挚的谢意，感谢前辈在百忙之中参与高校联盟的“码小农”活动，同时感谢集团技术发展部的高阳姐，多谢您从中沟通协调，保证本次活动顺利完成。以下涉及到凡提前辈本人的博文原文或解答等时，文字将被标记为蓝色，特此说明。
l 博文剖析
博文开始描述了凡提前辈遇到的一个需求：将某个路径作为参数传递给工具，然后工具可以遍历该目录下的所有子目录和文件，将所有数据文件进行解析转换。读到这里时，我脑海中第一个浮现出来的便是递归算法，用递归实现深度搜索，遍历整个目录。凡提前辈也是这样想的：做一个递归函数，遇到文件时处理文件，遇到目录时则进行递归，这样很快就可以把某个路径下的所有子目录和文件都遍历一遍，程序也会显得简洁明了。代码一般如下：
|
private void recursion (Path path) { FileStatus[] children = fs.listStatus (path); for(FileStatus child : children){ if(child.isDir()){ recursion(child.getPath()); } else{ …… //执行文件处理代码 } } } |
以上程序段在自测阶段没有出现问题，但是实际放到服务器上去运行的时候，产生了栈溢出错误，即工具抛出了StackOverflowError异常。凡提前辈很快找出了原因：实际运行的服务器文件系统的目录层次太深了，因此每一层递归累积起来终于将jvm的栈空间撑爆了。自测阶段之所以没有暴露出问题，完全是因为该服务器目录文件树在一个小集群中很难模拟。随之凡提前辈给出了解决办法：将递归算法替换成迭代算法就可以了。修改后的代码如下：
Stack<FileStatus>pathstack = new Stack<FileStatus>();
for(pathstack.push(fs.getFileStatus(path)); !pathstack.empty();){
FileStatus cur = pathstack.pop();
FileStatus[] children = fs.listStatus(cur.getPath());
for(inti = 0; i<children.length; i++) {
finalFileStatus child = children[i];
if (child.isDir()) {
pathstack.push(child);
}
else {
…… //执行文件处理代码
}
}
}
由于之前一直使用递归方法解决文件目录遍历问题，乍一看这迭代方法一时摸不着头脑，故配一张自己画的流程图解释一二：
凡提前辈成功解决这一问题后，又对JVM堆栈方面的技术做了重新的审视与探究：
众所周知，堆是有序完全二叉树，栈是一种先进后出的线性表，栈的特点是速度快，jvm的压栈和出栈操作都是非常高效的（相对来说，堆的二叉树遍历是要比先进后出线性表要慢的）。
“每一个Java应用都唯一对应一个JVM实例，每一个实例唯一对应一个堆。应用程序在运行中所创建的所有类实例或数组都放在这个堆中,并由应用所有的线程共享.跟C/C++不同，Java中分配堆内存是自动初始化的。Java中所有对象的存储空间都是在堆中分配的，但是这个对象的引用却是在栈中分配,也就是说在建立一个对象时从两个地方都分配内存，在堆中分配的内存实际建立这个对象，而在堆栈中分配的内存只是一个指向这个堆对象的指针(引用)而已。”
“JVM堆中存的是对象。JVM栈中存的是基本数据类型和JVM堆中对象的引用。一个对象的大小是不可估计的，或者说是可以动态变化的，但是在JVM栈中，一个对象只对应了一个4btye的引用。”
关于这一点，我制作了下面这段程序来进行证实：
|
public class StackLevel { privateint level = 1; public void stackLevel(){ level++; stackLevel(); } public static void main(String[]args) throws Throwable{ StackLevelsl = new StackLevel(); try{ sl.stackLevel(); }catch(StackOverflowError e){ System.out.println(sl.level); } } } |
这段代码执行下来，可以看到默认情况下递归深度是10827（java version "1.6.0_65"，系统不同值略有不同）。在stackLevel函数中，增加一个变量（String
buf = “”;）之后，再执行一遍，得到的深度为9925。随意的给字符串buf赋值，无论字符串长度是多少，9925这个深度都不会发生变化。而如果再增加一个变量申明，则递归深度又会再次变小。从而证明了栈只存放指针，而堆负责存储这件事情。
对于我们一般的本地化应用来说，遍历目录这样的简单任务，用递归还是最高效的，这不仅是因为算法设计上较为清晰简单，更因为递归利用了栈的高效，程序整体运行速度会比较快。但是如果遍历目录的层次深度可能会多达数十甚至数百层的文件系统，使用递归必然会使得函数空间层层堆叠直到导致栈溢出，这也是为什么DistCP中使用了Stack类来规避递归的原因（而我最开始看到这一段的时候只是觉得这样的算法费事不讨巧，完全没有理解其深层次的原因）。
最后，凡提前辈画龙点睛，道出了递归方法在特定环境下使用需审慎：类似大数据项目的测试中，每一个递归都应该仔细考量其规模，因为大数据的文件系统往往在深度、广度上都不是普通文件系统可以比拟的，单机上不会出现的问题，到了大数据上都有可能成为问题。再进一步，有了这次的这个经验，更提醒我在将来的coding中，使用递归前也要预估一下可能带来的后果，防止类似的bug重现。
l 互动交流
由于本人才疏学浅，通读博文后仍有些问题没能搞懂，后来通过邮件与凡提前辈沟通，得以解惑。以下是我的提问和前辈的回答：
¡ 提问：
1、递归的本质是否就是迭代，即入栈与出栈？如果递归的本质是入栈与出栈，那么为何迭代不会导致栈溢出？
2、迭代方法如果一直入栈是否会导致栈溢出？Stack类为何能有效防止栈溢出呢？
¡ 解答：
递归是通过一个函数进行的，函数使用了栈空间存放在函数中申明的基本数据类型（例如int，char）和堆中对象的引用（注意是引用，而非对象本身）。所以递归由于不断调用自身函数体，因此会导致需要使用的栈空间不断增加，最终导致栈溢出。
而迭代是在一个函数中的循环体，迭代使用的pathstack这个变量，在JVM栈中只有一个4字节的指针（引用的本质），而变量的主体本身使用的则是堆内存空间。
堆空间相对于栈空间来说要大得多，但是如果无限制的使用堆空间，当然也会溢出，这就是java程序员都经常会遇到的OOM（OutOfMemoryError）异常。OOM异常是非常常见的堆溢出，而StackOverFlow这个栈溢出异常则非常少见，如文章所言，栈中只存放一些4字节的指针，所以虽然栈空间很小，但想撑爆栈空间也不是那么容易的事情，这就是为什么本地应用很难遇到栈溢出的原因。
出现堆溢出的时候，我们也可以通过java的启动参数，例如-Xmx来调整堆空间的大小，避免OOM。
所以对于你的两个问题，问题1的答案是这样：递归就是在过程或函数里面调用自身，而迭代是利用变量的原值推算出变量的一个新值。如果递归是自己调用自己的话，迭代就是A不停的调用B。显然递归用了栈空间，迭代因为始终在一个函数体中，所以使用的是堆空间。迭代只会导致堆溢出（OOM）而不会导致栈溢出。
问题2的回答是：迭代不会使用栈空间，所以当然不会导致栈溢出。Stack类的实例变量因为使用的内存空间是处于堆空间中，因此当然可以避免栈溢出。
如果在阅读的过程有其他疑问，请加入“阿里高校技术联盟”的【来往-扎堆】（二维码在下面给出），在其中可以找到文章作者与其互动交流。
l 结束语
通过这次对《一个递归引发的思考》的学习，我了解到了深度搜索除了用递归方法实现，还可以用迭代方法，两者机制不同故各有利弊：递归方法简洁易懂、运行速度快，但对栈空间的需求量大；迭代方法虽然比递归难懂且运行较慢，但其只占用很少的栈空间，有效避免了栈溢出的bug。同时了解了JVM堆栈使用机制，以及清楚了递归耗费栈空间的真正原因，总的来讲此次收获颇丰，再次感谢凡提前辈和高阳姐，希望“码小农”活动越办越好！