… 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.
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)).
(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?