≡ Menu

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]

If you enjoyed this article, you might also like..

  1. 50 Linux Sysadmin Tutorials
  2. 50 Most Frequently Used Linux Commands (With Examples)
  3. Top 25 Best Linux Performance Monitoring and Debugging Tools
  4. Mommy, I found it! – 15 Practical Linux Find Command Examples
  5. Linux 101 Hacks 2nd Edition eBook Linux 101 Hacks Book

Bash 101 Hacks Book Sed and Awk 101 Hacks Book Nagios Core 3 Book Vim 101 Hacks Book

{ 10 comments… add one }

  • Alex September 22, 2013, 3:49 pm

    int fact(int n)
    {
    if (n == 0)
    return 1;
    return n * fact(n – 1);
    }

  • DuskoKoscica October 2, 2013, 7:26 am

    Would it be possible to have main function calling it self?
    I know, some of people will not say…, but lets just consider it for a second.
    How it would work with two function calling eachother at the same time.
    One more thing, it is good to omit global variables, you just don’t need it at the problem above. And who writes sum = sum + count, don’t you just know for a +=, it is not a Pascal for God sake.
    And where is more interesting problems!
    How theory looks at recursion, when to and not use it, and so on…
    There are many talks to say about this subject.

  • Chris October 8, 2013, 6:53 am

    Great post! Another great introduction to recursion is traversing a tree structure. I’ve used this a few times for my students and they seemed to get it.

  • DuskoKoscica October 9, 2013, 3:32 am

    Ok, great!
    So why you don’t share the wisdom with us on traversing a tree structure, I am sure it would be great contribution to the subject…

  • sandeep June 30, 2015, 11:40 pm

    Its great, very useful

  • nithi singh September 5, 2015, 4:10 am

    Yes it’s possible to call a main() func.

  • Mr. Pal September 10, 2015, 7:40 am

    its awesome….
    VERY very thanks for help me

  • shipra October 15, 2015, 11:04 am

    its easy to learn c and very usable.

  • Kartick Kisku December 24, 2015, 4:58 am

    Ohh!!!
    A master mind realy . I want to know more with example of different type of series calculation.

  • Linda Jenifer February 10, 2016, 4:04 am

    Thank you its very useful for me

Leave a Comment