What is recursion, and how do you use it? in C programming

What is recursion, and how do you use it?

In C, a function that calls itself (either directly or indirectly) is said to be recursive. You might be wondering why on earth a function would want to call itself. Perhaps this situation is best explained by an example. One classic case of recursion coming in handy is when a number’s factorial is being calculated. To calculate a number’s factorial value, you multiply that number (x) by its predecessor (x–1) and keep going until you’ve reached 1. For instance, the factorial of 5 can be calculated as shown here:

5 * 4 * 3 * 2 * 1

If x were 5, you could transform this calculation into an equation:

x! = x * (x-1) * (x-2) * (x-3) * (x-4) * 1

To perform this calculation using C, you could write a function called calc_factorial() that would repeatedly call itself, each time decrementing the number being calculated, until you have reached 1. Here is an example of how you might write the calc_factorial() function:

#include <stdio.h>
void main(void);

unsigned long calc_factorial(unsigned long x);
void main(void)
{
int x = 5;
printf(“The factorial of %d is %ld.\n”, x, calc_factorial(x));
}
unsigned long calc_factorial(unsigned long x)
{
if (!x)
return 1L;
return(x * calc_factorial(x-1L));
}

In the preceding example, the calc_factorial() calls itself after decrementing the value of x. If x is equal to 0, the if statement will evaluate to true, and calc_factorial() is not recursively called. Hence, when 0 is reached, the function exits for one last time, returning the value 1. It returns 1 because you can safely multiply any value by 1 and still retain its original value. If your program contained the statement

x = calc_factorial(5);
it would expand out to this:
x = 5 * (5-1) * (4-1) * (3-1) * (2-1) * 1;
Hence, x would evaluate to the factorial of 5, which is 120.

Recursion is a neat concept and can be a great source for experimentation, but it does not come without cost.
Recursive functions tend to take longer than straightforward programming statements (that is, while loops), and they also consume valuable stack space. Each time a recursive function calls itself, its state needs to be saved on the stack so that the program can return to it when it is done calling itself. Invariably, recursive functions can be trouble if they are not carefully thought out. If possible, you should avoid writing recursive functions. For instance, the previous factorial function could have been written this way:

#include <stdio.h>
void main(void);
unsigned long calc_factorial(unsigned long x);
void main(void)
{
int x = 5;
printf(“The factorial of %d is %ld.\n”, x, calc_factorial(x));
}

unsigned long calc_factorial(unsigned long x)
{
unsigned long factorial;
factorial = x;
while (x > 1L)
{
factorial *= --x;
}
return(factorial);
}

This version of the calc_factorial() function uses a while loop to calculate a value’s factorial. Not only is it much faster than the recursive version, but it also consumes a minimal amount of stack space.

Cross Reference:

XIX.11: What is iterative processing?