Why we use Recursion in methods?
- Code is easier to read
- Less lines of code
- 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.
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
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:
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
- The ability to debug using a stacktrace will get affected if this optimization is performed.
- Unlike functional languages, Java supports iteration based constructs like loops.
- Java is going to support "GoTo" construct in Java 8 !!!!
- https://blogs.oracle.com/darcy/entry/upcoming_jep
- http://en.wikipedia.org/wiki/Tail_call
.jpg)
