Is Recursion Good or Bad !!!

Why we use Recursion in methods?

1. Code is easier to read
2. Less lines of code
3. Problem solving approach is somewhat divide and conquer: Solve bigger problem by solving simpler sub problems.

Classical Example: Factorial of a number

int factorial(int number)
{
    if (number==1) // simplest sub problem
      return 1;
    //building solution by solving sub problems
    return number*factorial(number-1);   
 }

Cons of Recursion

• Lets say we have to calculate factorial of a very big number. Above method will be called recursively numerous times and each time before making recursive call we need to save next instruction address of calling method. StackOverFlow can easily occur.

What is Tail Call
A method call is said “Tail Call” if calling method directly returns the results of called method and do not performs any other operations on results returned by called method. Let us take example of Factorial(3). Above code will update call stack before calling factorial(2). It processes factorial(2) and gets the next instruction to execute from call stack. Then executes 3*factorial(2). Clearly above piece of code is not having tail call.

Why prefer Tail call style of code:

Tail call code can help compiler take decision of avoiding new stack frames each time method is called. Calling stack frame no longer performs any operations on return value of recursive call. No need of separate stack frame. Calling stack frame can be reused. This will be more memory efficient. This optimization called as tail call optimization becomes significant in case of Recursive methods having having lot of internal method calls.

Factorial Code in Tail Call style

int factorial(int number, int accumulator)
{
  if (number==1)   // simplest sub problem
    return accumulator;
  else
  {
     // tail call code –ready for optimization
     return factorial(number-1, accumulator * number);   
   }
 }

Tail call Support in Programming Languages

Compilers can optimize or transform code written in tail call manner into more memory efficient iterative code. For example:

Code input to Compiler

int factorial(int number)
{
  function foo(data) {
    a(data);
    return b(data);
}

Assembly Language Code generated by compiler

 foo:
  call B
  call A
 ret

Tail call optimization

 foo:
  call B
  jmp  A 

replaces last two lines with a single jump instruction:
Infact in functional languages like scala, tail call elimination is often guaranteed by the language standard.

Factorial Code Snippet in Scala:

import scala.annotation.tailrec
class Factorial2 {
  def factorial(n: Int): Int = {
    @tailrec def factorialAcc(acc: Int, n: Int): Int = {
      if (n <= 1) acc
      else factorialAcc(n * acc, n - 1)
    }
    factorialAcc(1, n)
  }
} 

@tailrec annotation helps the developer writing code in tail style in unit testing. If during compilation any code having @tailrec annotation is not tail optimized by compiler, error will be reorted to developer by compiler.

Arguments for Java not supporting Tail Call Optimization

1. The ability to debug using a stacktrace will get affected if this optimization is performed.
2. Unlike functional languages, Java supports iteration based constructs like loops.
3. Java is going to support "GoTo" construct in Java 8 !!!!

References:

1. https://blogs.oracle.com/darcy/entry/upcoming_jep
2. http://en.wikipedia.org/wiki/Tail_call