📌 Tail Recursion & Removing Recursion (Iteration vs Recursion in Problem Solving)

---

1️⃣ What is Tail Recursion?

Tail Recursion is a type of recursion where the recursive call is the last operation before returning the final result.
💡 Advantage: It can be optimized by compilers to use constant stack space (Tail Call Optimization - TCO).

Example: Tail Recursive Factorial

#include <stdio.h>

int tailFactorial(int n, int result) {
    if (n == 0) return result; // Base Case
    return tailFactorial(n - 1, n * result);  // Tail Call
}

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

🔹 Why Tail Recursive?
👉 The recursive call is the last operation before returning.
👉 No extra computation happens after the function call.

---

2️⃣ Removing Recursion (Converting to Iteration)

Recursion can lead to stack overflow for deep recursion. Iteration avoids this by using loops instead of function calls.

Example: Converting Recursive Factorial to Iterative

#include <stdio.h>

int iterativeFactorial(int n) {
    int result = 1;
    while (n > 0) {
        result *= n;
        n--;
    }
    return result;
}

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

🔹 Advantages of Iteration:
✅ Saves memory (no recursive calls).
✅ Faster execution (no overhead of function calls).

---

3️⃣ Example: Binary Search (Recursion vs Iteration)

Binary search is a classic example where recursion and iteration can be used interchangeably.

Recursive Binary Search

#include <stdio.h>

int binarySearchRecursive(int arr[], int left, int right, int key) {
    if (left > right) return -1; // Base case

    int mid = left + (right - left) / 2;
    
    if (arr[mid] == key) return mid; // Key found
    if (arr[mid] > key) return binarySearchRecursive(arr, left, mid - 1, key);
    return binarySearchRecursive(arr, mid + 1, right, key);
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int size = sizeof(arr) / sizeof(arr[0]);
    int key = 7;
    int result = binarySearchRecursive(arr, 0, size - 1, key);
    
    if (result != -1) 
        printf("Element found at index %d\n", result);
    else 
        printf("Element not found\n");
    return 0;
}

Iterative Binary Search

#include <stdio.h>

int binarySearchIterative(int arr[], int size, int key) {
    int left = 0, right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == key) return mid;
        if (arr[mid] > key) right = mid - 1;
        else left = mid + 1;
    }
    return -1;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int size = sizeof(arr) / sizeof(arr[0]);
    int key = 7;
    int result = binarySearchIterative(arr, size, key);

    if (result != -1) 
        printf("Element found at index %d\n", result);
    else 
        printf("Element not found\n");
    return 0;
}

🔹 Which is better?

Criteria	Recursive Binary Search	Iterative Binary Search
Memory Usage	Higher (Function calls in stack)	Lower (No extra memory needed)
Performance	Slightly slower (Function call overhead)	Faster (No recursion overhead)
Readability	More intuitive	Slightly complex
Tail Recursion?	No	Not applicable

---

4️⃣ When to Use Recursion vs Iteration?

✅ Use Recursion When:
✔ The problem has a natural recursive structure (e.g., Trees, DFS, Fibonacci).
✔ Readability is more important than performance.

✅ Use Iteration When:
✔ Performance and memory efficiency are critical.
✔ The recursion depth can be too large, leading to a stack overflow.