Converting recursive to iterative

Question

I'm trying to convert my recursive algorithm to an iterative one for performance improvement purposes as my program is trying to get all paths from a text file that has maze. I know that DP is quicker than iterative but I would love to see the differences between recursive, iterative and DP when it comes to this problem.

I'm wondering if there's a way to convert my algorithm to iterative without using stack.

Here's what I've done so far with my recursion.

    int[][] maze = new int[Integer.valueOf(dimensions[1])]
                         [Integer.valueOf(dimensions[0])];

    int colA = maze[0].length;
    int colB = colA;
    int rowA = 0;
    int rowB = 0;

    for (int i = 0; i < maze.length; i++) {
        String currLine = lines.get(i+1);
        int j = 0;
        for (char c : currLine.toCharArray()) {
            maze[i][j] = c == '*' ? -1 : 0;
            if (c == 'A') {
                maze[i][j] = 1;
                rowA = i;
                colA = j;   
            } else if (c == 'B') {
                maze[i][j] = 2;
                rowB = i;
                colB = j;
            }
            j++;
        }
    }
    return getAllPaths(maze, rowA, colA);
}

private static int getAllPaths(int[][] maze, int i, int j) throws IOException {

    if(maze[i][j] == -1) {
        return 0;
    }

    if(maze[i][j] == 2) {
        return 1;
    }

    return getAllPaths(maze, i+1, j) + getAllPaths(maze, i, j+1);
}

Any tips or suggestions where should I start from here to convert this into an iterative will be greatly appreciated!

Answer 1

Iterative vs recursive will not make a notable performance difference.

What you need to do is make the code memoize, so you don't make the same calculation multiple times.

To illustrate: In a 3x5 matrix, you will walk like this:

X → X → X → X → X
↓   ↓   ↓   ↓   ↓
X → X → X → X → X
↓   ↓   ↓   ↓   ↓
X → X → X → X → X

Replacing the X with the number of times getAllPaths would be called for that coordinate, you get:

1 → 1 → 1 →  1 →  1
↓   ↓   ↓    ↓    ↓
1 → 2 → 3 →  4 →  5
↓   ↓   ↓    ↓    ↓
1 → 3 → 6 → 10 → 15

As you can see, without memoization, coordinate 4,2 is called 15 times. That's very bad for performance. If the result had been saved to it only makes the recursive calls once, you would get much better performance.

I'll leave it to you as an exercise to learn more about memoization, so you can apply it to your code.

---

UPDATE

Quoting Wikipedia:

Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

So, you need to cache the results of calling the method, which means you need a cache of the same size as the maze.

private static int getAllPaths(int[][] maze, int row, int col) {
    int[][] cache = new int[maze.length][maze[0].length];
    for (int i = 0; i < cache.length; i++) {
        Arrays.fill(cache[i], -1);
    }
    return getAllPaths(maze, cache, row, col);
}

private static int getAllPaths(int[][] maze, int[][] cache, int row, int col) {
    // Check cache
    if (cache[row][col] != -1)
        return cache[row][col];

    // Normal logic
    int paths;
    if (maze[row][col] == -1) {
        paths = 0;
    } else if (maze[row][col] == 2) {
        paths = 1;
    } else {
        paths = getAllPaths(maze, cache, row+1, col) + getAllPaths(maze, cache, row, col+1);
    }

    // Save result in cache
    cache[row][col] = paths;

    return paths;
}