文档章节

常见Java面试题 – 第四部分:迭代(iteration)和递归(recursion)

crossbell
 crossbell
发布于 2014/06/03 19:21
字数 1096
阅读 20
收藏 0
点赞 0
评论 0

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

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

A.假设给定文本为”AAA rating”。迭代方式就很直观,如下:

 public class Iteration {
 
    public int countA(String input) {
        if (input == null || input.length( ) == 0) {
            return 0;
        }
 
        int count = 0;
        for (int i = 0; i < input.length( ); i++) {
            if(input.substring(i, i+1).equals("A")){
                count++;
            }
        }
        return count;
    }
 
    public static void main(String[ ] args) {
          System.out.println(new Iteration( ).countA("AAA rating"));     // Ans.3
    }
}

接下来,递归方式的代码如下:

 public class RecursiveCall {
 
    public int countA(String input) {
 
        // exit condition – recursive calls must have an exit condition
        if (input == null || input.length( ) == 0) {
            return 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
        //(i.e.  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 0;
  }
 
  return countA(input, 0) ;
 }
 
 public int countA(String input, int count) {
  if (input.length() == 0) {
   return count;
  }
 
  // 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"));
 }
}

本文转载自:http://www.importnew.com/2329.html

共有 人打赏支持
crossbell
粉丝 24
博文 167
码字总数 14545
作品 0
海淀
项目经理
阿里巴巴菜鸟Java一面11个问题,你会几个呢?

近日,w3cschool app开发者头条上分享了阿里菜鸟Java程序员一些面试题。 这吸引了不少程序员小伙伴们的注意。 在分享阿里菜鸟Java程序员面经前,来看下Java面试一些面试经验分享: 0、Java高...

W3Cschool ⋅ 04/03 ⋅ 0

面试中关于Java虚拟机(jvm)的问题看这篇就够了

最近看书的过程中整理了一些面试题,面试题以及答案都在我的文章中有所提到,希望你能在以问题为导向的过程中掌握虚拟机的核心知识。面试毕竟是面试,核心知识我们还是要掌握的,加油~~~ 下面...

snailclimb ⋅ 05/12 ⋅ 0

java编程学习常见面试题及答案

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰 ⋅ 05/22 ⋅ 0

百词斩Java程序员面试11个问题,你会几个?2018-04-10

近日,我们在w3cschool app开发者头条上,可以看到百词斩Java程序员面经。 在分享百词斩Java面经前,w3cschool特别给程序员小伙伴们带来一些Java学习干货: 0、学习Java必备的3大神器 如果你...

W3Cschool ⋅ 04/10 ⋅ 0

创建《Java程序员学习群》,请报名

最近会创建一个《Java程序员学习群》,每天一个技术题讨论,这个题可能是在工作中的问题,也可能是在面试过程中的面试题。 知识内容涉及到架构设计、Java语言深度解析、JVM深入理解、MySQL深...

小怪聊职场 ⋅ 05/07 ⋅ 0

如何理解并掌握 Java 数据结构

一说起“数据结构”可能很多同学都又交给老师了。但是实际工作中如果做得深入一些,特别是越往上发展,越大公司越离不开数据结构。本场 Chat 作者将带领大家重温《Java 数据结构》,讲解的内...

valada ⋅ 04/12 ⋅ 0

CSDN日报180524——《一个合格的程序员,需要哪些必备技能?》

程序人生 | 一个合格的程序员,需要哪些必备技能? 作者:hollischuang 本文,主要来简单介绍一下,作为一个合格的 Java 开发,除了自身技术成长之外,还有哪些方面可以提升。 点击阅读全文 ...

blogdevteam ⋅ 05/24 ⋅ 0

学习Java和Spring Boot Cloud ,不妨看看这个

专注于编程、互联网动态。最终将总结的技术、心得、经验(数据结构与算法、源码分析等)分享给大家,这里不只限于技术!还有职场心得、生活感悟、以及面经。 1 java版web项目 java版web项目,...

b644rofp20z37485o35m ⋅ 05/04 ⋅ 0

Java 8 停止维护,Java 9 难产,IDEA 2018 发布,还有……

祝大家五一劳动节快乐,工作顺利! 又到了总结上个月干货的时候了,这个月我们带来了各种Java技术干货,各种送书抽奖福利,各种面试题分享,各种最新动态资讯等。 - 5.1重磅活动 区块链免费送...

Java技术栈 ⋅ 04/30 ⋅ 0

面试必看!2018年4月份阿里最新的java程序员面试题目

目录 技术一面(23问) 技术二面(3大块) 性能优化(21点) 项目实战(34块) JAVA方向技术考察点(15点) JAVA开发技术面试中可能问到的问题(17问) 阿里技术面试1 1.Java IO流的层次结构...

美的让人心动 ⋅ 04/16 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

收集自网络的wordpress 分页导航的代码教程(全网最全版)

wordpress 分页导航是用来切换文章的一个功能,添加了 wordpress 分页导航后,用户即可自由到达指定的页面数浏览分类文章,而这样的一个很简单功能却有很多朋友在用插件:WP-PageNavi,插件的...

Rhymo-Wu ⋅ 21分钟前 ⋅ 0

微服务 WildFly Swarm 入门

Hello World 就像前面章节中的其他框架一样,我们希望添加一些基本的 Hello-world 功能,然后在其上逐步添加更多的功能。让我们从在我们的项目中创建一个 HolaResources 开始。您可以使用您的...

woshixin ⋅ 28分钟前 ⋅ 0

Maven的安装和Eclipse的配置

1. 下载Maven 下载地址 2. 解压压缩包,放到自己习惯的硬盘中 此处我将其放到了 D:\Tools 目录下。 3. 配置环境变量 右键此电脑 -> 属性 -> 高级系统设置 -> 环境变量。 在系统变量中新建,变...

影狼 ⋅ 35分钟前 ⋅ 0

python pip使用国内镜像的方法

国内源 清华:https://pypi.tuna.tsinghua.edu.cn/simple 阿里云:http://mirrors.aliyun.com/pypi/simple/ 中国科技大学 https://pypi.mirrors.ustc.edu.cn/simple/ 华中理工大学:http://......

良言 ⋅ 35分钟前 ⋅ 0

对于url变化的spa应该如何使用微信jssdk

使用vue单页面碰上微信jssdk config验证失败的坑。第一次成功 之后切换页面全部失败,找到了解决方法,第一次验证成功后保存验证信息 切换页面时验证信息直接拿来用,加一个wx.error() 失败时...

孙冠峰 ⋅ 40分钟前 ⋅ 0

Spring Cloud Gateway 一般集成

SCF发布,带来很多新东西,不过少了点教程,打开方式又和以前的不一样,比如这个SCG,压根就没有入门指导,所以这里写一个,以备后用。 一、集成 pom.xml <dependency> <groupI...

kut ⋅ 43分钟前 ⋅ 0

建造模式

《JAVA与模式》之建造模式

Cobbage ⋅ 57分钟前 ⋅ 0

WePY框架开发的小程序如何在微信web开发者工具中运行起来

一、首先需要安装node.js,安装步骤如下: 首先下载安装包 https://nodejs.org/en/download/ 点击下载相应的zip版本 然后将文件夹解压到任意目录 比如我这里解压到了:C:\Program Files\node...

Helios51 ⋅ 今天 ⋅ 0

使用EnumSet 代替位域(32)

1、位域(Bit field):使用or 运算将几个常量合并到一个集合中 位操作,可以有效地执行 AND 、OR 这样的位操作 但是 位域比int 常量枚举缺点更多 2、java.util 包里面的EnumSet 类是有效的替...

职业搬砖20年 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部