1

I am trying to solve the following problem:

Given a number n, generate a matrix of size 2^n * 2^n such that respects the following rule:

n = 1 
[ 1 2 ]
[ 3 4 ]

n = 2 
[ 1   2    5  6 ]
[ 3   4    7  8 ]
[ 9  10   13 14 ]
[ 11 12   15 16 ]

Here is my algorithm:

static void generare(int i , int j , int x , int y){
    if(x - i == 1 && y - j == 1)
        {
        mat[i][j] = counter++;
        mat[i][j+1] = counter++;
        mat[i+1][j] = counter++;
        mat[i+1][j+1] = counter++;
        }
    else{
        generare(i,j,x/2,y/2);
        generare(i,y/2+1,x/2,y);
        generare(x/2+1,j,x,y/2);
        generare(x/2+1,y/2+1,x,y);
    }
}

It works for n = 1,2 but when I try any number > 2, it crashes. How can i fix my recursive function?

guymaor86
  • 456
  • 7
  • 20
ivanciprian
  • 83
  • 1
  • 1
  • 10
  • 1. What is `mat`? 2. It crashes with what error/exception? – UnholySheep Nov 27 '16 at 12:26
  • mat is the name of my matrix. The error I get is "java.lang.StackOverflowError". My recursive function ends up in an infinite loop but I do not know what conditions should I add so my function would still do what I want it to do. – ivanciprian Nov 27 '16 at 12:29
  • And how is `mat` defined? Also checking for equality in calculations like these is often a bad idea, instead you should (probably) use `<=`. Also your code does not contain an `n` variable, so how exactly are you calling it? (I'm assuming you are passing the same number for every parameter?) – UnholySheep Nov 27 '16 at 12:46
  • As a recursive algorithm, you didn't told us how the first call is made. We can't be any helpful then. – glee8e Nov 27 '16 at 12:48
  • My bad, mat is ant int[][], and the first call of the recursive function is: generare(1,1,power,power); where power is 2^n – ivanciprian Nov 27 '16 at 12:54
  • You're talking about a https://en.wikipedia.org/wiki/Z-order_curve , right? – Marco13 Nov 27 '16 at 13:50
  • You may not even need recursion, by the way http://stackoverflow.com/questions/12157685/z-order-curve-coordinates – Marco13 Nov 27 '16 at 13:55

1 Answers1

3

First of all I think the way you called the function was incorrect. For me, the code you posted didn't even work for a 4X4 array.I think the recursive function should be called with (0, 0, 2^n, 2^n)

Anyways, the solution is as follows(and I will explain):

private static int[][] mat;
private static int counter = 1;

public static void generare(int i, int j, int x, int y) {
    if (x - i <= 2 && y - j <= 2) {

        mat[i][j] = counter++;
        mat[i][j+1] = counter++;
        mat[i+1][j] = counter++;
        mat[i+1][j+1] = counter++;
    } else {
        generare(i, j, x/2+i/2, y/2+j/2);
        generare(i, j+(y-j)/2, x/2 +i/2, y);
        generare(i+(x-i)/2, j, x, y/2+j/2);
        generare(i+(x-i)/2, j+(y-j)/2, x, y);
    }
}

public static void main(String[] args) {
    int power=3;
    int n =(int) Math.pow(2, power);
    mat = new int[n][n];
    generare(0, 0, n, n);
    for(int i=0;i<n;i++) {
        for(int j=0; j<n; j++){
            System.out.print(mat[i][j] +" ");
        }
        System.out.println();
    }
}

The way i solved it is:

  1. The recursive function should stop when we reached a 2 by 2 array.
  2. If the array is larger than a 2 by 2 array. We should call the function with 4 calls(like you did) but with 4 subarrays. Which is where you got it wrong, just the calculation itself.

It worked for you for n=1,2 because the recursive call happened only once. Once your code ran more than once the calculations were not correct. What I did was drew a 8 by 8 array and tried to use only i,j,x and y to represent the calls. Hope this helps :)

guymaor86
  • 456
  • 7
  • 20