C Language 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:

  1. 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.
  2. Check to see whether the current value(s) being processed match the base case. If so, process and return the value.
  3. Redefine the answer in terms of a smaller or simpler sub-problem or sub-problems.
  4. Run the algorithm on the sub-problem.
  5. Combine the results in the formulation of the answer.
  6. Return the results.

Source: Recursive Function