Recursion Using Stack with Example

A function that calls itself is called a recursive function and this technique is called recursion. A recursive function will call itself until a final call that does not require a call to itself is made. It takes advantage of the system stack to temporarily store the calling function’s return address and local variables.

There are two major cases in any recursive solution. They are

• Base case in which the problem is simple enough to be solved directly without the need for any more calls to the same function
• Recursive case
  • The problem at hand is initially subdivided into simpler sub-parts.
  • The function calls itself again, but this time with sub-parts of the problem obtained in the first step.
  • The final result is obtained by combining the solutions of simpler sub-parts.

A recursive function is said to be well-defined if it has the following two properties:

• There must be a base criteria in which the function doesn’t call itself.
• Every time the function is called itself, it must be closer to the base criteria.

Factorial Function

To illustrate recursive functions, consider calculating the factorial of an integer.

The product of the positive integers from 1 to n is called n factorial denoted by n! . To find n!, multiply the number by the factorial of the number that is one less than the number.

That is, n! = n * (n - 1)!

Assume we need to find the value of 5!.

Then, 5! = 5 * 4!, where 4! = 4 * 3!

Therefore, 5! = 5 * 4 * 3!

Expanding further, we get 5! = 5 * 4 * 3 * 2 * 1!

We can now write a recursive function that computes the factorial of a number. Here the base case is when n = 1, because the result will be 1 as 1! = 1. The recursive case of the factorial function will call itself, but with a smaller value of n, as factorial(n) = n factorial (n–1).

Example: Factorial of a given number

#include <stdio.h>
int Fact(int);
int main()
{
    int num, val;

    //read a number from the user
    printf("Enter the number: ");
    scanf("%d", &num);

    //call fact function
    val = Fact(num);

    //print result
    printf("Factorial of %d = %d", num, val);
    return 0;
}
//function to calculate factorial
int Fact(int n)
{
    if (n == 1)
        return 1;
    else
        return (n * Fact(n-1));
}

Output

Enter the number: 5
Factorial of 5 = 120