Originally Posted on SeedBx
Welcome to the eight part of the Gentle
Introduction to C series. As said before this series aims to provide you a
brief introduction to C language.
In this post, we will be talking
about the concept of recursion.
Recursion
Recursion is the process in which a function
calls itself directly or indirectly and the corresponding function is called a
recursive function.
Example :
void func() {
// some code...
func();
// some code...
}
The above function func() calls
itself in the function, so this is an instance when a function calls itself
directly in a recursion.
void func1() {
// some code...
func2();
// some code...
}
void func2() {
// some code...
func1();
// some code...
}
In the above code functions func1()
and func2() calls itself, however unlike the previous code both the
functions func1() and func2() calls itself indirectly.
Each recursion function consists of two
parts :
1.
General (Recursive) Case:
The part of the recursive functions which expresses the solution in terms of
smaller version of itself.
2.
Base Case:
The part of the recursive function for which the solution can be stated
non-recursviely.
Let us understand about these parts
through an example,
int fact(int n) {
if(n==1) // - (i)
return 1;
return n*fact(n-1); // - (ii)
}
In the above program, a function fact()
has been described which calculates the factorial of a given number. Here line
-(i) is the base case where as line -(ii) is the general case.
Typically to solve a problem using
recursion, we often try to break the problem statement in terms of smaller
version/ inputs of the given statement and think of a base case for which the
solution can be calculated easily.
Note : If the base case is not defined or not reached then a stack
overflow error/ problem arises.
Example :
int fact(int n) {
return n*fact(n-1);
}
The above function will never
terminate and hence a stack overflow error occurs.
Memory Allocation to Different Function Calls
Whenever a function is called from main(),
a portion of memory is allocated to it on the memory stack. So following the
same pattern, whenever a recursive function calls itself a portion of the
memory stack is allocated to that particular call on top of the previous call.
This process continues until the base case is reached, after which the function
calls are popped from the stack in a Last-In-First-Out (LIFO) manner.
For example, the call stack for
fact(4) will be,
Note : Stack overflow error also occurs when a lot of
function calls/ data are being pushed onto the stack, so that the total calls
exceed the memory/ capacity of the stack.
Comparison with Iterative Method
The fact that every recursive
solution has an iterative counterpart makes them direct candidates for
comparison.
Example :
int fact(int n) {
int res=1;
for(int i=1;i<=n;i++)
res=res*i;
return res;
}
In the above code, fact()
function described earlier is written in an iterative fashion.
Advantages of Recursion over
Iteration
Recursive
programs are often clean and easy to read and understand.
Disadvantages of Recursion over
Iteration
·
Recursion requires higher space
requirements as all the function calls remain in the memory stack until the
base case is reached.
·
Recursion programs are slow, with
respect to time, compared to their iterative counterparts due to all the
function calls and returns overhead.
Recursion is a programming concept
that is not only limited to C and expands to every programming language. Using
recursion is one of the many ways to efficiently use computational powers to do
difficult tasks and problems.
Thanks for reading.
Also See : Function, main() Function
