Linux C Programming Tutorial Part 18: Recursive functions

Irrespective of the programming language you use, as you start coding more and more, you get to learn concepts that make your code crisp and easy to read/understand. There are several such concepts in the C as well. One of them is 'recursive functions,' which we'll be discussing here in this article.

A recursive function is a function that calls itself. The call can be made directly from within the function's body, or indirectly from within some other function which gets called by the function in question.

Following is an example of direct recursion:

int func (int a)
{
    //statements

    func(a-1);

    // statements

    return 0;
}

And here's an example of indirect recursion:

int func (int a)
{
    //statements

    func_new(a);

    // statements

    return 0;
}

int func_new(int b)
{
    //statements

    func(b-1);

    //statementsur

    return 0;
}

As already mentioned in the beginning, recursion helps you achieve compact code, one that's not only easy to write but easy to understand and review as well. Let's take an example to make this advantage more clear.

I am sure you all must have heard about the concept of factorial. For those who aren't aware, factorial is the result you get when you multiply an integer with all the positive integers less than it. For example, the factorial of 5 is 5x4x3x2x1, which is equal to 120.

Here's a simple code to find the factorial of a number:

#include <stdio.h>

int main()
{
 int a = 0, i = 0, fact = 1;
 printf("Enter a number: ");

 scanf("%d", &a);
 
 for(i=1; i<=a; i++)
 {
 fact = fact * i;
 
 }
 printf("Factorial of the number is: %d ", fact);
 return 0;
}

Note that this code is just to let you know how factorial of a number can be calculated through a C program. The program doesn't take care of corner cases that may affect the accuracy of result it produces.

So this is one of the many ways in which you can calculate factorial of a number without using a recursive function. Now let's see a piece of code that uses recursion to calculate a factorial.

#include <stdio.h>

int factorial (int b)
{
 if(!b)
 return 1;
 
 return (b * factorial(b-1));
}

int main()
{
 int a = 0, fact = 1;
 printf("Enter a number: ");

 scanf("%d", &a);
 
 fact = factorial(a);
 
 printf("Factorial of the number is: %d ", fact);
 return 0;
}

So you can see, the function 'factorial' which actually calculates the factorial is very compact. And if you pay close attention, it's very easy to understand as well.

For those who don't know what's happening, the value that user has entered, say 5, is passed on the to the 'factorial' function when it's first called from within the 'main' function. Inside 'factorial' function, there's a check to see if the input value is zero, which is not true when the function gets called first time with input value '5'.

Then, the return statement contains an expression which multiplies 5 with the return value of 'factorial(4)'. So now, the 'factorial' function executes once again, and we reach the following expression: return (4 * factorial(3)). And then again these steps repeat.

So if you look broadly, here's how these function calls get stacked:

• 5 * factorial(4)
• 4 * facttorial(3)
• 3 * factorial(2)
• 2 * factorial (1)
• 1 * factorial (0)

Now when factorial(0) executes, the 'if' condition in the 'factorial' function becomes true, and value '1' is returned. So now, this is how the above listed calls complete (compare the last entry in previous list with first entry in this list, and so on):

• 1 * 1
• 2 * (1*1)
• 3 * (2*(1*1))
• 4 * (3*(2*(1*1)))
• 5 *  (4 * (3*(2*(1*1))))

Which is effectively 5 * 4 *3 * 2 * 1, which in turn is 120, the factorial of 5.

So this is how recursive functions work. While there's no doubt about the recursive function advantages we listed so far, there are some disadvantages as well.

For example, in our example above, until the call 'factorial(0)' completed, all previous 'factorial' calls were waiting for the function processing to be completed. Not to mention the fact that automatic or local variables occupy memory for each recursive call made.

So there's effectively no savings in storage space when you use recursion. Plus, there's also no gurantee that your code will be faster in execution. The real advantage of a recursive function is when you deal with data structures, which will be discussing later on as part of this ongoing C tutorial series.

Conclusion

To conclude, while you may not use recursive function frequently in your day to day coding tasks, it's an important concept that you must be aware of. Try out the example we've mentioned here, and tweak it to understand the concept of recursive functions even better.