Tiling recursion size 4*1

#1

#include
using namespace std;
int count(int n)
{
if(n<4)
{
return 1;
}
int c1=count(n-1);
int c2=count(n-4);
return c1+c2;
}
int main() {
int n;
cin>>n;
cout<<count(n)<<endl;
return 0;
}
is my code correct for all test cases?

#2

Hello @AjayRRJ,

Always share your code using online Coding Blocks IDE.
The way you have shared it may introduce many syntax errors to it.
STEPS:

  1. Paste your code at https://ide.codingblocks.com/
  2. Save it there.
  3. Share the URL generated.

Now, coming back to your code:
You have missed a base case i.e. when the board is of the size 4X4.
Then there are two ways of placing tiles:

  1. All horizontally
  2. All vertically

Rest of the code is correct. Here is your modified code:

Hope, this would help.
Give a like if you are satisfied.

1 Like
#3

but without n==2 it gives same correct output i.e 2. thanks

#4

Yes, it will.

Reason:
for n=4:

  1. c1 and c2 both are 1.
    But, for calculating c2, you are passing n as 0.
    Which means either there is no board or the board is already tiled and no space is left.
    So, ideally the value returned should be 0.
    As you cannot tile an already filled board.

  2. But in your case, it is returning 1.
    As n=0 is less than 4.

Hope, you have understood this.
Give a like if you are satisfied.