The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function.

Using recursive algorithm, certain problems can be solved quite easily. Examples of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc

In Recursion user represent a problem in terms of one or more smaller problems, and add one or more base conditions that stop recursion.

For example, we compute factorial n if we know factorial of (n-1). Base case for factorial would be n = 0. We return 1 when n = 0.

When any function is called from main(), the memory is allocated to it on stack.

A recursive function calls itself, the memory for called function is allocated on top of memory allocated to calling function and different copy of local variables is created for each function call. When the base case is reached, the function returns its value to the function by whom it is called and memory is de-allocated and the process continues.

Consider the following program

    // Recursive C program to find sum of digits 
    // of a number
    #include <stdio.h>

    // Function to check sum of digit using recursion
    int sum_of_digit(int n)
    {
        if (n == 0)
           return 0;
        return (n % 10 + sum_of_digit(n / 10));
    }

    // Driven Program to check above
    int main()
    {
        int num = 12345;
        int result = sum_of_digit(num);
        printf("Sum of digits in %d is %d\n", num, result);
        return 0;
    }