DSA Day 66: The Tiling Problem (Spatial Recursion)

📅 Date: June 17, 2026

🧠 Mood: The Architect 🏗️

🔥 Topic: DSA Day 66: The Tiling Problem (Spatial Recursion)

🧩 Coding in Two Dimensions

For the past few days, my recursive functions have been dealing with linear data: finding the sum of numbers or searching through a flat array. But the real world isn't one-dimensional. Today, the curriculum threw a spatial reasoning problem at me called the Tiling Problem, and it required a complete shift in how I visualize the Call Stack.

The premise is simple: You have a floorboard of size $2 \times N$. You are given an infinite supply of tiles that are size $2 \times 1$. How many different ways can you arrange the tiles to completely cover the floorboard? At first glance, this feels like a permutation nightmare. But when you break it down using the "Divide and Conquer" mindset, a beautiful mathematical truth emerges.

---

🧱 The Illusion of Choice

In recursion, you don't try to solve the whole board. You only make one choice for the very first tile, and let the recursive function handle the rest. You only have two valid moves:

1. Place it Vertically

If you place a $2 \times 1$ tile vertically, it perfectly fills one column. What is left? A smaller board of size $2 \times (N-1)$.

2. Place it Horizontally

If you place a tile horizontally, it forces you to place another one right below it to fill the $2 \times 2$ gap. What is left after taking up 2 columns? A smaller board of size $2 \times (N-2)$.

Does that logic look familiar? The total ways to tile the board is the sum of the vertical choices plus the horizontal choices. Mathematically: $Ways(N) = Ways(N-1) + Ways(N-2)$. It is literally the Fibonacci Sequence in disguise.

---

💻 The C++ Implementation

#include <iostream>
using namespace std;

int tilingProblem(int n) {
    // 1. BASE CASES
    // A 2x0 board has 1 way to be tiled (do nothing)
    // A 2x1 board has 1 way (one vertical tile)
    if (n == 0 || n == 1) {
        return 1;
    }
    
    // 2. RECURSIVE CHOICES
    int verticalPlacement = tilingProblem(n - 1);
    int horizontalPlacement = tilingProblem(n - 2);
    
    // 3. COMBINE
    return verticalPlacement + horizontalPlacement;
}

int main() {
    int boardLength = 4; // A 2x4 board
    cout << "Total ways to tile the board: " << tilingProblem(boardLength) << endl;
    // Output: Total ways to tile the board: 5
    return 0;
}

---

🎯 The Takeaway

Realizing that complex spatial problems boil down to basic branching recursion is a massive mental breakthrough. Tomorrow, we move from floor tiles to text manipulation: Removing Duplicates from a String using Recursion.