常见Java面试题 – 第四部分：迭代和递归 - ImportNew
| 分类： ,
ImportNew注： 本文是ImportNew编译整理的Java面试题系列文章之一。你可以从这里查看全部的系列。
Q.请写一段代码来计算给定文本内字符“A”的个数。分别用迭代和递归两种方式。
A.假设给定文本为”AAA rating”。迭代方式就很直观，如下：
public class Iteration {
public int countA(String input) {
if (input == null || input.length( ) == 0) {
int count = 0;
for (int i = 0; i & input.length( ); i++) {
if(input.substring(i, i+1).equals(&A&)){
public static void main(String[ ] args) {
System.out.println(new Iteration( ).countA(&AAA rating&));
接下来，递归方式的代码如下：
public class RecursiveCall {
public int countA(String input) {
// exit condition – recursive calls must have an exit condition
if (input == null || input.length( ) == 0) {
int count = 0;
//check first character of the input
if (input.substring(0, 1).equals(&A&)) {
count = 1;
//recursive call to evaluate rest of the input
2nd character onwards)
return count + countA(input.substring(1));
public static void main(String[ ] args) {
System.out.println(new RecursiveCall( ).countA(&AAA rating&)); // Ans. 3
递归比较难以理解，我们用下面的图来进行说明。
Q.理解递归需要了解哪些概念？
A. 可重入方法（re-entrant method）是可以安全进入的方法，即使同一个方法正在被执行，深入到同一个线程的调用栈里面也不会影响此次执行的安全性。一个非可重入方法则不是可以安全进入的。例如，加入写文件或者向文件中写入日志的方法不是可重入方法时，有可能会毁坏那个文件。
如果一个方法调用了其自身的话，我们称之为递归调用。假定栈空间足够的话，尽管递归调用比较难以调试，在Java语言中实现递归调用也是完全可行的。递归方法是众多算法中替代循环的一个不错选择。所有的递归方法都是可重入的，但是不是所有可重入的方法都是递归的。
栈遵守LIFO（Last In First Out）规则，因此递归调用方法能够记住“调用者”并且知道此轮执行结束之返回至当初的被调用位置。递归利用系统栈来存储方法调用的返回地址。 Java是一种基于栈设计的编程语言。
顺着这个思路还有那些问题可以用来面试？
Q.什么情况下应该采用递归？
A. 上面的例子中其实不必采用递归，循环的方式可以达到目的，但是在某些情况下采用递归方式则代码会更加简短易读。递归方法在循环树结构以及避免丑陋的嵌套循环的情况下是非常好用的。
Q.什么是尾递归，为什么需要尾递归？上面的代码用尾递归方式如何重写？
A. 常规递归方法（亦称，头递归）在上面演示了，这种方式会增加调用栈的大小。每次递归，其入口需要被记录在栈中。方法返回之前需要给countA(input.substring(1)的结果加一个count。假定count大于1，那么返回结果就是count + countA(input.substring(1))，当然事先要算出来countA(input.substring(1))才行。同时，这也意味着直到countA(input.substring(1)计算出来才能得到最终的结果。因此，最后需要做的事其实是加法运算，而非递归本身。
尾递归的好处是什么？
在尾递归中，最后要做的是递归，加法运算在之前就已经完成了。一轮递归调用完毕后就没有其他事情了（除了加法运算），因此调用时生成的信息也就没什么用了。这些无用信息可以丢弃，然后用一组新的参数来调用一次递归方法来产生一个新的结果。这也就是说，栈调用减少带来了内存消耗减少并且程序的性能更好。
尾递归重写的代码如下:
public class TailRecursiveCall {
public int countA(String input) {
// exit condition – recursive calls must have an exit condition
if (input == null || input.length() == 0) {
return countA(input, 0) ;
public int countA(String input, int count) {
if (input.length() == 0) {
// check first character of the input
if (input.substring(0, 1).equals(&A&)) {
count = count + 1;
// recursive call is the last call as the count is cumulative
return countA(input.substring(1), count);
public static void main(String[] args) {
System.out.println(new TailRecursiveCall().countA(&AAA rating&));
扩展阅读：
英文原文： ，编译： -
译文链接：
【如需转载，请在正文中标注并保留原文链接、译文链接和译者等信息，谢谢合作！】
关于作者：
2009年北航计算机学院毕业，加入IBM CDL至今。从事过web产品测试及开发工作。目前兴趣主要在游泳和自助穷游上。
讨论快慢离开具体情况（insert/delete和get）都是刷流氓。看楼主的意思，应该是get的情...
tony.chenjy
关于ImportNew
ImportNew 专注于 Java 技术分享。于日 11:11正式上线。是的，这是一个很特别的时刻 :)
ImportNew 由两个 Java 关键字 import 和 new 组成，意指：Java 开发者学习新知识的网站。 import 可认为是学习和吸收， new 则可认为是新知识、新技术圈子和新朋友……
新浪微博：
推荐微信号
反馈建议：ImportNew.
广告与商务合作QQ：
– 好的话题、有启发的回复、值得信赖的圈子
– 写了文章？看干货？去头条！
– 为IT单身男女服务的征婚传播平台
– 优秀的工具资源导航
– 活跃 & 专业的翻译小组
– 国内外的精选博客文章
– UI,网页，交互和用户体验
– JavaScript, HTML5, CSS
– 专注Android技术分享
– 专注iOS技术分享
– 专注Java技术分享
– 专注Python技术分享
& 2018 ImportNew17:14 提问
关于String中的一个递归问题
今天学习java String时，遇到书上讲的一个递归问题，先上代码
import java.util.*;
public class InfiniteRecursion {
public String toStirng() {
return "InfiniteRecursion address: "+ this +"\n";
public static void main(String[] args) {
List&InfiniteRecursion& list = new ArrayList&InfiniteRecursion&();
for(int i = 0; i &2; i++)
list.add(new InfiniteRecursion());
System.out.println(list);
书上讲到在toString()方法里面，编译器会将this转化为String,而转换时会调用toString()方法，这样就产生了递归调用。。我思考了也这么觉得，，但是运行代码时没有报错。把this换成super.toString()也能运行。求请教，为什么没有递归（书上讲的java SE5，我的编译器是1.7的）。
按赞数排序
不会递归。因为你重写的是InfiniteRecursion的toString，而你调用的是List&InfiniteRecursion&的toString
这么写才会递归调用
public class InfiniteRecursion {
public String toString() {
//this关键字会调用this.toString()方法，产生递归
//修改为super.toString()
return "InfiniteRecursion : " +
public static void main(String[] args) {
InfiniteRecursion ir = new InfiniteRecursion();
System.out.println(ir.toString());
//Exception in thread "main" java.lang.StackOverflowError
不会调用toString
返回的是类名@引用地址
import java.util.*;
class Ideone {
public String toStirng() {
return "InfiniteRecursion address: "+ this +"\n";
public static void main(String[] args) {
List&Ideone& list = new ArrayList&Ideone&();
for(int i = 0; i &2; i++)
list.add(new Ideone());
System.out.println(list);
在线编译运行结果
[Ideone@b8fba5, Ideone@9133f6]
我的测试代码：
public static void main(String[] args) {
EverhThingTest ett = new EverhThingTest();
ett.printList();
// ett.printAbclr();
public String toString() {
// TODO Auto-generated method stub
return "ssss"+this+"\n";
private void printList() {
// TODO Auto-generated method stub
List&EverhThingTest& list = new ArrayList&EverhThingTest&();
list.add(new EverhThingTest());
list.add(new EverhThingTest());
System.out.println(list);
你这个问题确实很有意思，建议你在输出时打个断点跟一下，我根据你的代码测试了一下，我这里是可以递归调用，程序没有结果，会报Exception in thread "main" java.lang.StackOverflowError。从下面的错误信息可以看到递归调用了，如下：
Exception in thread "main" java.lang.StackOverflowError
at java.lang.System.arraycopy(Native Method)
at java.lang.String.getChars(String.java:854)
at java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:391)
at java.lang.StringBuilder.append(StringBuilder.java:119)
at java.lang.StringBuilder.&init&(StringBuilder.java:93)
at EverhThingTest.toString(EverhThingTest.java:16)
at java.lang.String.valueOf(String.java:2826)
at java.lang.StringBuilder.append(StringBuilder.java:115)
at EverhThingTest.toString(EverhThingTest.java:16)
at java.lang.String.valueOf(String.java:2826)
at java.lang.StringBuilder.append(StringBuilder.java:115)
at EverhThingTest.toString(EverhThingTest.java:16)
at java.lang.String.valueOf(String.java:2826)
at java.lang.StringBuilder.append(StringBuilder.java:115)
at EverhThingTest.toString(EverhThingTest.java:16)
at java.lang.String.valueOf(String.java:2826)
at java.lang.StringBuilder.append(StringBuilder.java:115)
at EverhThingTest.toString(EverhThingTest.java:16)
at java.lang.String.valueOf(String.java:2826)
at java.lang.StringBuilder.append(StringBuilder.java:115)
at EverhThingTest.toString(EverhThingTest.java:16)
at java.lang.String.valueOf(String.java:2826)
后面还有...
我在JDK1.6和1.7上都试过了，都是不可以的。不知道你的1.7为啥不能递归调用。
顺便说一下，输出list时，调用的toString方法在AbstractCollection类中（我两次跟代码都是跟到了这里，你自己看下是不是一致），代码如下：
public String toString() {
Iterator&E& it = iterator();
if (! it.hasNext())
return "[]";
StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
E e = it.next();
sb.append(e == this ? "(this Collection)" : e);
if (! it.hasNext())
return sb.append(']').toString();
sb.append(',').append(' ');
上面的sb.append(e == this ? "(this Collection)" : e);语句中，会调用StingBuilder的append(Object obj)方法，代码如下：
public StringBuilder append(Object obj) {
return append(String.valueOf(obj));
而上面的String.valueOf(obj)方法的代码如下：
public static String valueOf(Object obj) {
return (obj == null) ? "null" : obj.toString();
可以看到，最终还是指向了obj的toString方法，也就是你自己定义的toString方法。
建议你断点调试下，看看问题所在，期待你的回复。
刚才那个确实没有调用InfiniteRecursion的toString()方法，但是现在这个是调用了RecursionTest的toString()方法。而且也发生了递归。
import java.util.ArrayL
import java.util.L
class RecursionTest {
public String toString() {
System.out.println("this is called");
return "recursion: "+
public class Test {
public static void main(String[] args) {
List&RecursionTest& lr = new ArrayList&RecursionTest&();
lr.add(new RecursionTest());
System.out.println(lr);
统一回复一下，我把toString()方法名写错了，并没有调用我的这个方法，所以最终还是会调用toString()的，也产生了递归了。
准确详细的回答，更有利于被提问者采纳，从而获得C币。复制、灌水、广告等回答会被删除，是时候展现真正的技术了！
其他相关推荐Java递归方法求5!的实现代码
转载 &更新时间：日 23:45:11 & 投稿：mdxy-dxy
这篇文章主要介绍了Java递归方法求5!的实现代码,需要的朋友可以参考下
题目：利用递归方法求5!。
程序分析：递归公式：fn=fn_1*4!
程序设计：
import java.util.S
public class Ex22 {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
Ex22 tfr = new Ex22();
System.out.println(tfr.recursion(n));
public long recursion(int n) {
long value = 0 ;
if(n ==1 || n == 0) {
value = 1;
} else if(n & 1) {
value = n * recursion(n-1);
方法二利用递归方法求5!。
public class lianxi22 {
public static void main(String[] args) {
int n = 5;
rec fr = new rec();
System.out.println(n+"! = "+fr.rec(n));
class rec{
public long rec(int n) {
long value = 0 ;
if(n ==1 ) {
value = 1;
value = n * rec(n-1);
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具> 问题详情
如何使用java实现一个简单的递归程序？
悬赏：0&答案豆
提问人：匿名网友
发布时间：
如何使用java实现一个简单的递归程序？
您可能感兴趣的试题
1什么情况会使用递归?2什么是递归?3反转控制(IOC)和面向方向编程(AOP)在spring中的应用有哪些？4如何结合struts、hibernate、spring开发Web应用?
我有更好的答案
<a href="//www.shangxueba.com/ask/9336110.html" target="_blank" title="当n=5时，下列函数的返回值是：()。[cpp] view plaincopyint foo(int n){if(n当n=5时，下列函数的返回值是：()。[cpp] view plaincopyint foo(int n){if(n<2)retu
请先输入下方的验证码查看最佳答案
图形验证：
验证码提交中……
每天只需0.4元
选择支付方式
支付宝付款
郑重提醒：支付后，系统自动为您完成注册
请使用微信扫码支付(元)
支付后，系统自动为您完成注册
遇到问题请联系在线客服QQ：
恭喜你被选中为
扫一扫-免费查看答案！
请您不要关闭此页面,支付完成后点击支付完成按钮
遇到问题请联系在线客服QQ：
恭喜您！升级VIP会员成功
提示：请截图保存您的账号信息，以方便日后登录使用。
常用邮箱：
用于找回密码
确认密码：关于Java程序中的递归例子，求帮助
Java自学者，最近看到IO，做到一个递归列出文件列表的例子
自己写的不对，仿照例子一样写的，结果也跑不起来
以D盘为目标路径，打印了几行就提示空指向异常
其他盘几乎就直接提示空指向异常了
求帮助，谢谢！
import .io.*;
public class JavaTest26_04{
public static void main(String args[]){
JavaTest26_04 j = new JavaTest26_04();
j.loop("d:\\");
public void loop(String lj){
String list[] =
File f = new File(lj);
if(f.isDirectory()){
list = f.list();
for(int i=0;i&list.i++){
loop(lj + "\\" + list[i]);
System.out.println(lj);
list = f.list();
这一句中list可能为null。看一下File里面的list函数的文档，上面有写：
An array of strings naming the files and directories in the
directory denoted by this abstract pathname.
The array will be
empty if the directory is empty.
Returns {@code null} if
this abstract pathname does not denote a directory, or if an
I/O error occurs.
当File不是目录或者发生I/O错误的时候，会返回null。你这里应该是发生I/O错误了，所以下一个语句会报空指针异常。PS：可能是你的D盘下有一个隐藏的文件夹System Volume Information,访问这个文件夹时会报错。
@lhcpig的解答已经很好了。在for循环前面添加：
if (list != null && list.length & 0)
Copyright & IOQQ - All Rights Reserved.