一道面试题引发的思考(递归)

前言

某日,去某互联网公司面试,被问到了如下一道面试题:

题目很简单,有一队人,已知第一个人8岁,后一个人比前一个人大两岁,以此类推,问第8个人多少岁?第N个人多少岁。

我拿过笔和纸,不假思索的写下了如下答案:

1
2
3
4
5
6
7
static int getAge(int n){
if(n==1){
return 8;
}else{
return getAge(n-1)+2;
}
}

面试官又问我还有什么需要注意的吗?我说要注意参数不能小于1.

显然,面试官不是很满意,又问我如果N很大会怎么样?

我想了想,说,会出现OOM异常吧,或者超了int的范围。

感觉他还是不满意。

思考

自那过去一段时间,我自认为答得没有问题,也答到了点上(只可惜面试没过O(∩_∩)O哈哈)。

最近又想到了这个问题,决定研究研究。

实践

我用自己的方法,进行了数据测试。当然我把为了测试效果明显,我加大了测试值。

1
2
3
public static void main(String[] args) { 
System.out.println(getAge(1000000));
}

结果使我惊讶,不是OOM异常,而是堆栈异常。

1
Exception in thread "main" java.lang.StackOverflowError

后面我了解到,递归调用,可以假想成一个函数调用另一个函数,而每个函数相当于占用一个栈帧,这些栈帧以先进后出的方式排列起来形成栈。如下图:

upload successful

这样,函数会追寻到栈顶,拿到getAge(1)的值后逐渐返回。如下。

1
2
3
4
getAge(1)=8
getAge(2)=getAge(1)+2=10
getAge(3)=getAge(2)+2=12
getAge(4)=getAge(3)+2=14

可以知道,如果堆栈深度不够的话,就会出现异常。

我们上图所示的异常就是这个原因。

提升

改进一

在研究这个问题时,我发现了一种递归,尾递归。

如下所示:

1
2
3
4
5
6
7
static int getAge1(int n,int result){
if(n==1){
return result;
}else{
return getAge1(n-1,result+2);
}
}

这种递归我们可以看到,带了一个参数result,当他运行到n==1时,直接返回了result,不用在一层层回退进行计算。如下:

1
2
3
4
5
  getAge(4,8)
= getAge(3,8+2)
= getAge(2,8+2+2)
= getAge(1,8+2+2+2)
= 14

一些编译器发现这些函数可以在一个栈帧里进行完成,就会复用栈帧,优化代码。

可惜的是,到目前为止,JAVA在HotSpot(Oracle的JVM)上使用时,并不支持尾递归优化。
据说IBM的JVM支持尾递归优化,有兴趣的童鞋可以试下。

所以这种方案的测试结果肯定也是StackOverflowError啦。

改进二

循环解决:

那时脑子笨,现在想想,这道题用循环也是可以解决的,且不用担心堆栈溢出问题。如下:

While循环:

1
2
3
4
5
6
7
static int getAge2(int n,int result,int step){
while(n>1){
result+=step;
n--;
}
return result;
}

For循环:

1
2
3
4
5
6
static int getAge3(int start,int end,int firstValue,int step){
for(int i=start;i<end;i++){
firstValue+=step;
}
return firstValue;
}

且速度也提高了不少。

改进三

这么有规律的数据,当然乘法就可以解决,如下:

1
2
3
static int getAge4(int start,int end,int firstValue,int step){
return firstValue+(end-start)*step;
}

以上例子没有对入参做校验处理,结合实际场景,其实需要处理的,在此略掉了。

总结

JDK源码中很少有递归,因为递归不能被优化,当数据过大时,很容易出现堆栈溢出,我们也应该慎用,基本能有递归解决的问题也可以用循环解决。

可以看出,对于一个问题,实现的方案可能不止一种。

看到自己想了及总结了多种方法,感觉很诧异,面试时却只想到了递归一种,而且实现很不好。还是自己基础不够扎实,应该多学多看多练。

其他

上面都说要多学多看多练啦…..

这是我测试IBM JDK对于尾递归(getAge1方法)的结果。

upload successful

upload successful

说明IBM JDK确实对尾递归有优化,我又测试了getAge方法(普通递归),结果和Oracle JDK一样,抛出 java.lang.StackOverflowError 异常。




-------------文章结束啦 ~\(≧▽≦)/~ 感谢您的阅读-------------

您的支持就是我创作的动力!

欢迎关注我的其它发布渠道