C Algorithms: Recursion, Divide-and-Conquer & Greedy Paradigm Masterclass

⚡ C (C17 / C23 Standard) 🟢 Lesson 53 📂 Phase 19: Algorithms & Big-O Complexity 📅 2026 Comprehensive Master Edition

📌 Covered in this in-depth guide: Recursion Call Stack · Tail Recursion · Divide-and-Conquer Paradigm · Greedy Choice Property · Fractional Knapsack · Coin Change Problem · Activity Selection

Welcome to Phase 19 (Chapter 53): C Algorithms — Recursion, Divide-and-Conquer & Greedy Paradigm Masterclass! Design paradigms provide templates for solving complex problems. In this guide, you will master recursion mechanics, Divide-and-Conquer strategies, and Greedy Choice algorithms in C.

1Recursion & Tail Recursion Optimization

Recursion occurs when a function calls itself to solve smaller subproblems. Tail Recursion happens when the recursive call is the final statement in the function, allowing compilers (GCC `-O2`) to optimize stack frames away into a simple loop!

2Divide-and-Conquer Strategy

Divide-and-Conquer breaks a problem into smaller independent subproblems, solves them recursively, and combines results (e.g. Merge Sort, Binary Search).

3Greedy Strategy & Fractional Knapsack

C — Fractional Knapsack Problem (Greedy Strategy)▶ Run Code in C Compiler

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

typedef struct {
    double weight;
    double value;
    double ratio; // value / weight
} Item;

static int compareItems(const void *a, const void *b) {
    Item *i1 = (Item *)a;
    Item *i2 = (Item *)b;
    if (i2->ratio > i1->ratio) return 1;
    if (i2->ratio < i1->ratio) return -1;
    return 0;
}

double fractionalKnapsack(Item items[], int n, double capacity) {
    qsort(items, n, sizeof(Item), compareItems);
    double totalValue = 0.0;
    for (int i = 0; i < n; i++) {
        if (capacity <= 0) break;
        if (items[i].weight <= capacity) {
            capacity -= items[i].weight;
            totalValue += items[i].value;
        } else {
            totalValue += items[i].value * (capacity / items[i].weight);
            capacity = 0;
        }
    }
    return totalValue;
}

int main(void) {
    Item items[] = {{10, 60, 6.0}, {20, 100, 5.0}, {30, 120, 4.0}};
    double maxVal = fractionalKnapsack(items, 3, 50.0);
    printf("Maximum Knapsack Value: %.2f\n", maxVal);
    return 0;
}

4Technical FAQs

Q1: What is the core difference between Greedy and Dynamic Programming?

Greedy makes a locally optimal choice at each step without reconsidering past decisions. DP evaluates all subproblem choices and stores optimal solutions to subproblems.

Q2: Does Greedy strategy always guarantee the global optimal solution?

No! Greedy fails for 0/1 Knapsack, but works for Fractional Knapsack, Huffman Coding, and Prim's/Dijkstra's algorithms.

Q3: What causes stack overflow in recursion?

Missing base cases or excessively deep recursive calls exhaust the allocated RAM stack memory frame limit.

Q4: How does tail call optimization work in GCC?

GCC reuses the current stack frame for the next recursive function call instead of allocating a new frame.

Q5: What is the Master Theorem in Divide-and-Conquer?

A mathematical formula used to solve recurrence relations of the form T(N) = aT(N/b) + f(N).