Mastering Recursion in C: A Movie Theater Seating Challenge

Why Recursion Still Matters in 2026

Recursion is a fundamental concept in computer science that often trips up students. But with the rise of AI tools like ChatGPT and GitHub Copilot, understanding recursion is more important than ever—these tools use recursive algorithms under the hood. In this tutorial, we'll tackle a classic recursion problem inspired by a real COP 3502C assignment: seating moviegoers with constraints. By the end, you'll be able to generate permutations, check validity, and output results efficiently.

Understanding the Problem: Movie Night with Friends

Imagine you and your friends are heading to the movies. There are n people (3 to 10), each with a name and a flag indicating if they bought popcorn (1) or not (0). Additionally, p pairs of people cannot sit next to each other. The goal is to find all valid seating arrangements where:

• No restricted pair sits adjacent.
• Every person either has popcorn or sits next to someone who does.

For example, with 5 people (Alia, Belinda, Carlos, Danica, Edward) where only Alia and Edward have popcorn, and restrictions (Alia-Carlos, Belinda-Edward), there are exactly 10 valid orderings. Your task is to write two programs: one to count all valid permutations (Program 1) and another to output the first lexicographically valid permutation (Program 2).

Recursion: The Heart of the Solution

The key is to generate all permutations of the n people using recursion. We'll use a classic backtracking approach with a used array to track which names have been placed. For each position, we try each unused name, check if placing it violates any constraints, and recurse. When we've placed all n names, we check the popcorn rule. This runs in O(n * n!) time, acceptable for n ≤ 10.

Step 1: Data Structures

We'll store names in an array of strings, popcorn flags in an integer array, and restrictions in a 2D boolean matrix. Since n is small, we can use static arrays.

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define MAX 10

char names[MAX][20];
int popcorn[MAX];
bool cannotSit[MAX][MAX] = {false};
bool used[MAX];
int perm[MAX];
int count = 0;
int n, p;

Step 2: Input Parsing

Read n and p, then read n lines of name and popcorn flag. Then read p pairs of names, find their indices, and mark cannotSit[i][j] = true.

void readInput() {
    scanf("%d %d", &n, &p);
    for (int i = 0; i < n; i++) {
        scanf("%s %d", names[i], &popcorn[i]);
    }
    char name1[20], name2[20];
    for (int i = 0; i < p; i++) {
        scanf("%s %s", name1, name2);
        int idx1 = -1, idx2 = -1;
        for (int j = 0; j < n; j++) {
            if (strcmp(names[j], name1) == 0) idx1 = j;
            if (strcmp(names[j], name2) == 0) idx2 = j;
        }
        cannotSit[idx1][idx2] = cannotSit[idx2][idx1] = true;
    }
}

Step 3: Validity Checks

We need two checks: one for the seating constraint (when placing a person) and one for the popcorn rule (after full permutation). For the seating constraint, when placing person i at position pos, check if i cannot sit next to the person to the left (if any). For the popcorn rule, after a full permutation, ensure every person either has popcorn or is adjacent to someone who does.

bool canPlace(int person, int pos) {
    if (pos > 0 && cannotSit[person][perm[pos-1]]) return false;
    return true;
}

bool isValidPerm() {
    for (int i = 0; i < n; i++) {
        int person = perm[i];
        if (popcorn[person]) continue;
        bool leftOk = (i > 0 && popcorn[perm[i-1]]);
        bool rightOk = (i < n-1 && popcorn[perm[i+1]]);
        if (!leftOk && !rightOk) return false;
    }
    return true;
}

Step 4: Recursive Permutation Generation

We'll write a recursive function permute(int pos) that tries all unused names at position pos. For Program 1, we count all valid permutations; for Program 2, we stop at the first valid one.

void permute(int pos) {
    if (pos == n) {
        if (isValidPerm()) {
            count++;
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i] && canPlace(i, pos)) {
            used[i] = true;
            perm[pos] = i;
            permute(pos+1);
            used[i] = false;
        }
    }
}

Program 1: Counting Valid Orderings

Simply call permute(0) and print count. The sample input 5 2 yields 10.

Program 2: First Lexicographic Ordering

To get the first lexicographic ordering, we modify the recursion to return early when a valid permutation is found. Since the names are input in alphabetical order, iterating i from 0 to n-1 naturally explores permutations in lex order. We can use a global flag found to stop recursion.

bool found = false;

void permuteFirst(int pos) {
    if (found) return;
    if (pos == n) {
        if (isValidPerm()) {
            found = true;
            // print perm
            for (int i = 0; i < n; i++) {
                printf("%s\n", names[perm[i]]);
            }
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i] && canPlace(i, pos)) {
            used[i] = true;
            perm[pos] = i;
            permuteFirst(pos+1);
            used[i] = false;
            if (found) return;
        }
    }
}

Real-World Connections: AI and Event Planning

Recursion isn't just for homework. Modern AI systems use recursive neural networks for natural language processing. Event planning apps like SeatGeek use similar algorithms to optimize seating for concerts. Even TikTok's recommendation algorithm uses recursive graph traversal to find related content. Understanding recursion helps you think algorithmically, a skill valued in tech interviews at Google, Meta, and startups.

Common Pitfalls and Tips

• Base case: Ensure you check the popcorn rule only after a full permutation.
• Lexicographic order: Since names are input alphabetically, iterating in order works. But if names weren't sorted, you'd need to sort them first.
• Performance: For n=10, n! = 3.6 million, which is fine. But you can prune early using the seating constraint.
• Memory: Use static arrays; no dynamic allocation needed.

Conclusion

Recursion is a powerful tool for generating permutations and solving constraint satisfaction problems. By implementing this movie theater seating challenge, you've practiced recursion, backtracking, and problem decomposition. These skills are directly applicable to more complex problems in AI, scheduling, and optimization. Now go ahead and code your solution—you've got this!