Step 1) recursive function to find a better decomposition than the actual solution.
Step 2) recursive function to arrange it. If success we have a new actual solution.

Forget about recursivity, it's nice but time consuming. It can be translated to iterations in a known way.

Reasonable guesses:
a) solution contains one (n+1)/2 and two (n-1)/2
b) located at [0,0], [0,(n+1)/2] and [(n+1)/2,0]

b) implies there is always at least one 1-square, so Step1 skips decompositions without 1-squares.

Only non brute force trick on Step2: squares of identical size to last located (they are tried in decreasing order) only try posterior placements.

Obviously, 1-squares are not tried to be placed: they fit always

So, Step2 is by far THE problem. How do you improve it? Any ideas?