- The basic definition of a recursive function can be given as below:
A function that calls itself is known as recursive function and the process in which a function calls itself is known as recursion.
Example of Recursion in C programming
- To understand the concept of recursion consider the following program calculating sum of first n natural numbers using recursion.
- Note: Positive integers are known as natural number i.e. 1, 2, 3….n
/* C program to calculate sum of first n natural numbrs.*/
#include "stdio.h"
int sum(int n); // function prototype
void main()
{
int num,add;
printf("Enter a positive integer:\n");
scanf("%d",&num);
add=sum(num); // function call
printf("sum=%d",add);
}
/* Recursive function definition */
int sum(int n)
{
if(n==0) /* condition to break recursion */
return n;
else
return n + sum(n-1); /* recursive call to function sum() */
}
Output:
Enter a positive integer:
5
15
- In, the above program, sum() function is invoked from within the same function.
- If n is not equal to 0 then, the function calls itself passing argument 1 less than the argument it was previously called with.
- Suppose, n is 5 initially. Then, during next function calls, 4 is passed to function and the value of argument decreases by 1 in each recursive call.
- When, n becomes equal to 0, the condition for breaking recursion evaluates to true and hence the value of n is returned which is the sum numbers from 5 to 1.
- The below is the complete recursion calls for better visualization of recursion process:
sum(5) // initial call to sum() function
=5+sum(4)
=5+4+sum(3)
=5+4+3+sum(2)
=5+4+3+2+sum(1)
=5+4+3+2+1+sum(0)
=5+4+3+2+1+0
=5+4+3+2+1
=5+4+3+3
=5+4+6
=5+10
=15
- Note that there must be some way to end the recursion. In this example when, n is equal to 0, there is no recursive call and recursion ends.
Advantages
- Recursion is more powerful and requires few variables which make program clean.
- It can be used to replace complex nesting code by dividing the problem into same problem of its sub-type.
- Recursion can replace large program logic with a few line of code and thus, helps to reduce program code.
Disadvantages
- The major difficulty with recursion is that it is hard to think the logic of a recursive function.
- It is also difficult to debug the code containing recursion.
Comparison of Recursion and iteration
Recursion | Iteration |
---|---|
Recursion is the term given to the mechanism of defining a set or procedure in terms of itself. | Iteration is the block of statement executed repeatedly using loops. |
A conditional statement is required in the body of the function for stopping the function execution |
The iteration control statement itself contains statement for stopping the iteration. At every execution, the condition is checked. |
At some places, use of recursion generates extra overhead. so its better to skip when easy solution is available with iteration. | All problems can be solved with iteration. |
Recursion is expensive in terms of speed and memory. |
Iteration does not create any overhead. All the programming languages support iteration. |
- While using recursion, programmers need to be careful to define an exit condition from the function, otherwise it will go in infinite loop.
- Recursive function are very useful to solve many mathematical problems like calculating factorial of a number, generating Fibonacci series, etc