文档章节

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

crossbell
 crossbell
发布于 2014/06/03 19:21
字数 1096
阅读 20
收藏 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
粉丝 25
博文 172
码字总数 14545
作品 0
海淀
项目经理
Android--面试中遇到的问题总结(三)

《Android 开发工程师面试指南 LearningNotes 》,作者是陶程,由梁观全贡献部分。大家可以去知乎关注这两位用心的少年。这份指南包含了大部分Android开发的基础、进阶知识,不仅可以帮助准备...

sealin
2017/02/22
0
0
金九银十,史上最强 Java 面试题整理。

以下会重新整理所有 Java 系列面试题答案、及各大互联网公司的面试经验,会从以下几个方面汇总,本文会长期更新。 Java 面试篇 史上最全 Java 面试题,带全部答案 史上最全 69 道 Spring 面试...

Java技术栈
09/13
0
0
Java面试:投行的15个多线程和并发面试题

本文由ImportNew -一杯哈希不加盐 翻译自dzone。欢迎加入翻译小组。转载请见文末要求。 多线程和并发问题已成为各种 Java 面试中必不可少的一部分。如果你准备参加投行的 Java 开发岗位面试,...

ImportNew
08/23
0
0
阿里巴巴菜鸟Java一面11个问题,你会几个呢?

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

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

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

snailclimb
05/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

你为什么在Redis里读到了本应过期的数据

一个事故的故事 晚上睡的正香突然被电话吵醒,对面是开发焦急的声音:我们的程序在访问redis的时候读到了本应过期的key导致整个业务逻辑出了问题,需要马上解决。 看到这里你可能会想:这是不...

IT--小哥
今天
2
0
祝大家节日快乐,阖家幸福! centos GnuTLS 漏洞

yum update -y gnutls 修复了GnuTLS 漏洞。更新到最新 gnutls.x86_64 0:2.12.23-22.el6 版本

yizhichao
昨天
5
0
Scrapy 1.5.0之选择器

构造选择器 Scrapy选择器是通过文本(Text)或 TextResponse 对象构造的 Selector 类的实例。 它根据输入类型自动选择最佳的解析规则(XML vs HTML): >>> from scrapy.selector import Sele...

Eappo_Geng
昨天
4
0
Windows下Git多账号配置,同一电脑多个ssh-key的管理

Windows下Git多账号配置,同一电脑多个ssh-key的管理   这一篇文章是对上一篇文章《Git-TortoiseGit完整配置流程》的拓展,所以需要对上一篇文章有所了解,当然直接往下看也可以,其中也有...

morpheusWB
昨天
5
0
中秋快乐!!!

HiBlock
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部