What is Recursion? How is this helpful and where it is used?
Recursive function is that function which calls itself inside its body. In computer science recursion is very necessary for solving a problem which has the recursive nature.
Take for example we want to calculate the factorial of a positive integer. In mathematics
Factorial (n) = 1 * 2 * 3 .. n; Factorial (n) = n * Factorial (n -1);
Here the problem of factorial of an integer has a problem domain of factorial (n-1) inside it. To solve this recursive nature of this problem we can we can call the function itself inside the function body of factorial calculation.
Code:
unsigned int factorial(unsigned int n )
{
if ( n <= 1 )
{
return 1;
}
else
{
return n * factorial(n - 1);/*Call itself*/
}
}
Many mathematical functions can be defined recursively:
- factorial
- Fibonacci
- Euclid's GCD (greatest common denominator)
- Fourier Transform
Fibonacci numbers are also another frequently solved problem using recursion.
Definition: Fibonacci numbers are a series of positive numbers starting from zero and at any point of position the next number is the sum of last two numbers.
fibonacci(n) = fibonacci (n - 1) + fibonacci(n - 2);
Code:
int fibonacci ( int n )
{
if ( n < 2 )
{
return n;
}
else
{
return fibonacci (n - 1) + fibonacci(n - 2);
}
}
Advantages, Limitation and precaution:
One major advantage of recursion is that it reduces the code complexity. It reduces loop statements and makes code easy to understand.
However it has a major limitation regarding the stack usage. Every call inside the function takes extra stack frames. When inner call goes further inside, call stack grows accordingly. The following example shows how a factorial of 4 takes call stack from the most inner function call.
Call factorial 4
| Call Stack |
| Push 4 |
| Return of factorial |
After inner Call of factorial 3
| Call Stack |
| Push 4 |
| Return of factorial |
| Push 3 |
| Return of factorial |
After inner Call of factorial 2
| Call Stack |
| Push 4 |
| Return of factorial |
| Push 3 |
| Return of factorial |
| Push 2 |
| Return of factorial |
After inner Call of factorial 1
| Call Stack |
| Push 4 |
| Return of factorial |
| Push 3 |
| Return of factorial |
| Push 2 |
| Return of factorial |
| Push 1 |
| Return of factorial |
In this example the stack grows 8 stack frames * sizeof(int) = 8*4= 32 bytes
Only factorial of 4 causes the stack to grow about 32 bytes. Thus we should be very careful to use recursion. It may cause stack overflow at runtime. Most embedded system and system side utilities have very less amount of stack. It is recommended not to use recursion or use it keeping in mind the current stack size and limitations.
About our authors: Team EQA
You have viewed 1 page out of 252. Your C learning is 0.00% complete. Login to check your learning progress.