C Language Common pitfalls Recursive function — missing out the base condition
Example
Calculating the factorial of a number is a classic example of a recursive function.
Missing the Base Condition:
#include <stdio.h>
int factorial(int n)
{
return n * factorial(n - 1);
}
int main()
{
printf("Factorial %d = %d\n", 3, factorial(3));
return 0;
}
Typical output: Segmentation fault: 11
The problem with this function is it would loop infinitely, causing a segmentation fault — it needs a base condition to stop the recursion.
Base Condition Declared:
#include <stdio.h>
int factorial(int n)
{
if (n == 1) // Base Condition, very crucial in designing the recursive functions.
{
return 1;
}
else
{
return n * factorial(n - 1);
}
}
int main()
{
printf("Factorial %d = %d\n", 3, factorial(3));
return 0;
}
Sample output
Factorial 3 = 6
This function will terminate as soon as it hits the condition n is equal to 1 (provided the initial value of n is small enough — the upper bound is 12 when int is a 32-bit quantity).
Rules to be followed:
- 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.
Source: Recursive Function
