Everything you want to know about Recursion?
Hello again, In this blog, we take a look at one of the more challenging computer science concepts: Recursion . We’ll go over the basics of recursion and hopefully help you develop, or refine, a very important programming skill. Thank you for reading and happy coding! So, let’s get started!!
First, we can ask some questions:
What is recursion?
Why Use Recursion?
Difference between Recursion and Iteration?
How to Use Recursion?
Some Examples…
Stack With Recursion…
What is recursion
Recursion simply means “self reference”. When something refers to itself or describes itself, it is called recursive. Let’s say you and your friends have ordered pizza, and now you want to cut it into equal slices. To do that you cut it in half, then you cut the resulting slices in half, and keep going until there’s enough slices for everyone.
In programming, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Recursive function is a function that calls itself.
Why Use Recursion
Using the recursive algorithm, certain problems can be solved quite easily, Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science. Recursion is a wonderful programming tool. It provides a simple, powerful way of approaching a variety of problems.
Difference between Recursion and Iteration
Recursion and iteration both repeatedly executes the set of instructions. Recursion is when a statement in a function calls itself repeatedly. The iteration is when a loop repeatedly executes until the controlling condition becomes false.
The primary difference between recursion and iteration is that is a recursion is a process, always applied to a function. The iteration is applied to the set of instructions which we want to get repeatedly executed.
A conditional statement decides the termination of recursion and control variable’s value decide the termination of the iteration statement.
How to Use Recursion
In this blog, you will learn to write recursive functions in programming with the help of some examples.
A recursive function requires two parts: a recursive call and a base case. The recursive call is the part of the function that will keep calling itself
Every recursive program follows the same basic sequence of steps:
. Initialize the algorithm. Recursive programs often need a seed value to start with. This is accomplished either by using a parameter passed to the function or by providing a gateway function that is non,recursive but that sets up the seed values for the recursive calculation.
. Check to see whether the current value(s) being processed match the base case. If so, process and return the value.
. Redefine the answer in terms of a smaller or simpler sub-problem or sub-problems.
. Run the algorithm on the sub-problem.
. Combine the results in the formulation of the answer.
. Return the results.
Some Examples
Finally, let’s put the theory into practice. Let’s take a classic example where recursion is the best solution: Writing a function that prints an integer. You can only use putchar function to print.
Using recursive algorithm, certain problems can be solved quite easily.
void print_number(int n)
{
unsigned int x = n;
if (n < 0)
{
putchar('-');
x = -x;
}
if ((x / 10) > 0)
{
print_number(x / 10);
}
putchar(x % 10 + '0');
}Let’s take another example. In this case, we have to write a function that returns the factorial of a given number.
The factorial function (symbol: !) says to multiply all whole numbers from our chosen number down to 1.
Example: 5! is shorthand for 5 × 4 × 3 × 2 × 1
int factorial(int n)
{
int x;
if (n == 0)
{
return (1);
}
else if (n < 0)
{
return (-1);
}
x = n * factorial(n - 1);
return (x);
}Much cleaner than when compared to the iterative solution:
int factorial(int n)
{
int i;
unsigned long long fact = 1;// shows error if the user enters a negative integer
if (n < 0)
return (-1);
else {
for (i = 1; i <= n; ++i) {
fact *= i;
}
return fact;
}
Another example to explain more the concept of recursion by writing a function that returns the value of x raised to the power of y
float _pow_recursion(float x, float y)
{
if (y == 0)
return (1);
if (y < 0)
return (_pow_recursion(x, y + 1) / x);
return (_pow_recursion(x, y - 1) * x);
}We can also illustrate the concept of recursion by writing a function that converts a binary number to an unsigned int
void print_binary(unsigned long int n)
{
if (n > 1)
print_binary(n >> 1);
putchar((n & 1) + '0');
}Stack With Recursion
The stack is used to store the set of new local variables and parameters each time the function is called. The system uses the Stack abstract data type for this purpose. So. we have to track during recursion who called the given method and what arguments are to be handed over. But iteration does not uses stack.
What are the disadvantages of recursive programming over iterative programming?
Note that both recursive and iterative programs have the same problem-solving powers, i.e., every recursive program can be written iteratively and vice versa is also true. The recursive program has greater space requirements than iterative program as all functions will remain in the stack until the base case is reached. It also has greater time requirements because of function calls and returns overhead.
What are the advantages of recursive programming over iterative programming?
Recursion provides a clean and simple way to write code. Some problems are inherently recursive like tree traversals, Tower of Hanoi, etc. For such problems, it is preferred to write recursive code. We can write such codes also iteratively with the help of a stack data structure. For example refer Inorder Tree Traversal without Recursion, Iterative Tower of Hanoi.
Conclusion
So, we can say that this article gives you a piece of deep knowledge about recursion and how to use it. I hope this helped you understand recursion.. Thanks for reading!
Happy learning!
