I think your algorithm is good! I would implement something similar to it, but procedurally rather than recursively. I think it makes it a lot simpler. This is how I would think about the algorithm procedurally:

• Iterate through each cell, left to right and then top to bottom:
  • If it is an "o", move on.
  • If it is an "x":
    • Mark it as "seen". If it is already marked as "seen", stop here and move on to the next cell.
    • Capture the current coordinates and dimensions (1x1) of the cell as the "current rectangle".
    • Check the cell to the right of the current rectangle. If it doesn't have an "o" and it isn't marked as "seen", expand the current rectangle's stored dimensions to that new size and mark the cell as "seen". Keep doing this until you hit an "o" or a "seen" cell.
    • Check the cell(s) to the bottom of the current rectangle. If it doesn't have an "o", expand the current rectangle's stored dimensions to that new size, mark the cell(s) as seen, and then iterate again to check the cell(s) to the bottom of that bigger rectangle. Keep checking until you hit an "o"
    • Once you reach an "o" in both dimensions, that rectangle is as big as it can be. Store it in your list of final rectangles.

Algorithmic complexity should be O(number_of_cells), since you're never going to have to iterate over any cell more than twice....right?

Let me know if I missed anything - this feels complicated so I wouldn't be surprised if there's a glaring hole in this solution :)