C Recursion Tutorial

1. What is Recursion?

Recursion occurs when a function calls itself to break down a problem into smaller, more manageable sub-problems. A key part of recursive functions is the base case, which stops the recursion.

2. Example of Recursion in C

Let's look at a simple recursive function to calculate the factorial of a number:

#include <stdio.h>

int factorial(int n) {
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}

int main() {
    int result = factorial(5);
    printf("Factorial of 5 is %d", result);
    return 0;
}
                

This function calls itself until it reaches the base case (n == 0), which prevents infinite recursion.

3. Understanding the Flow of Recursion

In the factorial function above, each recursive call multiplies the current number by the result of factorial(n - 1). The recursion stops when n == 0, returning 1.

4. Recursive Function Design

When designing a recursive function, consider the following:

• Define the base case that stops recursion.
• Ensure each recursive call reduces the problem size.
• Be mindful of stack overflow in deep recursion.

5. Advantages and Disadvantages of Recursion

Recursion simplifies the code for problems like tree traversal and factorial computation. However, it may lead to higher memory usage and stack overflow if not properly managed.

6. Conclusion

Recursion is a powerful tool in C programming, but it should be used carefully. Always ensure a base case is defined, and consider the impact on memory and performance.