Recursion in C Language

Recursion is the process of repeating items in a self-similar way. In this tutorial, we are going to learn about recurssion and how does it works with using examples.

In programming languages, if a program allows you to call a function inside the same function, then it is called a recursive call of the function. 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 Recursion is a programming technique that allows the programmer to express operations in terms of themselves.

A function that calls itself is known as a recursive function. And, this technique is known as recursion.

How recursion works?

void recurse()
{
    ... .. ...
    recurse();
    ... .. ...
}

int main()
{
    ... .. ...
    recurse();
    ... .. ...
}

A recursive function performs the tasks by dividing it into the subtasks. There is a termination condition defined in the function which is satisfied by some specific subtask. After this, the recursion stops and the final result is returned from the function.

The case in which a function does not recur is called the base case, while the case in which it repeatedly performs a subtask is called the recursive case. Recursive functions can be written by converting the base case to this format.

Example: Sum of Natural Numbers Using Recursion

#include <stdio.h>
int sum(int n);

int main() {
    int num, ans;

    printf("Enter a positive integer: ");
    scanf("%d", &num);

    ans = sum(num);

    printf("sum = %d", ans);
    return 0;
}

int sum(int n) {
    if (n != 0)
        // sum() function calls itself
        return n + sum(n-1);
    else
        return n;
}

Enter a positive integer: 3
sum = 6

Initially, the sum() is called from the main() function with number passed as an argument.

Suppose, the value of n inside sum() is 3 initially. During the next function call, 2 is passed to the sum() function. This process continues until n is equal to 0.

When n is equal to 0, the if condition fails and the else part is executed returning the sum of integers ultimately to the main() function.

Advantages and Disadvantages of Recursion:

• Recursion makes program elegant. However, if performance is vital, use loops instead as recursion is usually much slower.
• Recursion is an important concept. It is frequently used in data structure and algorithms.
• The recursive program has greater space requirements than iterative program as all functions will remain in the stack until the base case is reached.
• Recursion provides a clean and simple way to write code.