Recursion in C is a technique where a function calls itself to sollve a problem. The core idea involves breaking down a complex problem into smaller, similar subproblems until a base case is reached, at which point recursion stops.

Core Principles of Recursion

A recursive function must include a termination condition to prevent infinite loops. Each recursive call should progress toward this condition.

Calculating Factorials Using Recursion

Factorials, such as 5! = 5 × 4 × 3 × 2 × 1 = 120, can be computed iteratively or recursively. The recursive approach leverages the relationship n! = n × (n-1)!.

#include <stdio.h>

int compute_factorial(int num) {
    if (num == 0) {
        return 1;
    } else {
        return num * compute_factorial(num - 1);
    }
}

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

In this example, compute_factorial recursively reduces the problem size until reaching the base case where num is 0.

Printing Digits of an Integer in Order

To print each digit of an integer sequentially, such as input 1234 outputting "1 2 3 4", use recursion to handle the number digit by digit.

#include <stdio.h>

void display_digits(int value) {
    if (value > 9) {
        display_digits(value / 10);
    }
    printf("%d ", value % 10);
}

int main() {
    display_digits(1234);
    return 0;
}

This function recursively divides the number by 10 to process digits from most significant to least, printing them in order.

Computing Fibonacci Numbers Recursively

The Fibonacci sequence, defined as F(n) = F(n-1) + F(n-2) with F(0)=0 and F(1)=1, can be implemented recursively, but this method is inefficient for large values due to repeated calculations.

#include <stdio.h>

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

int main() {
    int fib_result = fibonacci(10);
    printf("Fibonacci number at position 10 is: %d\n", fib_result);
    return 0;
}

Drawbacks of Recursion

Recursive functions have several limitations:

• High Memory Usage: Each recursive call allocates stack memory, which can lead to stack overflow with deep recursion.
• Slow Performance: Frequent stack operations (push/pop) slow downn execution, especially in cases like the Fibonacci example where calculations are duplicated.
• Poor Readability: Recursive code can be harder to understand and maintain compared to iterative solutions.
• Risk of Infinite Loops: Without proper termination conditions, recursion may enter infinite loops.

For instance, computing Fibonacci numbers recursively results in exponential time complexity due to redundant calls, making it impractical for large inputs. In contrast, iterative methods or memoization can improve efficiency.

Practical Considerations

When using recursion, insure the base case is clearly defined to avoid infinite recursion. For performance-critical applications, consider alternative approaches like iteration or dynamic programming to mitigate memory and speed issues.