Recursion in C

Recursion is a programming technique that allows the programmer to express operations in terms of themselves.

Recursive Function

In C, this takes the form of a function that calls itself. Any function which calls itself is called recursive function, and such function calls are called recursive calls. Recursion involves several numbers of recursive calls. A useful way to think of recursive functions is to imagine them as a process being performed where one of the instructions is to "repeat the process". For example, recursion may be applied to sorting, searching, and traversal problems.

void recursion() {
    recursion(); /* function calls itself */
}
int main() {}

Recursive functions are very useful to solve many mathematical problems, such as calculating the factorial of a number, generating Fibonacci series, tower of Hanoi etc.

In the following example, recursion is used to calculate the factorial of a number.

#include <stdio.h>
int fact(int);
int main() {
    int n, f;
    printf("Enter the number whose factorial you want to calculate?");
    scanf("%d", & n);
    f = fact(n);
    printf("factorial = %d", f);
}
int fact(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return n * fact(n - 1);
    }
}

We can understand the above program of the recursive method call by the figure given below:

Below is the example to find the nth term of the Fibonacci series.

#include<stdio.h>
int fibonacci(int);
void main() {
    int n, f;
    printf("Enter the value of n?");
    scanf("%d", & n);
    f = fibonacci(n);
    printf("%d", f);
}
int fibonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Memory allocation of Recursive method

Each recursive call creates a new copy of that method in the memory. Once some data is returned by the method, the copy is removed from the memory. As all the variables and statements declared inside function get stored in the stack, a separate stack is maintained at each recursive call. Once the value is returned from the corresponding function, the stack gets destroyed. Recursion involves so much complexity in resolving and tracking the values at each recursive call. So we need to maintain the stack and track the values of the variables defined in the stack.

Consider the following example to understand the memory allocation of the recursive functions.

int display(int n) {
    if (n == 0)
        return 0; // terminating condition
    else {
        printf("%d", n);
        return display(n - 1); // recursive call
    }
}

Explanation

Let us examine this recursive function for n = 4. First, all the stacks are maintained which prints the corresponding value of n until n becomes 0, Once the termination condition is reached, the stacks get destroyed one by one by returning 0 to its calling stack. Consider the following image for more information regarding the stack trace for the recursive functions.