常见java面试题–第四部分：迭代和递归-java开发java经验技巧

《常见java面试题–第四部分：迭代和递归-java开发java经验技巧》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、常见Java面试题-第四部分：迭代和递归-Java开发Java经验技巧常见Java面试题-第四部分：迭代(iteration)和递归(recursion)本文作者：ImportNcw-郑雯未经许可，禁止转载！ImportNew注：本文是ImportNew编译整理的Java而试题系列文章之一。你可以从这里查看全部的Java面试系列。Q.请写一段代码来计算给定文木内字符“A”的个数。分别用迭代和递归两种方式。A.假设给定文本为”AAArating"。迭代方式就很直观,如下:publicclassIteration{publicintcountA(Stringi

2、nput){if(input二二nul1

3、

4、input,length()二二0){rcturn0;}intcount二0;for(inti二0;i

5、ecursiveCall{publicintcountA(Stringinput)//exitcondition-recursivecallsmusthaveanexitconditionif(input二二null

6、

7、input,length()==0){return0;}intcount=0;//checkfirstcharacteroftheinputif(input.substring(0,1).equals){count二1;//recursivecalltoevaluaterestoftheinput//(i.e.2ndcharacteronw

8、ards)returncount+countA(input.substring(l));}publicstaticvoidmain(String[]args){System,out.printin(newRecursiveCall().countA(〃AAArating〃))；//Ans.3递归比较难以理解，我们用下面的图來进行说明。Q.理解递归需要了解哪些概念?A.可重入方法(re-entrantmethod)是可以安全进入的方法，即使同一个方法正在被执行，深入到同一个线程的调用栈里面也不会影响此次执行的安全性。一个非可重入方法则不是可以安全进入的。例如

9、，加入写文件或者向文件屮写入日志的方法不是可重入方法时，有可能会毁坏那个文件。如果一个方法调用了其自身的话，我们称之为递归调用。假定栈空间足够的话，尽管递归调用比较难以调试，在Ja腹语言中实现递归调用也是完全可行的。递归方法是众多算法小替代循环的一个不错选择。所有的递归方法都是可重入的，但是不是所有可重入的方法都是递归的。栈遵守LIFO(LastInFirstOut)规则，因此递归调用方法能够记住“调用者”并口知道此轮执行结束之返冋至当初的被调用位置。递归利用系统栈来存储方法调用的返回地址。Java是一种基于栈设计的编程语言。顺着这个思路还有那些问题町以用

10、來面试？Q・什么情况下应该采用递归？A.上而的例子屮其实不必采用递归，循环的方式可以达到目的，但是在某些情况下采用递归方式则代码会更加简短易读。递归方法在循环树结构以及避免丑陋的嵌套循环的情况下是非常好用的。Q・什么是尾递归，为什么需要尾递归？上面的代码用尾递归方式如何重写？A.常规递归方法(亦称，头递归)在上而演示了，这种方式会增加调用栈的大小。每次递归，其入口需要被记录在栈屮。方法返回之前需要给countA(input,substring(l)的结果加一个count。假定count大于1,那么返冋结果就是count+countA(input,subst

11、ring(l)),当然事先要算岀来countA(input,substring(l))才行。同时,这也意味着直到countA(input,substring(1)计算出来才能得到最终的结果。因此，最后需要做的事其实是加法运算，而非递归本身。尾递归的好处是什么？在尾递归屮，最后要做的是递归，加法运算在之前就已经完成了。一轮递归调用完毕后就没有其他事情了(除了加法运算)，因此调用时生成的信息也就没什么用了。这些无用信息可以丢弃，然后用一组新的参数来调用一次递归方法来产生一个新的结果。这也就是说，栈调用减少带来了内存消耗减少并冃程序的性能更好。尾递归重写的代码如

12、下：publcclassTai1RecursiveCal1{pu