常见Java面试题（四）：迭代（iteration）和递归（recursion）

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"));
 }
}