Recursion
Hello everyone!
On this blog, we will discuss recursion which is an implicit application of STACK ADT(Abstract Data Type).
A recursive function is defined as a function that calls itself to solve a smaller version of its task until a final call is made that does not require a call to itself.
until a final call is made that does not require a call to itself. Since a recursive function
calls itself repeatedly, it uses the system stack to temporarily store the return address and local variables of the calling function.
the local variables of the calling function. Each recursive solution has two main cases.
They are:
- Basic case, in which the problem is simple enough to be fixed immediately without using other calls to the same function.
- Recursive case, in which the problem to be solved is first divided into simple sub-parts. In a second step, the function calls itself, but with sub-parts of the problem obtained in the first step. Finally, the result is obtained by combining the solutions of the simpler subparts.
To understand recursive functions, let us take an example of calculating factorial of a number.
To calculate n!, we multiply the number with factorial of the number that is 1 less than that number.
Let us say we need to find the value of 5!:
5! = 5 x 4 x 3 x 2 x 1
= 120.
This can be written as follows
5 ! = 5 x 4 !, where 4 ! = 4 x 3 ! Therefore, 5 ! = 5 x 4 x3 !
Similarly, we can also write 5! = 5 x 4 x 3 x 2!
Expanding further 5! = 5 x 4 x 3 x 2 x 1! , We know, 1! = 1
The series of problems and solutions can be given as
shown in picture down below :
Now if you look at the problem carefully, you can see that we can write a recursive function to calculate the factorial of a number. every recursive function must have a base case and a recursive case. For the factorial function :
Every recursive function must have at least one base case. Otherwise, the recursive function will generate an infinite sequence of calls, thereby resulting in an error condition known as an infinite stack.
- The basic case is when n = 1, because if n = 1, the result will be 1 because
1 ! = 1. - The recursive case of the factorial function is called itself, but with a smaller value of n.
With a smaller value of n, this case can be given as follows
factorial(n) = n × factorial (n-1).
Another Example for recursive pow of 2 float (x, 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);
}how the stack performs in the following recursive function using LIFO (Last in First Out):
Sources :
Mastering Algorithms with C By Kyle Loudon
