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) {
// 退出条件
if (input == null || input.length( ) == 0) {
return 0;
}
int count = 0;
//检查第一个字符
if (input.substring(0, 1).equals("A")) {
count = 1;
}
//递归调用来计算其结果
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"));
}
}
分享到:
相关推荐
强化学习算法-基于python的策略迭代算法policy_iteration实现
强化学习算法-基于python的值迭代算法value-iteration实现
迭代算法,利用matlab编译环境实现迭代求解矩阵最大特征值和特征向量;包含雅克比迭代、高斯迭代和SOR
机器学习 马可夫决策 策略迭代 MATLAB代码
非线形方程的迭代法_牛顿迭代_C++_cpp源代码_数值计算 牛顿迭代 一. 实验名称: 非线形方程的迭代法(2) 二....(如需计算其他 ,需修改函数Function(double x) )牛顿迭代 附件: 1-26liaoli_2_Newton_Iteration.cpp
Gauss-Seidel 迭代是数值计算方法中增加迭代效率,减少迭代时间的一种方法. 采用vs2010,C语言.
迭代与分形,用matlab画koch雪花以及其他一些和迭代与分形有关的图形。
高斯迭代,雅克比迭代,sor迭代,通过判断矩阵是否正定再进行各个操作
采用矩阵迭代的方法生成图像,不断刷新屏幕,最终生成一副图像
雅克比迭代法用来求解线性方程组,使用非常广泛,是最常用的求解非线性方程组的算法
应用于图像分割的学习,里面有关于MRF---ICM----条件迭代算法
什么是迭代(iteration)呢? 给定一个list或者tuple,通过for循环来遍历这个list或者tuple、这种遍历就是迭代(iteration)。只要是可迭代的对象都可以进行迭代、怎么判断一个对象是否是可迭代的对象呢?可以用...
fixed_point_iteration 使用定点迭代计算单变量函数的不动点。... 默认容差和最大迭代次数分别为TOL = 1e-12和imax = 1e6 。 c = fixed_point_iteration(f,x0,TOL)返回函数的固定点 由功能句柄f指
非线形方程的迭代法(2)__cpp源代码_简单迭代_数值计算 数值分析实验报告(二) 一. 实验名称: 非线形方程的迭代...(如需计算其他 ,需修改函数Function(double x) )简单迭代 附件: 1-26liaoli_2_Simple_Iteration.cpp
数值分析计算中,用牛顿迭代法求解矩阵的特征值和特征向量
对象深层迭代 遍历元素的对象,依次将每个元素产生为iteratee函数。 迭代是对对象的深入研究。 如果传递了iteratee,则将它绑定到上下文对象。 每次调用iteratee时都会调用三个参数:(element,path,obj)。 ...
摘要:牛顿迭代法是《数值分析》这门课程中一个重要的计算方法和思想。这次的课程设计是通过在学习中所学习到的牛顿迭代的方法的思想计算方程:求方程 x3+x2-3x-3=0 在1.5附近根。并通过VISUALC++编译程序计算出方程...
This paper gives an iteration method on general sideways parabolic equations. The algorithm is proved to be quite efficient.
这是romberg迭代法的源代码,这是romberg迭代法的源代码
并行计算课程作业,实现jacobi迭代的串行优化,主要是一级和二级cache优化。