Q1. Can you write a sample code that will count the number of “A”s in a given text? Show iterative, recursive, and tail recursive approaches?
“AAA rating”
A1.
Iteration
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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 } } |
Recursion
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
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.
Recursion
Tail Recursion
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
public class TailRecursiveCall { public int countA(String input) { //input validation if (input == null || input.length() == 0) { return 0; } return countA(input, 0) ; } public int countA(String input, int count) { // exit condition – recursive calls must have an exit condition 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")); } } |
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.
Q. What is the benefit of tail recursion?
A. 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.
