The most efficient way to tile a rectangle with squares?

I was writing up a description of the Euclidean algorithm for a set of course notes and was playing around with one geometric intuition for the algorithm that involves tiling an $m \times n$ rectangle with progressively smaller squares, as seen in this animation linked from the Wikipedia article:

I was looking over this animation and was curious whether or not the squares that you would place down in the course of this algorithm necessarily gave the minimum number of squares necessary to cover the entire rectangle.

More formally: suppose that you are given an $m \times n$ rectangle, where $m, n \in \mathbb{N}$ and $m, n > 0$. Your goal is to tile this rectangle with a set of squares such that no two squares overlap. Given $m$ and $n$, what is the most efficient way to place these tiles?

Is the tiling suggested by the Euclidean algorithm (that is, in an $m \times n$ rectangle, with $m \ge n$, always place an $n \times n$ rectangle, then recurse on the remaining rectangle) always optimal? If not, is there are more efficient algorithm for this problem?

I am reasonably sure that the Euclidean approach is correct, but I was having a lot of trouble formalizing the intuition with a proof due to the fact that there are a lot of different crazy ways you can try to place the squares. For example, I'm not sure how to have the proof handle the possibility that squares could be at angles, or could have side lengths in $\mathbb{R} - \mathbb{Q}$.

Thanks!

Recalling Kenyon's work on this, I found these comments in an old MO post

Tiling a rectangle with the fewest squares. Kenyon, Richard J. Combin. Theory Ser. A 76 (1996), no. 2, 272–291. "We show that a square-tiling of a p×q rectangle, where p and q are relatively prime integers, has at least $\log 2p$ squares. If $q>p$ we construct a square-tiling with less than $q/p+C \log p$ squares of integer size, for some universal constant $C.$''

Rectangles as sums of squares. Walters, Mark Discrete Math. 309 (2009), no. 9, 2913–2921. Where precisely this question is discussed and is ascribed to Laczkovich (i.e., the minimum number of squares needed to tile an integer sided rectangle (the squares are not assumed to be integer sided though). Of course you are asking for an efficient algorithm which is a different question ... Kenyon paper does discuss some algorithm(greedy) though. –- Vagabond Nov 2 2010 at 9:18

Euclid doesn't always minimize the number of squares. E.g., with an $8\times9$ rectangle, Euclid says use an 8-square and 8 1-squares, 9 squares in all. But you can do it with a 5, two 4s, a 3, a 2, and two 1s, making 7 squares total. You put the 5 in a corner, then put the 4s in the corners that have room for them; that leaves a $3\times5$ rectangle to fill, which you can do by Euclid.