Recursion

The problem involves finding the number of ways to tile a floor of size N x 1 using tiles of size 1 x 1 and 4 x 1. The function Tiling takes an integer N as its parameter, representing the length of the floor, and returns the total number of ways to tile it.

int Tiling(int N) {
    if(N < 3) {
        return N;
    }
    int ans = Tiling(N - 1) + Tiling(N - 4);
    return ans;
}

int main() {
    int ans = Tiling(5);
    printf("%d ", ans);
}

1. The base case: If N is less than 3, the function returns N. This is because if the floor length is 1 or 2, there is only one way to tile it (using 1 x 1 tiles), and if it's 0, there are zero ways.
2. The recursive case: If N is 3 or greater, the function calculates the number of ways to tile a floor of length N by adding two recursive calls. The first recursive call Tiling(N - 1) represents the ways to tile the remaining part of the floor after placing a 1 x 1 tile at the beginning. The second recursive call Tiling(N - 4) represents the ways to tile the remaining part of the floor after placing a 4 x 1 tile at the beginning.
3. The result is the sum of these two recursive calls, and it is returned as the final answer.

It’s worth noting that this implementation uses a naive recursive approach, and it may lead to redundant calculations, resulting in high time complexity for larger values of N. Memoization or dynamic programming techniques could be applied to optimize the solution by avoiding repeated calculations and improving overall performance

Tiling(5)
            |
     +-------------+
     |             |
 Tiling(4)      Tiling(1)
     |             |
 +-------+     +-------+
 |       |     |       |
 Tiling(3) Tiling(0)
 |       |
 +-------+
 |       |
 Tiling(2)
 |
 Tiling(1)