A little understanding of LISPlike programming makes this sort of task (recursive mkdir()ing in PHP4) much simpler. This version works nicely:
function MakeDirectory($dir, $mode = 0755)
if (is_dir($dir) || @mkdir($dir,$mode)) return TRUE;
if (!MakeDirectory(dirname($dir),$mode)) return FALSE;
How it works: line one attempts to make the directory, and returns TRUE if it works or if it already exists. That's the easy case if the parent directories all exist.
Line two trims off the last directory name using dirname(), and calls MakeDirectory recursively on that shorter directory. If that fails, it returns FALSE, but otherwise we come out of it knowing that the parent directory definitely exists.
Finally, presuming the recursive call worked, once we get to line three we can create the requested directory.
Note the use of @ to suppress warning messages from mkdir.
The beauty of this is that if, say, the great-grandparent directory exists but the grandparent and parent directories don't, the function will simply call itself recursively until it gets high enough up the tree to do some work, then carry on unwinding back until all the new directories have been created.
This is pretty bog-standard recursive programming. Anyone who can't wrap their head around it after a few minutes of concentration should probably try a career in sales.