之前的文章中有系统的讲过GC相关的理论知识，如果对GC相关的理论知识不太理解的朋友，可以阅读一下：漫谈GC —— GC基本理论和深度剖析
提到递归，很多人的第一反应就是著名的 StackOverflowException, 栈溢出错误, 能够理解递归调用的逻辑是操作系统上的一个压栈操作，通常情况下，栈的内存非常小，所以调用层次很深的话就会产生类似的错误。我做了一个小测试，看一下调用多少层之后，我的系统会报出栈溢出。
代码如下(C#实现):
public class TestClass
{
public void M1(int num)
{
if (num < int.MaxValue)
{
num++;
Console.WriteLine(num);
M1(num);
}
}
}
可以看到我设置的递归出口是int自增到int最大值的时候退出。
栈溢出统计
可以看到我的机器大概会在51520次的时候，栈溢出。由于方法里面几乎没有额外操作，所以这个数值比实际情况中大一些，而且计算机不同，结果肯定也不一样，日常的方法调用层数一般不会大于这个数值，所以常规的开发中，栈溢出基本上不会碰到。这里不是为了测试栈溢出的临界值的，所以只是简单理解一下栈溢出的异常就够了。
那这里提出一个问题，递归有没有可能内存溢出呢？
看下面这段测试代码(C#)：
public void M1(int num)
{
Console.WriteLine("倒数第：" + num); //输出
int[] arr = new int[100000]; //定义了一个长度为10W的数组
for (int i = 0; i < arr.Length; i++)
{
arr[i] = 100;
}
if (num > 0)
{
M1(num - 1);
}
}
public static void Main(string[] args)
{
temp.M1(50000);//由于我的电脑的栈溢出大概在50000以上，所以设置50000，看一下效果
}
上面的代码也不难理解，有几点提及一下：
- 我的电脑 的栈溢出在50000+，所以调用层数设置为50000，
- 每次递归的时候，定义了一个比较大的数组，长度为10W，每次赋值之后没有额外的任何操作。
我们看一下执行的结果：
内存溢出
可以看到，发生了
OutOfMemoryException内存溢出，而递归只进行了不到10000次。
C# & Java GC算法
这里不谈太多的理论上的内容，理论上的细节可以看我在开篇引言中提到的另一篇文章。
C#与Java中，GC采用的是GC Root 的链路可达性分析算法解决的GC标记问题。原理就是一个对象只要有GC Root引用，就不会释放，这个不难理解，那么什么对象会被定义为GC Root对象呢？
GC Root对象大概包括这几类（我在概念文章里也提及了）：
- 虚拟机栈对象（JVM，CLR等）
- OS 栈（操作系统本地方法的栈，Native）
- 方法区中的常量或者静态引用的对象等。
上面的例子就是由于方法压栈，产生的问题，每一个新生成的数组，都被压栈进去的方法所引用，进行GC的时候，都是可达对象，无法GC，所以不会被释放。
实际生产问题
这里描述一下当时的问题：
当时是有一个服务器的文件夹，里面存储了大量的mp3文件，递归的过程中，需要把他们统一取出来，放入一个数组，过程中使用了递归的方式遍历所有文件夹下的文件，生成了大量的临时字符串，而字符串本质上也是一个byte数组，长度很大的话，也是比较消耗内存的，递归过程中同样不被释放，而服务器的内存较小，只有2GB。本地测试的时候，机器是16G电脑，没有问题，但是到服务器上就崩溃了。
递归虽然是很优雅的编程方式，在诸多算法里面也是热点，但是同样不能忽视递归调用过程中的栈溢出，以及上文提及的内存溢出。
后记
Go语言的垃圾回收机制，没有使用链路可达性分析，而是三色标记法，细节可以看这里
这里还是贴一段代码：
package main
var count = 0
func main() {
arr := make([]int,10)
test(arr)
}
func test(arr []int ) []int {
if count == 20 {
return arr
}else{
count++
caps:= cap(arr)
for i:= 0;i< 2 * caps;i++{
arr = append(arr, i)
}
println(arr, cap(arr))
arr = test(arr)
}
return arr
}
上面的递归算法同样没有到20次，就抛出了内存溢出，请了解Go的小伙伴通过对三色标记法的理解，留言讨论一下吧。
网友评论