Smarter recursion to compute #tilings of $m \times n$ board with $2 \times 1$ dominoes?
From my answer on math.SE:

If you just used $1\times2$ rectangles, then this is same as finding the number of matchings in the $m \times n$ rectangle graph, and a formula for that has been given by Kastelyn:

$$ \sqrt{\left|\prod_{j=1}^{m}\prod_{k=1}^{n} \left(2 \cos \frac{\pi j}{m+1} + 2i\cos \frac{\pi k}{n+1}\right)\right|}$$

This was done, by mapping the number to the square root of the determinant of a weighted adjacency matrix of the graph.

You can find a nice exposition for the $1\times 2$ case in the first chapter of Kenyon's lecture notes.