Introduction to Recursion (A way to write an function in Computer Science world)
Hi, I am Shubham Mishra a computer science engineer, passionate about writing technical posts. While writing posts for algorithms such as Merge Sort and others, I thought that I should write a post on Recursion, which is a way to write a function where a step is repeated for multiple times. But before reading this I would like you to read my previous post Data Structure and Types. Now start with the term Recursion.
When a function is defined in terms of itself that is it is called even inside its own body then it is called a Recursive function. Don't be confused just scroll down and see below picture for a better understanding. Suppose you want to calculate the factorial of '4'. The factorial is calculated by multiplying the terms itself with all the numbers below to it till one. It is as '4 * 3 * 2 * 1 * 1'. The '1' extra is the Factorial(0) = 1.
The factorial function will work as it will return '1' if the factorial is called for zero ('0'), or else it will multiply the term 'n' with the output of factorial function for 'n-1'.
The above diagram represents the actual working of the recursive function. Let me represent it in the code. The below c function is to calculate factorial of a given number 'n'.
The same kind of function can be written for Fibonacci series. The Fibonacci series is also required to repeat the single operation of summation. Let understand it by assuming we want to find out the Fibonacci for the term 'n', then T(n) = T(n-1) + T(n-2) if n > 1, or it returns 1 and 0 for n=1 and n=0 respectively.
In this way, recursion makes the way easier for writing the function for many problems. There are more and more applications are available for recursion but the best application for the recursion is the famous Tower of Hanoi problem. Now let's talk about its disadvantages. The biggest disadvantages for this kind of approach is memory consumptions. Due to repeatedly calling the same function one has to store the current status of the function somewhere before calling the next iteration. This is done by stack approach. When the function is called recursively then the current status for nth term is stored in the top of the stack and the function is called for (n-1)th term. In the same way, the states are stored into the stack and popped out from the same when the recursion starts reverse direction as in the above diagram. This process consumes a lot of memory for storage.
Anyways this is the end of the post 'Recursion Function'. I hope you found a way better approach for writing a function. If you are interested in python then look my this blog, Pygame used for game development. Also view Analysis of Algorithm.Than You.
See my all posts Shubham Mishra
When a function is defined in terms of itself that is it is called even inside its own body then it is called a Recursive function. Don't be confused just scroll down and see below picture for a better understanding. Suppose you want to calculate the factorial of '4'. The factorial is calculated by multiplying the terms itself with all the numbers below to it till one. It is as '4 * 3 * 2 * 1 * 1'. The '1' extra is the Factorial(0) = 1.
The factorial function will work as it will return '1' if the factorial is called for zero ('0'), or else it will multiply the term 'n' with the output of factorial function for 'n-1'.
 |
| Recursion Algorithm |
The above diagram represents the actual working of the recursive function. Let me represent it in the code. The below c function is to calculate factorial of a given number 'n'.
The same kind of function can be written for Fibonacci series. The Fibonacci series is also required to repeat the single operation of summation. Let understand it by assuming we want to find out the Fibonacci for the term 'n', then T(n) = T(n-1) + T(n-2) if n > 1, or it returns 1 and 0 for n=1 and n=0 respectively.
In this way, recursion makes the way easier for writing the function for many problems. There are more and more applications are available for recursion but the best application for the recursion is the famous Tower of Hanoi problem. Now let's talk about its disadvantages. The biggest disadvantages for this kind of approach is memory consumptions. Due to repeatedly calling the same function one has to store the current status of the function somewhere before calling the next iteration. This is done by stack approach. When the function is called recursively then the current status for nth term is stored in the top of the stack and the function is called for (n-1)th term. In the same way, the states are stored into the stack and popped out from the same when the recursion starts reverse direction as in the above diagram. This process consumes a lot of memory for storage.
Anyways this is the end of the post 'Recursion Function'. I hope you found a way better approach for writing a function. If you are interested in python then look my this blog, Pygame used for game development. Also view Analysis of Algorithm.Than You.
See my all posts Shubham Mishra
Ok great, we are done with this post,
Now if you like my way of talk, lets explore more blogs written by me and my inner knowledge,
Get to know answers for common search on Google : A blog for posts which can help you for daily life problems, such as where to get free images, Topic suggestion for the blog.
Computer Science algorithms and other knowledge share : A blog for posts such as best search algorithm, Top interview questions for diffrent technologies, knowledge share for some frameworks or programming languages for the interview or in general terms.
My ideas to solve real world problems : A blog where me shared and presented my ideas to solve a real world problems, this will be interesting for me.
Future of computer science technology discussed : A blog where me discussed about the future of computer science and new technologies which will change our way for looking to solve problems.
Ruby on Rails Web development Blog : As the name suggest, it is the blog for sharing few knowledge about RoR web development framework.
Liked my blogs, wanna to connect:
Thanks for reading this post, Have a good day :)
Comments
Post a Comment