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

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

常见Java面试题-第四部分迭代

(iteration)和递归(recursion)

本文  ImportNcw-郑雯未经许可禁止

ImportNew注本文是ImportNew编译整理的Java而试题系列文章之一。你可以从这里查看全部的Java面试系列。

Q.请写一段代码来计算给定文木内字符“A”的个数。分别用迭代和递归两种方式。

A.假设给定文本为” AAA rating" 。迭代方式就很直观,如下:publ ic class Iterat ion {publ ic int countA(String input ) {if ( input二二nul1 | | input , length( )二二0) { rcturn 0;

}int count二0;for ( int i二0; i < input , length( ) ; i++) { if ( in put . substrin g( i , i + 1 ) ・ cquei lsC'A” ) ) { count++;

}

}return count ;

}publ ic static void main(String[ ] args) {

System, out . print ln(new Iteration( ) .countA( 〃AAA rating〃 ) ) // Ans . 3

}

}

接下來递归方式的代码如2publ ic class RecursiveCal l {publ ic int countA(String input )

// exi t condi tion - recursive cal ls must have an exi t condi tion if

( input二二nul l | | input , length( ) == 0) {

return 0;

} int count = 0;

//check first character of the inputif ( input . substring(0, 1) . equal s ){ count二1 ;

//recursive cal l to evaluate rest of the input

//( i . e. 2nd character onwards) return count + countA( input .substring( l ) ) ;

}publ ic static void main(String[ ] args) {

System, out . printin (new RecursiveCal l ( ) . countA( 〃AAArat ing〃 ) )  // Ans . 3

递归比较难以理解我们用下面的图來进行说明。

Q.理解递归需要了解哪些概念?

A.可重入方法(re-entrant method)是可以安全进入的方法即使同一个方法正在被执行深入到同一个线程的调用栈里面也不会影响此次执行的安全性。一个非可重入方法则不是可以安全进入的。例如加入写文件或者向文件屮写入日志的方法不是可重入方法时有可能会毁坏那个文件。

如果一个方法调用了其自身的话我们称之为递归调用。假定栈空间足够的话尽管递归调用比较难以调试在Ja腹语言中实现递归调用也是完全可行的。递归方

法是众多算法小替代循环的一个不错选择。所有的递归方法都是可重入的但是不是所有可重入的方法都是递归的。

栈遵守LIFO (Last In First Out)规则因此递归调用方法能够记住“调用者” 并口知道此轮执行结束之返冋至当初的被调用位置。递归利用系统栈来存储方法调用的返回地址。 Java是一种基于栈设计的编程语言。

顺着这个思路还有那些问题町以用來面试

Q・什么情况下应该采用递归

A.上而的例子屮其实不必采用递归循环的方式可以达到目的但是在某些情况下采用递归方式则代码会更加简短易读。递归方法在循环树结构以及避免丑陋的嵌套循环的情况下是非常好用的。

Q・什么是尾递归为什么需要尾递归上面的代码用尾递归方式如何重写

A.常规递归方法(亦称头递归)在上而演示了这种方式会增加调用栈的大小。每次递归其入口需要被记录在栈屮。方法返回之前需要给coun t A(input, subs tring(l)的结果加一个coun t 。假定count大于1 ,那么返冋结果就是coun t + coun tA(input, subs tring(l)),当然事先要算岀来countA( input , substring( l ) )才行。同时,这也意味着直到coun tA(input, subs tring(1)计算出来才能得到最终的结果。因此最后需要做的事其实是加法运算而非递归本身。

尾递归的好处是什么

在尾递归屮最后要做的是递归加法运算在之前就已经完成了。一轮递归调用完毕后就没有其他事情了(除了加法运算) 因此调用时生成的信息也就没什么用了。这些无用信息可以丢弃然后用一组新的参数来调用一次递归方法来产生一个新的结果。这也就是说栈调用减少带来了内存消耗减少并冃程序的性能更好。尾递归重写的代码如下publ\ c class Tai 1RecursiveCal1 {publ ic int countA(String input ) {

// exi t condi tion - recursive cal ls must have an exi t condi t ionif ( input二二nul l | | input . 1 ength( ) == 0) {return 0;

}return countA( input , 0) ;

}publ ic int countA(String input , int count ) {if ( input , length( )二二0) {return count ;

}

// check first character of the inputif ( input . substring(0, 1) . equal s ){count = count + 1 ;

}

// recursive cal l is the last cal l as the count is cumulative returncountA( input . subst ring( l ) , count ) ;

}publ ic static void main(String[ ] args) {

System, out . printin(new Tai lRecursiveCal l ( ) . countA( 〃AAA rating〃 ) ) ;扩展阅读

• 常见Java面试题-第一部分:非可变性(Immutab ility)和对象引MJ(Obj ect reference)

• 常见Java面试题-第二部分 equal s与二二

• 常见Java面试题-第三部分重载(overlo ading)与覆盖(overriding)

英文原文 Java Success ,编译 ImportNew?-?郑雯

译文链接 . importnew. 2329.

【如需请在正文屮标注并保留原文链接、译文链接和译者等信息谢谢合作 】关于 郑雯

2009年北航计算机学院毕业加入IBMCDL至今。从事过web产品测试及开发工作。口前兴趣主要在游泳和自助穷游上。

查看郑雯的更多文章>>