Recursion

Recursion is Recursion is Recursion is Recursion is Recursion is Recursion is Recursion is Recursion is Recursion is Recursion is Recursion is Recursion is Recursion.

Recursion

Recursion is a powerful concept where a function calls itself to solve a problem. It’s useful for tasks that can be broken down into smaller, similar tasks.

How Recursion Works:

1. Base Case: The simplest case, where the function returns a result without making any further recursive calls.

2. Recursive Case: The function calls itself with modified arguments, moving towards the base case.

Example: Factorial Function (Recursive)

We already saw a recursive factorial function, but let’s break it down:

#include <stdio.h>

// Recursive function to calculate factorial
int factorial(int n) {
    if (n == 0) {
        return 1;  // Base case: factorial of 0 is 1
    }
    return n * factorial(n - 1);  // Recursive case
}

int main() {
    int result = factorial(5);  // 5! = 120
    printf("Factorial of 5: %d\n", result);  // Outputs: Factorial of 5: 120
    return 0;
}

Explanation:

• Base Case: When n is 0, the function returns 1.

• Recursive Case: For any other n, the function multiplies n by the factorial of n-1.

Example: Fibonacci Sequence (Recursive)

The Fibonacci sequence is a classic example of recursion.

#include <stdio.h>

// Recursive function to calculate Fibonacci number
int fibonacci(int n) {
    if (n <= 1) {
        return n;  // Base case: fibonacci(0) = 0, fibonacci(1) = 1
    }
    return fibonacci(n - 1) + fibonacci(n - 2);  // Recursive case
}

int main() {
    int result = fibonacci(5);  // fibonacci(5) = 5
    printf("Fibonacci of 5: %d\n", result);  // Outputs: Fibonacci of 5: 5
    return 0;
}

Explanation:

• Base Case: When n is 0 or 1, return n.

• Recursive Case: Sum of the two preceding Fibonacci numbers.

---

Function Pointers

Function pointers are variables that store the address of a function. They allow you to call functions indirectly and are useful for callback functions and dynamic function dispatch.

Declaration and Usage:

#include <stdio.h>

// Function to be pointed to
void greet() {
    printf("Hello, World!\n");
}

int main() {
    void (*funcPtr)();  // Declare a function pointer
    funcPtr = greet;    // Assign the address of 'greet' to 'funcPtr'
    
    funcPtr();  // Call the function using the pointer
    
    return 0;
}

Explanation:

• void (*funcPtr)(); declares a function pointer funcPtr that points to a function returning void and taking no arguments.

• funcPtr = greet; assigns the address of the greet function to funcPtr.

• funcPtr(); calls the greet function using the pointer.

---

Inline Functions

An inline function is a function that is expanded in line where it is called, rather than being invoked through a function call. This can reduce the overhead of function calls.

Declaration:

#include <stdio.h>

inline int square(int x) {
    return x * x;
}

int main() {
    printf("Square of 4: %d\n", square(4));  // Outputs: Square of 4: 16
    return 0;
}

Explanation:

• Use the inline keyword before the function’s return type.

• The compiler tries to replace the function call with the function’s code to avoid the overhead of a call.

---

Recursive Functions with Multiple Base Cases

Sometimes, a recursive function may have multiple base cases.

Example: Greatest Common Divisor (GCD)

#include <stdio.h>

// Recursive function to find GCD using Euclidean algorithm
int gcd(int a, int b) {
    if (b == 0) {
        return a;  // Base case: GCD(a, 0) = a
    }
    return gcd(b, a % b);  // Recursive case
}

int main() {
    int result = gcd(48, 18);  // GCD of 48 and 18
    printf("GCD of 48 and 18: %d\n", result);  // Outputs: GCD of 48 and 18: 6
    return 0;
}

Explanation:

• Base Case: When b is 0, return a.

• Recursive Case: Compute GCD of b and a % b.

---

Summary

• Recursion involves functions calling themselves, useful for problems that can be broken down into smaller similar problems.

• Function Pointers allow indirect function calls, useful for callbacks and dynamic dispatch.

• Inline Functions can reduce the overhead of function calls by expanding the function’s code at the call site.

• Functions can have multiple base cases in recursion.

---