Recursion - C Tutorial

Recursion

The process of calling a function by itself is called recursion and the function which calls itself is called recursive function. Recursion is used to solve various mathematical problems by dividing it into smaller problems. This method of solving a problem is called Divide and Conquer.

In programming, it is used to divide complex problem into simpler ones and solving them individually.

Example:

 Factorial n, denoted n!, is the product of positive integers from 1 to n. The factorial can be formally defined as: 
factorial(0)=1, (base case)
factorial(n)= n * factorial(n-1), for n > 0. (recursive call)

Recursion shows up in this definition as we define factrorial(n) in terms of factorial(n-1).

Every recursion function should have termination condition to end recursion. In this example, when n=0, recursion stops. The above function expressed in C is:

int fact(int n)
{
        if(n == 0)
        { 
            return 1;
        }
        return (n * fact(n-1));
}
Diagramatic view of recursion