Recursion and backtracking

#1

chrome
chrome1080×2160 198 KB
in tilling problem in recursion section i am not able to understand how
F(n)=F(n-1)+F(n-4)

#2

Hey Mayur, this is because we can place a tile either horizontally or vertically,
if you place it vertically n becomes n-1
and if you place it horizontally n becomes n-4
That’s why F(n)=F(n-1)+F(n-4).

#3

But why its sum is equal to f(n) unable to understand it??

#4

Here, Let F(n) denote the number of ways of tiling an n×4 grid.

We begin the tiling at the left end. We have two possibilities:

  • We place a tile vertically. This leaves an (n-1)×4 grid, that can be tiled in F(n-1) ways
  • We place a tile horizontally. Then, to complete the tiling, we are forced to place another tile horizontally below (or above) it. This leaves an (n-4)×4 grid, that can be tiled in F(n-4) ways.

Thus, we can express F(n) using the recurrence:
F(n) = F(n-1) + F(n-2)

For the base case we have

F(0) = 1 (if we have no grid, there is only one way to tile it!)
F(1) = 1 (we must place a single tile vertically)
If you are not happy with F(0) as a base case, you can add

F(4) = 2 (place 4 tiles horizontally, or 4 tiles vertically)
Then, we can compute T(k) for any k starting at the base case

F(5) = F(4) + F(1) = 2 + 1 = 3
F(6) = F(5) + F(2) = 3 + 2 = 5
…
…

as this there exist this recurrence relation.

#5

Hey @sanjeetboora Acc to me, F(4) means (4*4) wall. Then there is 1 way to arrange 4 tiles horizontally and 1 way to arrange 4 tiles vertically. So F(4)=2. Please correct me if i am wrong…

#6

That’s totally correct