First not using @Override
is fine!
If there was no interface. Also @Override
is used if somewhere there was a method isIdentity
given. And with a static
method, a stand-alone function there cannot be an override.
An other remark, for the real life: follow conventions, use spaces and braces, and indentions of 4 spaces. If you have got hundred sources, are customized typing in one convention, the hundred and first source cannot be different. You will be irritated if that source comes from your new colleague.
Validation
Where you immediately went wrong is to validate the input.
Recursion checks the input on the simple case(s) and then does the recursion on the remaining difficult but smaller problem.
Add validation, check on the input parameters, best in a non-recursive function calling the recursive one.
Or do it at the end. This is a practical tip, as thinking on validation takes some effort. And here validation is much:
- mat.length != 0, mat[0].length != 0
- size >= 0, x >= 0, x <= mat.length, x <= mat[0].length
- x + size <= mat.length, x + size <= mat[0].length
You were not perfect on the input validation, but let's take a look at the real algorithm.
The algorithm they probably desired
Without validation.
public static boolean isIdentity(int[][] mat, int x, int size) {
if (size == 0) {
return true; // A matter of definition, false?
}
if (mat[x][x] != 1) {
return false;
}
for (int i = 1; i < size; ++i) {
if (mat[x][x + i] != 0 || mat[x + i][x] != 0) {
return false;
}
}
return size == 1 || isIdentity(mat, x + 1, size - 1);
}
The above checks
1000..
0xxx..
0xxx..
0xxx..
:.....
Where xxx is left to the recursion.
For 1 the check is simple.
For the zeros it went wrong.
You only did [x±1][x] and [x][x±1] which is wrong. I needed a for loop, from 1 upto size - 1.
The recursion is linear, moving one step on the diagon as you did. But only one single recursive call needed.
Here one could have done the last return as
if (size == 1) {
return true;
}
return isIdentity(mat, x + 1, size - 1);
Evaluation
Your algorithm did neither have an easy and full validation as far as I can see.
In general not so problematic.
Your algorithm however contains errors, and just on the recursion relevant code.
Loop holes, code lawyer
If one of the requirements was not to use loops, like the for above,
one would have needed an extra parameter (i
).
Tips
- Input validation can become verbose, especially in the 2 dimensions of matrices.
Doing it later, gives to you a head start, and prevents thinking stress.
However do it early when it is a no-brainer. Then it may help.
- Make it depictable, clear, my
1000..
etcetera helps.
- Then it is a bit of seeing where
if (size == 1)
is applicated, here late,
as the checks on the zeros is independent on the size, and must be done always.
- Keep it simple.