Java coding questions frequently asked in technical tests and job interviews -- part 4: iteration Vs recursion

Core Java Coding Questions and Answers for beginner to intermediate level

Q1

Q2

Q3

Q4

Q5 - Q8

Q9

Q10

Q11

Q12 - Q14

Q15

Q. Can you write a sample code that will count the number of "A"s in a given text? Show both iterative and recursive approaches?

A. Let's assume the input string is "AAA rating". The iterative approach is pretty straight forward as illustrated below.

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
    }
} 

Now, let's look at the recursive approach.

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
    }
}

Many find it harder to understand recursion, hence let's try it with a simple diagram.

Q.What concepts do you need to know to understand recursion?

A re-entrant method would be one that can safely be entered, even when the same method is being executed, further down the call stack of the same thread. A non-re-entrant method would not be safe to use in that way. For example, writing or logging to a file can potentially corrupt that file, if that method were to be re-entrant.

A function is recursive if it calls itself. Given enough stack space, recursive method calls are perfectly valid in Java though it is tough to debug. Recursive functions are useful in removing iterations from many sorts of algorithms. All recursive functions are re-entrant, but not all re-entrant functions are recursive.

Stack uses LIFO (Last In First Out), so it remembers its ‘caller’ and knows whom to return when the function has to return. Recursion makes use of system stack for storing the return addresses of the function calls.Java is a stack based language.



What follow up question(s) to expect?

Q. When would you use recursion? 
A. Recursion might not be the efficient way to code the above example and iterative approach will do the job, but there are scenarios where recursion is preferred as recursive functions are shorter, simpler, and easier to read and understand. Recursive functions are very handy in working with tree structures and avoiding unsightly nested for loops.

Q. What is a tail recursion, and why would you need it? Can you rewrite the above code with tail recursion?
A. Regular recursive function (aka head recursion) demonstrated above grows the size of the call stack. Each time the function calls itself, another entry has to be pushed onto the stack. The thing the function has to do before returning is add count with the result of countA(input.substring(1), assuming count is greater than 1, the computer has to evaluate count + countA(input.substring(1)), and in order to do that it must evaluate countA(input.substring(1)). This alse mean that you need to wait for the call to countA(input.substring(1) to complete so that you can add the value it returns with count. So, the last thing done here is actually the addition, not the recursive call.


What is the benifit of tail recursion? 

In tail recursion, the last thing done is the recursion and the addition would have been done before. You don't have any use for the old information because there’s nothing to do after the recursive call. You can throw out all of your old information and simply run the function again with the new set of parameters. This means you run with shorter call stack leading to lower memory usage and better performance.

Here is the above rewritten with tail recursion.

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