Recursion : behind the code

Recursion is a very popular concept widely used in programming. This approach can be used to solve those type of problems, in which a part of algorithm is to be repeated to get the solution.
The discussion of this topic, here, is to clearly understand of how RECURSION works? It will be discussed in two sessions. The first session will simply help you to visualize the working pattern of Recursion and the second will explore the strategy to write algorithms using recursion.
Before going through this article, you should have

• Understanding of control flow of function calls.
• Basic understanding of what ‘recursion’ is?
• How stack(internal) is used in C programs.

Session 1: visualize recursion
Now, to understand this concept, the simplest example is -- program of -- finding factorial of a number.

int Factorial (int n) {
    if (n <= 1) {
        return 1;
    } else {
        // “fact” is an integer variable
        fact = n * Factorial (n-1) ;
        return (fact);
    }
}

Whenever a function is called:

• The control goes from the calling function to the called function.
• What happens when a function calls itself? It’s simple, think of what will happen if you write a letter and post it to yourself. Though in case of function calls, it is somewhat confusing of how the control will be transferred from “me” to “me”.
• Also, whenever a function finishes, the control returns to its parent function i.e the function which called it.

To visualize this, follow the steps:

• Suppose you want to find factorial of 5. So you will call the factorial function with argument(n=5).
• Now, suppose that we have several copies of Factorial function in memory. First, main() function calls Factorial(5). Then, Factorial() function calls itself with n=4.
• Though, in the figure, it looks like there are five Factorial functions and in every function, the next Factorial function is called. But, actually, the Factorial() function calls itself recursively and returns to same point after the completion at each step.

Important Notes:

• The image above is just for understanding and visualization of Recursion. In reality, memory have only one copy of the function.
• When a function is called several times(as in this case), the memory for variables(of that function) is reserved those many times separately.The line numbers in the image tries to represent the control flow of process.
• At each function call, the value of 'n' is decreased by 1. So main function calls Factorial function with n=5. Then it calls itself with n=4. It goes on till n reaches to 1. At that point, the function returns to its parent function which called it because it is the base case. This goes on until it finally returns to main function.

-----
Feel free to give suggestions,
Happy Coding :-)