C Recursion Fundamentals Explained with Examples

In C programming language, when a function calls itself over and over again, that function is known as recursive function.

The process of function calling itself repeatedly is known as recursion.

In this tutorial, we will understand the concept of recursion using practical examples.

1. C Recursion Concept

Lets start with a very basic example of recursion :

#include <stdio.h>

void func(void)
{
    printf("\n This is a recursive function \n");
    func();
    return;
}

int main(void)
{
    func();
    return 0;
}

In the code above, you can see that the function func(), in its definition calls itself. So, func() becomes a recursive function. Can you guess what will happen when the code (shown above) is executed? If we go by the code, the main() function would call func() once and then func() would continue calling itself forever. Will this be the exact behaviour?

Lets execute the code and check this. Here is the output :

$ ./recrsn
This is a recursive function 

 This is a recursive function 

 ....
 ....

 This is a recursive function 

 This is a recursive function 

 This is a recursive function
Segmentation fault (core dumped)

In the output above:

• The print “This is a recursive function” prints continuously many times.
• A set of three dots “…” is used to omit large part of actual output which was nothing but the same print.
• Towards the end of the output you cab observe “Segmentation fault” or as we popularly say, the program crashes.

Earlier, we thought that the program would continue executing forever because recursive function func() would continue calling itself forever but it did not happen so. The program crashed. Why did it crash?

Here is the reason for this crash :

• For each call to func(), a new function stack is created.
• With func() calling itself continuously, new function stacks also are also created continuously.
• At one point of time, this causes stack overflow and hence the program crashes.

On a related note, it is also important for you to get a good understanding on Buffer Over Flow and Linked Lists.

2. Practical Example of C Recursion

For complete newbies, it ok to have a question like What’s the practical use of recursion? In this section, I will provide some practical examples where recursion can makes things really easy.

Suppose you have numbers from 0 to 9 and you need to calculate the sum of these numbers in the following way :

0 + 1 = 1
1 + 2  = 3
3 + 3 = 6
6 + 4 = 10
10 + 5 = 15
15 + 6 = 21
21 + 7  =28
28 + 8 = 36
36 + 9 = 45

So, you can see that we start with 0 and 1, sum them up and add the result into next number ie 2 then again we add this result to 3 and continue like this.

Now, I will show you how recursion can be used to define logic for this requirement in a C code :

#include <stdio.h>

int count = 1;

void func(int sum)
{
    sum  = sum + count;
    count ++;

    if(count <= 9)
    {
        func(sum);
    }
    else
    {
        printf("\nSum is [%d] \n", sum);
    }

    return;
}

int main(void)
{
    int sum = 0;
    func(sum);
    return 0;
}

If you try to understand what the above code does, you will observe :

• When func() was called through main(), ‘sum’ was zero.
• For every call to func(), the value of ‘sum’ is incremented with ‘count’ (which is 1 initially), which itself gets incremented with every call.
• The condition of termination of this recursion is when value of ‘count’ exceeds 9. This is exactly what we expect.
• When ‘count’ exceeds 9, at this very moment, the value of ‘sum’ is the final figure that we want and hence the solution.

Here is another example where recursion can be used to calculate factorial of a given number :

#include <stdio.h>

int func(int num)
{
    int res = 0;

    if(num <= 0)
    {
        printf("\n Error \n");
    }
    else if(num == 1)
    {
        return num;
    }
    else
    {
        res  = num * func(num -1);
        return res;
    }

    return -1;

}

int main(void)
{
    int num = 5 ;
    int fact  = func(num);

    if (fact > 0)
        printf("\n The factorial of [%d] is [%d]\n", num, fact);

     return 0;
}

Please note that I have used hard coded number ‘5’ to calculate its factorial. You can enhance this example to accept input from user.

The earlier example demonstrated only how at the final call of func() sum was calculated but the reason I used example is because it demonstrates how return values can be used produced desired results. In the example above, the call sequence across different function stacks can be visualized as :

res  = 5 * func(5 -1); // This is func() stack 1
res  = 4 *func(4-1);   // This is func() stack 2
res  = 3 *func(4-1);   // This is func() stack 3
res  = 2 *func(2-1);   // This is func() stack 4
return 1;              // This is func() stack 5

Now, substitute return value of stack 5 in stack 4, the return value of stack 4 (ie res) into stack 3 and so on. Finally, in stack 1 you will get something like

res = 5 * 24

This is 120, which is the factorial of 5, as shown in the output when you execute this recursive program.

$ ./recrsn 

 The factorial of [5] is [120]