Recursion in C is a programming technique that involves a function calling itself, either directly or indirectly. Recursive functions are useful for solving problems that can be broken down into smaller sub-problems that are similar in nature. The recursive function operates on the sub-problems until they are small enough to be solved directly, and then combines the results to solve the original problem.
Here is an example of a recursive function in C that calculates the factorial of a non-negative integer:
int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
Here, the `factorial` function takes an integer `n` as its argument and returns the factorial of `n` (i.e., the product of all positive integers up to `n`). The function first checks whether `n` is 0; if it is, it returns 1 (since the factorial of 0 is 1). Otherwise, it calls itself recursively with the argument `n – 1`, and multiplies the result by `n`.
For example, to calculate the factorial of 5, we would call the `factorial` function with an argument of 5:
int result = factorial(5);
The function would then call itself with an argument of 4, and so on, until it reaches the base case of `n == 0`. The final result returned by the function would be the factorial of 5, which is 120.
It’s important to note that recursive functions can consume a lot of memory and cause stack overflow errors if they are not written properly. To avoid these issues, recursive functions should have a well-defined base case that terminates the recursion, and should ensure that the recursive calls converge to the base case by making progress towards it (e.g., by reducing the size of the input, as in the example above). In addition, tail recursion can be used to optimize the performance of recursive functions by allowing the compiler to optimize the function call stack.