Recursion - adv/lim, factorial, Ackemann's fun

Recursion - adv/disadv, types, factorial, Ackemann's fun, etc.

What is Recursion?

It's a programming technique which facilitates writing simpler, shorter, and clearer code. A fucntion calling itself (either directly or indirectly) is called recursion. There are many programming situations which are very difficult (if not practically impossible) to be modelled without using recursion.

Advantages of using Recursion?

Recursive functions are simpler, clearer, and shorter as compared to their iterative counterparts.Recursive functions focus directly and precisely on the actual problem as compared to their non-recursive counterparts (which need to focus on other manipulations to avoid a recursion).

Disadvantages/Limitations of Recursion?

• Inherently Inefficient - Recursive functions are inherently inefficient as they normally require relatively more space and time to execute. Every single call requires space to have its own set of local variables. In addition the caller needs to retain its own set so that when the callee returns it can resume its own execution. A function call requires some CPU time for context switching as well because the control requires to get transferred from the caller to the callee and then back to the caller. Such inherent overheads can't be eliminated from a recursive function and hence it'll almost always be relatively inefficient than its iterative counterparts. So why to use them? Because ther are certain problems which are very difficult to be designed and devloped (and in turn maintained) without using recursion. There may be cases where you don't really care too much about the performance instead on the correctness and maintainability of the solution. Recursion may be of use in those cases.
• Difficulty in Debugging and fixing bugs - Does it sound little conflicting with what we discussed in the above point? Well... it's not actually. Recursion do facilitate better maintainability as the code is shorter, clearer, and directly focused towards the actual strategy. But, what if you're not very clear about the strategy? Unlike the iterative counterparts you don't get much access to the intermediate results and hence debugging a subtle issue may be frustrating at times particularly in the cases where the function calls itself a large number of times.

Types of Recursion?

• Preemptive Recursion - the normal recursion where a function keeps calling itself unless some boundray condition is satisfied. It's normally achieved by decrementing/incrementing the passed arguments. Example: Recursive Factorial Algorithm where fact(n) calls itself with fact(n-1).
• Non-Premptive Recursion: if a function calls itself from one of its parameters then such a recursion is called Non-Premptive Recursion. Example: Ackermann's function is an example of Non-Preemptie Recursion.

Ackermann_fun(m,n) = n+1 if m=0; Ackermann_fun(m-1, 1) if n=0; Ackermann_fun(m-1, Ackermann_fun(m,n-1)) otherwise.

It's important to note here that iterative counterparts of Preemptive Recursion is relatively easier to find as compared to the same in case of Non-Preemptive Recursion.

Recursive Factorial Function - Code

long int factorial(int n){

 if(n == 0)
  return 1;
 else
  return (n * factorial(n-1));
}

Recursive Factorial Function - Call Sequence for 'factorial(3)'