📌 Queues: Operations on Queue

A Queue is a linear data structure that follows the FIFO (First-In, First-Out) principle. This means that the element added first will be removed first, just like a queue of people waiting in line.

---

1️⃣ Basic Queue Operations

Operation	Description
Enqueue()	Adds an element to the rear (back) of the queue.
Dequeue()	Removes an element from the front of the queue.
Front() / Peek()	Returns the front element without removing it.
isEmpty()	Checks if the queue is empty.
isFull()	Checks if the queue is full (for fixed-size queues).

---

2️⃣ Implementation of Queue in C

(a) Queue Using Arrays

#include <stdio.h>
#define MAX 5  // Maximum queue size

int queue[MAX], front = -1, rear = -1;

// Enqueue operation
void enqueue(int value) {
    if (rear == MAX - 1) {
        printf("Queue Overflow!\n");
        return;
    }
    if (front == -1) front = 0;  // Set front to first element if empty
    queue[++rear] = value;
    printf("Enqueued: %d\n", value);
}

// Dequeue operation
void dequeue() {
    if (front == -1 || front > rear) {
        printf("Queue Underflow!\n");
        return;
    }
    printf("Dequeued: %d\n", queue[front++]);
    if (front > rear) front = rear = -1; // Reset when queue is empty
}

// Display the queue
void display() {
    if (front == -1) {
        printf("Queue is empty!\n");
        return;
    }
    printf("Queue: ");
    for (int i = front; i <= rear; i++)
        printf("%d ", queue[i]);
    printf("\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    display();
    dequeue();
    display();
    return 0;
}

✅ Simple Implementation
❌ Wastes space when elements are dequeued (fixed front).

---

(b) Queue Using Linked List

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

struct Node *front = NULL, *rear = NULL;

// Enqueue operation
void enqueue(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    
    if (rear == NULL) front = rear = newNode;  
    else {
        rear->next = newNode;
        rear = newNode;
    }
    printf("Enqueued: %d\n", value);
}

// Dequeue operation
void dequeue() {
    if (front == NULL) {
        printf("Queue Underflow!\n");
        return;
    }
    struct Node* temp = front;
    printf("Dequeued: %d\n", front->data);
    front = front->next;
    free(temp);

    if (front == NULL) rear = NULL;
}

// Display queue
void display() {
    if (front == NULL) {
        printf("Queue is empty!\n");
        return;
    }
    struct Node* temp = front;
    printf("Queue: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    display();
    dequeue();
    display();
    return 0;
}

✅ Efficient memory usage
✅ No fixed size limit
❌ More complex (pointers needed)

---

3️⃣ Special Types of Queues

1️⃣ Circular Queue – Overcomes the issue of wasted space in arrays.
2️⃣ Deque (Double-Ended Queue) – Can add/remove from both front & rear.
3️⃣ Priority Queue – Elements are dequeued based on priority, not order.

 

📌 Tradeoffs Between Iteration and Recursion

When solving problems in programming, we often have a choice between iteration (loops) and recursion (function calls). Both approaches have advantages and disadvantages, depending on the problem, performance needs, and memory constraints.

---

1️⃣ Key Differences Between Iteration & Recursion

Feature	Iteration (Loops)	Recursion (Function Calls)
Definition	Uses loops (for, while) to repeat operations	A function calls itself to solve subproblems
Memory Usage	Uses a single stack frame (low memory)	Uses additional stack frames (high memory)
Performance	Faster (no function call overhead)	Slower (function calls add overhead)
Readability	Sometimes complex, especially for tree-based problems	Often more intuitive for recursive structures
Termination	Controlled by loop conditions	Controlled by base cases
Use Case	Best for problems with definite repetition (e.g., array traversal)	Best for divide & conquer problems (e.g., DFS, Trees, Hanoi)

---

2️⃣ Advantages & Disadvantages of Iteration

✅ Advantages of Iteration

✔ Memory Efficient – Uses a single loop variable (no extra stack space).
✔ Faster Execution – No overhead from multiple function calls.
✔ Better for Large Inputs – Avoids stack overflow issues.

❌ Disadvantages of Iteration

✖ Can Be Complex – Some problems (e.g., tree traversal) are harder to express with loops.
✖ Requires Extra Variables – May need additional data structures like stacks or queues.

---

3️⃣ Advantages & Disadvantages of Recursion

✅ Advantages of Recursion

✔ More Natural for Certain Problems – Useful for problems like trees, graphs, backtracking (e.g., DFS, Fibonacci, Tower of Hanoi).
✔ Simpler & Readable Code – Shorter and more intuitive for recursive problems.

❌ Disadvantages of Recursion

✖ Higher Memory Usage – Each function call takes additional stack space (O(n)).
✖ Slower Execution – Function call overhead makes recursion less efficient.
✖ Risk of Stack Overflow – Too many recursive calls can cause memory crashes.

---

4️⃣ Tradeoffs with Example Problems

(a) Factorial (Recursion vs Iteration)

Recursive Approach

#include <stdio.h>

int factorialRecursive(int n) {
    if (n == 0) return 1;  // Base case
    return n * factorialRecursive(n - 1);
}

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

✅ Simple & clean
❌ Stack Overflow risk for large n

Iterative Approach

#include <stdio.h>

int factorialIterative(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

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

✅ Memory efficient & faster
❌ Less intuitive

---

(b) Fibonacci Sequence (Recursion vs Iteration)

Recursive Fibonacci (Inefficient)

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

❌ Time Complexity: O(2^n) (Very slow for large n)
❌ Stack Overhead

Iterative Fibonacci (Optimized)

int fibonacciIterative(int n) {
    int a = 0, b = 1, temp;
    for (int i = 2; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

✅ Time Complexity: O(n)
✅ No Stack Overhead

---

(c) Binary Search (Recursion vs Iteration)

Recursive Binary Search

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;
    if (arr[mid] > key) return binarySearchRecursive(arr, left, mid - 1, key);
    return binarySearchRecursive(arr, mid + 1, right, key);
}

✅ Simpler code
❌ More stack calls

Iterative Binary Search (More Efficient)

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;
}

✅ No recursion overhead
✅ Better for large data sets

---

5️⃣ When to Use Iteration vs Recursion?

Use Iteration When...	Use Recursion When...
You need better performance	Problem naturally follows divide & conquer
Memory usage is a concern	Tree, graph, or backtracking problems
The problem requires repeated steps	You want a more intuitive approach
Problem has a clear looping structure	You can optimize recursion (e.g., memoization)

---

6️⃣ Tail Recursion (Optimized Recursion)

Tail recursion is a special type of recursion where the recursive call is the last operation before returning.
💡 Advantage: Can be optimized into iteration by the compiler.

Example: Tail Recursive Factorial

int tailFactorial(int n, int result) {
    if (n == 0) return result;
    return tailFactorial(n - 1, n * result);
}

🔹 Memory-efficient compared to normal recursion
🔹 Can be converted into an iterative approach

 

📌 Fibonacci Numbers & Tower of Hanoi

---

1️⃣ Fibonacci Numbers

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones:

🔹 Formula:

$$F(n) = F(n-1) + F(n-2)$$

🔹 Base Cases:

$$F(0) = 0, \quad F(1) = 1$$

🔹 Example Sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

(a) Recursive Fibonacci (Simple but Inefficient)

#include <stdio.h>

int fibonacciRecursive(int n) {
    if (n <= 1) return n;  // Base Case
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

int main() {
    int n = 10;
    printf("Fibonacci(%d) = %d\n", n, fibonacciRecursive(n));
    return 0;
}

🔹 Time Complexity: O(2^n) (Exponential, slow)
🔹 Space Complexity: O(n) (Recursive stack)

---

(b) Optimized Fibonacci (Using Iteration)

#include <stdio.h>

int fibonacciIterative(int n) {
    if (n <= 1) return n;
    
    int a = 0, b = 1, temp;
    for (int i = 2; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

int main() {
    int n = 10;
    printf("Fibonacci(%d) = %d\n", n, fibonacciIterative(n));
    return 0;
}

🔹 Time Complexity: O(n) (Linear)
🔹 Space Complexity: O(1) (Constant, no extra memory used)

---

(c) Fibonacci Using Dynamic Programming (Memoization)

#include <stdio.h>

#define MAX 100
int fibCache[MAX];

int fibonacciMemo(int n) {
    if (n <= 1) return n;
    if (fibCache[n] != -1) return fibCache[n];  // Use cached result
    return fibCache[n] = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
}

int main() {
    for (int i = 0; i < MAX; i++) fibCache[i] = -1;
    
    int n = 10;
    printf("Fibonacci(%d) = %d\n", n, fibonacciMemo(n));
    return 0;
}

🔹 Time Complexity: O(n) (Faster than recursion)
🔹 Space Complexity: O(n) (For memoization table)

---

2️⃣ Tower of Hanoi

The Tower of Hanoi is a mathematical puzzle where three pegs (A, B, C) and n disks must be moved while following these rules:

🔹 Rules:
1️⃣ Only one disk can be moved at a time.
2️⃣ A larger disk cannot be placed on a smaller disk.
3️⃣ The goal is to move all disks from peg A to peg C using peg B as an auxiliary.

🔹 Steps for n Disks:

1. Move n-1 disks from A → B (using C).
2. Move the largest disk from A → C.
3. Move n-1 disks from B → C (using A).

🔹 Minimum Moves Required:

$$M(n) = 2^n - 1$$

🔹 Example for n = 3 (Moves = 7):

Move Disk 1 from A to C
Move Disk 2 from A to B
Move Disk 1 from C to B
Move Disk 3 from A to C
Move Disk 1 from B to A
Move Disk 2 from B to C
Move Disk 1 from A to C

---

Recursive Solution for Tower of Hanoi

#include <stdio.h>

void towerOfHanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        printf("Move Disk 1 from %c to %c\n", from, to);
        return;
    }
    towerOfHanoi(n - 1, from, aux, to);  // Move n-1 disks from A to B
    printf("Move Disk %d from %c to %c\n", n, from, to);
    towerOfHanoi(n - 1, aux, to, from);  // Move n-1 disks from B to C
}

int main() {
    int n = 3;  // Number of disks
    towerOfHanoi(n, 'A', 'C', 'B');
    return 0;
}

🔹 Time Complexity: O(2^n) (Exponential)
🔹 Space Complexity: O(n) (Recursive calls)

---

🚀 Summary Table: Fibonacci vs Tower of Hanoi

Problem	Approach	Time Complexity	Best Optimization
Fibonacci	Recursion	O(2^n) (Exponential)	Memoization (O(n))
Fibonacci	Iteration	O(n)	Best for large n
Tower of Hanoi	Recursion	O(2^n)	No major optimizations
Tower of Hanoi	Iteration	Difficult to implement	Mostly solved using recursion

 

📌 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.

 

📌 Recursion: Principles of Recursion

1️⃣ What is Recursion?

Recursion is a programming technique where a function calls itself to solve a problem. It breaks a problem into smaller subproblems until it reaches a base condition.

Example: Factorial Using Recursion

c
#include <stdio.h>

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

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

🔹 Output:

csharp
Factorial of 5 is 120

---

2️⃣ Principles of Recursion

(a) Base Case (Termination Condition)

A base case is the condition where recursion stops. Without it, recursion runs infinitely, causing a stack overflow.

🔹 Example: In the factorial function, the base case is:

c
if (n == 0) return 1;

(b) Recursive Case (Self-Call with Reduced Problem Size)

Each recursive call reduces the problem size and moves toward the base case.

c
return n * factorial(n - 1);

(c) Stack Memory Usage

Each recursive call stores its state in the call stack. When the base case is reached, calls start returning results.

🔹 Example: Recursive Stack for factorial(5)

scss
factorial(5) → factorial(4) → factorial(3) → factorial(2) → factorial(1) → factorial(0)

Each function call waits for the next call to return its value.

---

3️⃣ Types of Recursion

(a) Direct Recursion

A function calls itself directly.

c
void func() {
    func();  // Direct call
}

(b) Indirect Recursion

A function calls another function, which calls it back.

c
void A() { B(); }
void B() { A(); }

(c) Tail Recursion

The recursive call is the last operation before returning.

c
void tailRecursion(int n) {
    if (n == 0) return;
    printf("%d ", n);
    tailRecursion(n - 1);  // Last operation
}

🔹 More memory-efficient than normal recursion.

---

4️⃣ Common Recursion Problems

(a) Fibonacci Series

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

(b) Sum of Digits

c
int sumDigits(int n) {
    if (n == 0) return 0;
    return (n % 10) + sumDigits(n / 10);
}

(c) Reverse a String

c
void reverseString(char str[], int start, int end) {
    if (start >= end) return;
    char temp = str[start];
    str[start] = str[end];
    str[end] = temp;
    reverseString(str, start + 1, end - 1);
}

---

5️⃣ Recursion vs Iteration

Aspect	Recursion	Iteration
Memory Usage	High (Stack)	Low
Speed	Slower (Function Calls)	Faster
Code Simplicity	More Elegant	More Efficient
Example	Factorial using recursion	Factorial using loop

---

6️⃣ When to Use Recursion?

✅ Problems with natural recursive structure (Trees, DFS, Fibonacci).
✅ When code clarity is more important than performance.
✅ When stack space is not a constraint.

🚀 Do you prefer recursion or loops? Let’s discuss! ⬇️