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

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

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

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

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

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)计算出来才能得到最终的结果。因此,最后需要做的事其实是加法运算,而非递归本身。

尾递归的好处是什么?

在尾递归中,最后要做的是递归,加法运算在之前就已经完成了。一轮递归调用完毕后就没有其他事情了(除了加法运算),因此调用时生成的信息也就没什么用了。这些无用信息可以丢弃,然后用一组新的参数来调用一次递归方法来产生一个新的结果。这也就是说,栈调用减少带来了内存消耗减少并且程序的性能更好。

尾递归重写的代码如下:

原文发布于微信公众号 - java一日一条(mjx_java)

原文发表时间:2016-04-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程

给初学者:JavaScript 中数组操作注意点

作者:CarterLi https://segmentfault.com/a/1190000012463583 不要用 for_in 遍历数组 这是 JavaS...

1836
来自专栏华章科技

新手上路必学的Python函数基础知识,全在这里了(多段代码举例)

导读:函数是Python中最重要、最基础的代码组织和代码复用方式。根据经验,如果你需要多次重复相同或类似的代码,就非常值得写一个可复用的函数。通过给一组Pyth...

1032
来自专栏yl 成长笔记

工厂模式

1203
来自专栏郭耀华‘s Blog

Java命名规范

Java命名规范 定义规范的目的是为了使项目的代码样式统一,使程序有良好的可读性。 包的命名  (全部小写,由域名定义) Java包的名字都是由小写单词组...

5819
来自专栏http://www.cnblogs.com

内置函数filter()和匿名函数lambda解析

一.内置函数filter filter()函数是 Python 内置的一个高阶函数,filter()函数接收一个函数 f 和一个list,这个函数 f 的作用是...

32312
来自专栏nnngu

算法05 五大查找之:顺序查找

这一篇要介绍的是算法中的查找算法。查找在我们生活中无处不在,比如查公交,查机票,查酒店等等。 首先看一下查找的分类。如下图: ? 那么这一篇要总结的是顺序表中的...

37511
来自专栏码洞

看完Java的动态代理技术——Pythoner笑了

Java的动态代理常用来包装原始方法调用,用于增强或改写现有方法的逻辑,它在Java技术领域被广为使用,在阿里的Sofa RPC框架序列化中你能看到它的身影,H...

953
来自专栏C语言及其他语言

数组越界为什么没有出错

数组越界 在C语言中, 数组属于构造数据类型。一个数组可以分解为多个数组元素,这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不...

39310
来自专栏Linyb极客之路

JVM 方法内联

调用某个函数实际上将程序执行顺序转移到该函数所存放在内存中某个地址,将函数的程序内容执行完后,再返回到转去执行该函数前的地方。

1834
来自专栏九彩拼盘的叨叨叨

学习纲要:JavaScript 数据类型

701

扫码关注云+社区

领取腾讯云代金券