Skip to main content

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 :-)
Labels:

Comments

Post a Comment

Popular posts from this blog

error: invalid application of ‘sizeof’ to incomplete type ‘struct ’

list.c:47:39: error: invalid application of ‘sizeof’ to incomplete type ‘struct Litsnode’ So, I was trying to run a program based on linked list and this is what I got. This is a very silly problem. I am mentioning it here just to help those who got frustrated like me :-\ Let me show you the line where this error occurred : 46   struct Listnode * newnode; 47   newnode = (struct Listnode *) malloc(sizeof(struct Litsnode)); Now, View it properly. Check the name(spelling) of the structure mentioned to sizeof : " struct Li ts node ". Though the defined name of the structure was : " struct Listnode " That's it.  This happens all the time that we may type something wrong. The important thing is to identify it. :-) Feel free to give any suggestions :)
3 comments
Read more

Expandable Arrays in C : behind the code

Arrays. They are beautiful. In C, we always try to work through restrictions arrays have i.e the size of the array must be statically defined. We always want a dynamic array whose size can be decided at run-time. There are ways which we use widely for e.g by using pointers and then dynamically allocating memory to it using malloc or calloc. But depending on the situation, we might require more efficient and organizable ways. I will explain the concept with a series of examples as in how simple arrays evolved to the tricky expandable ones. The classic way is to use pointers This snippet will allocate a memory block of size = array_size(integer array). Though this is not what I wanted to explain because this way is too clumsy. Imagine if you need 10 dynamic arrays in your program, you have to write these four lines each time and you have to keep track of all the 10 sizes. A better way is to use structures: We can simply create a structure containing two elements: array_size and...
2 comments
Read more

The First C Program - Hello World! : Behind the code

This code will print Hello World! as output. #include <stdio.h> int main() { printf("Hello World!\n"); return 0; } To understand more, I would recommend to go through following: 1. Preprocessor macros # directive is for C preprocessor. #include simply looks for file stdio.h and includes the complete file in the current program. stdio.h is a header file which contains the declaration of variables, macros and functions of C standard library. 2. main() function This is the function which acts as starting point for C program. Its return type is int, which is followed as per ISO C89/99 standard. The system considers a program to have run successfully if at the end, it returns 0. So, in my opinion, this might have been the reason to choose int as the return type of main. 3. Logic Further, more functions and logic can be included inside main() to complete a desired task. In the above program, we are only printing one line and thats "Hello World!". 4...
Post a Comment
Read more