方法或者说函数的调用和返回使栈的大小增长或者收缩,而递归这种操作使得栈大小爆炸性增长,存在栈空间溢出的风险。在很多种编程语言中存在对尾递归这种特殊递归的优化机制,比如GCC编译器会把C语言中的尾递归优化成循环。而Java语言环境中无论在编译时还是在运行时都没有针对尾递归的优化,一个很简单的验证如下。
public static void main(String[] args) {
func(1);
}
public static int func(int i) {
return func(i + 1);
}
这段代码在我的笔记本上大概会调用一万多次,然后抛出一个‵StackOverflowError‵。是不是Java中就没有办法进行大规模递归了呢?是。但是有很多可以取巧的办法可以把递归转换成其他什么操作避免栈溢出,而代码看起来仍像递归。比如这篇文章的做法(文章本身说法有问题,实际上是Stream把递归转换成了循环+对象方法调用)。
再比如Groovy中的Trampoline。顺着这个思路来看其实可以达到类似的优化的办法有很多,并不是说一定要用到Stream这个东西。比如实现一个迭代器,稍微包装一下照样可以使代码看起来很像递归。