Prev Next

Recursion in C

Recursion occurs when a function calls itself directly or indirectly. Recursive functions are used to solve problems that can be broken down into similar sub-problems.

Key Topics

1. How Recursion Works

Recursive functions consist of two parts:

  • Base Case: The condition under which the recursion ends.
  • Recursive Case: The part where the function calls itself with a smaller problem.

2. Example: Calculating Factorial

Recursive Function for Factorial

int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1; // Base case
    } else {
        return n * factorial(n - 1); // Recursive case
    }
}

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

3. Example: Fibonacci Sequence

Recursive Function for Fibonacci

int fibonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    int terms = 10;
    printf("Fibonacci Sequence:\n");
    for (int i = 0; i < terms; i++) {
        printf("%d ", fibonacci(i));
    }
    printf("\n");
    return 0;
}

Output:

Fibonacci Sequence:
0 1 1 2 3 5 8 13 21 34

Best Practices

  • Ensure that the base case is reached to prevent infinite recursion.
  • Use recursion when it simplifies the solution to complex problems.
  • Be mindful of stack overflows with deep recursion.

Don'ts

  • Don't forget to define a base case; missing it leads to infinite recursion.
  • Don't use recursion for problems that can be solved iteratively with better performance.
  • Don't ignore the potential for increased memory usage due to recursive calls.

Key Takeaways

  • Recursion involves functions calling themselves to solve sub-problems.
  • Properly designed recursive functions include base and recursive cases.
  • Recursion can simplify code but may have performance considerations.
Prev Next