Understanding Recursion

How it happens internally ?
Lets see what happens when we call the recursive function as sum(3);
Sum(3); will call Sum(2); which will in-turn call sum(1); So the memory stack will have activation records of three functions with each having a local variable n, something like below:

Also consider the fact that when a function calls another, then the state of the calling function (the value of temporary variables, the Instruction Pointer and other register values) is saved in the memory. This state will be reloaded into the memory when the called function will return the control to the calling function
(This is conceptually similar to the Context switch which happens in a muti-processing Operating system when one process is preempted to execute the another process and at sometime the control returns back to this process).
In the iterative version there will be only one function call to Sum(3) and two local variables i & s on the Activation Record(AR) of the function.
We have compared the two for n=3. You may want to compare them for n=1000. The recursive version will take

• Time: O(n)
• Memory: O(n)

While the Iterative version will take:

• Time: O(n)
• Memory: O(1)

The Time may look the same O(n) for both cases, but the constant multiplier with the recursive version will be much bigger than the Iterative version.
So recursion is a huge overhead. Both from memory point-of-view and execution time point-of-view.
Why should we use Recursion then?

Recursion wins in its Simplicity and Intuitive approach. Not every recursive function can be written in an iterative version with such an ease. For example, Tree traversal functions are very easy & intuitive to write in a recursive manner, but a pain to write the non-recursive version (By non-recursive I does not mean the Stack simulation version of recursive).

If the size of Input is large or Unbounded then recursion is not a good idea.

 
Next: Head and Tail Recursion …