Given a matrix return true if it contains the Identity matrix (by recursion)

Question

I need to write recursive static method with given 3 parameters the method will return true if the sub matrix with the size of (int size) which the left corner is mat[x][x] is the identity matrix

picture for example:

It was part of my exam and I barely got any points,this is what i wrote:

public static boolean isIdentity(int[][] mat,int x,int size) {
  if(x > mat.length-1 || x > mat[0].length-1 || size < 0)
         return false;
         
  if(size > 0)
     if(mat[x+1][x] != 0 || mat[x][x+1] != 0 || mat[x][x-1] != 0 || mat[x-1][x] != 0)
         return false;
         
  if(size == 0)
          return true;
         
  if(mat[x][x]== 1)
  {
             
  return(isIdentity(mat,x+1,size-1)); 
             
            
  }
        
  return isIdentity(mat,x+1,size-1);
      
        
    } 

My question:

I didn't use override and regret it, but can I make this work without override?

My thought process was checking the diagonal for 1. If its not 1 return false. If its 1 continue the recursion with x+1(keep moving on the diagonal), and I'm not sure I used the size in the optimal way. what I wrote worked for some tests but got OutOfBoundsException for some values. Can I fix it?

Answer 1

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.