Comment by ondras

For me, that would be Eller's algorithm: http://www.neocomputer.org/projects/eller.html

It generates perfect mazes of arbitrary size M*N, using only O(max(M, N)) memory.