Complexity of recursive algorithm

I have an algorithm, and I would like to find out the complexity of it, but there is recursion, and I don't know how to count with recursion. My code is:

public boolean algorithm(int x, int y) {
    if (x == matrixHeight - 1 && matrix1[x][y] == '0') {
        return true;
    } else if (x == 1 && matrix1[x-1][y] == '0') {
        return true;
    } else if (y == matrixWidth - 1 && matrix2[x][y] == '0') {
        return true;
    } else if (y == 1 && matrix2[x][y-1] == '0') {
        return true;
    }
    if (matrix1[x-1][y] == '0' && tempMatrix[x-1][y] == '-'){
        path.push(new int[]{x-1, y});
        tempMatrix[x-1][y] = '+'
        if (!algorithm(x-1, y)) {
            path.pop();
        } else {
            return true;
        }
    }
    if (matrix2[x][y] == '0' && tempMatrix[x][y+1] == '-'){
        path.push(new int[]{x, y+1});
        tempMatrix[x][y+1] = '+';
        if (!algorithm(x, y+1)) {
            path.pop();
        } else {
            return true;
        }
    }
    if (matrix1[x][y] == '0' && tempMatrix[x+1][y] == '-'){
        path.push(new int[]{x+1, y});
        tempMatrix[x+1][y] = '+';
        if (!algorithm(x+1, y)) {
            path.pop();
        } else {
            return true;
        }
    }
    if (matrix2[x][y-1] == '0' && tempMatrix[x][y-1] == '-'){
        path.push(new int[]{x, y-1});
        tempMatrix[x][y-1] = '+';
        if (!algorithm(x, y-1)) {
            path.pop();
        } else {
   开发者_开发知识库         return true;
        }
    }
    return false;
}

• There, x, y are coordinates in matrix.
• matrix1 and matrix2 are two-dimensional arrays that contain '0' or '1'
• tempMatrix is a two-dimensional array that contains '+' or '-'
• path is a Stack
• matrixHeight is matrix1.length
• matrixWidth is matrix[0].length
• N, M is the size of the matrix (constant)

Note: this is maze solver that uses backtrack.

---

For recursion, you need to generate a recurrence relation and solve. See http://en.wikipedia.org/wiki/Recurrence_relation. There is no set way to solve every recurrence relation or even to generate one from an algorithm.

An example is with merge sort. Consider how much work is done at each recursive call. First, there is a constant time division; then two recursive calls are made; then there is a linear time merge. How much work does the recursive call take? Well, each one does the same thing, two recursive calls plus linear merge step. So you need an expression for how deep and wide the tree goes. You know for input size of n, the height of the tree is O(log(n)), and at each step a total of O(n) merge work is done, so therefore O(n log(n)) work is done total.

---

It looks like a depth first maze solver that returns true if you can exit the labyrinth and false otherwise. The complexity is O(lines * columns) because you visit each cell a constant number of times in the worst case.

1 1 1 1
1 0 0 1
0 0 0 1
1 1 1 1

Start at (1, 1). Your algorithm will go up, backtrack, go right, try up again, backtrack, right again, backtrack, then down and so on. For labyrinths constructed like this it looks like your algorithm will spend a lot of time solving them.

In fact, most recursive (depth first to be more accurate) approaches will spend a long time, because it will always be possible to force them to do a maximum number of steps.

Look into the Lee algorithm for a better approach.

---

There is actually a really simple analysis of the complexity of this algorithm.

Each call to algorithm makes zero to four recursive calls to algorithm and does some constant amount of other work. So, if we can bound the number of times that algorithm is called then we know the complexity. Now, note that just before every call to algorithm (except for the first) you change an element of tempMatrix from '-' to '+'. And so, the number of calls to algorithm is bounded by the size of tempMatrix, and the complexity is O(matrixWidth * matrixHeight).

Another approach (that would be more obvious with more meaningfull variable names) is simply noticing that you are doing a depth-first search on the x-y grid. And so each "square" will be visited once.