Tail Call Optimization

From wikipedia

… the main reason for having a Call Stack is to keep track of the point to which each active subroutine should return control when it finishes executing …

Call stack is also used to store the local variables and parameters. Maintaining the stack is very important and no need to mention that it grows based on the function calls we make.

If the last expression of a function (say funA) is nothing but another function (say funB) call, it is called the tail call and it can be easily optimized by the compiler. Compiler recognizes that once funB is done, there is no need to return back to funA and based on this a call stack entry is saved. Please note that the tail function call should be the whole, complete last statement not just a part of the last statement.

This optimization may not be seen as a big thing in imperative programming. But when it comes to the languages where we don’t have the loop constructs, this optimization brings us the huge benefit. Recursive functions can reap considerable benefits based on this.

If the iterative versions of the corresponding recursive versions work faster, then it should be mainly due to the overhead involved in managing the stack.

Though recursive, factorial(50) may return the result quickly but fibonacci(50) would take too much time. This is because the recursive call occurs only once for factorial (factorial(n) = n * factorial(n)) whereas for fibonacci it occurs twice (fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)).

Please see how the recursive factorial function can be optimized to make tail calls.

(Not sure about the Tail Recursive version of Fibonacci terms calculation. I would be happy to see one.)
<update> Simple search on Google returned http://tratt.net/laurie/tech_articles/articles/tail_call_optimization </update>

So, it means that it is still in the programmers’ hand to write the efficient code.

Food for thought: Apart from loops and recursion, is there any other way to accomplish the same but in a faster manner?

Happy Programming!
Cheers!

Advertisements

One thought on “Tail Call Optimization

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s