An alternative to the drunkard’s walk algorithm is a recursive search algorithm. This algorithm begins, from the initial coordinates, by initiating a recursive search. For example, the recursive search might begin by searching to the immediate left, then down, then up, and finally to the right, with each point searched initiating a further recursive search in the same direction until a border is reached or the target is found.
For example, assume a recursive search beginning at point 100,100. The recursive process calls itself, first with the coordinates for the point to the immediate left (99,100). When this first search returns, assuming that the target point has not been found, the next search will be up (100,99), then down (100,101), and then right (101,100).
However, the first search at (99,100) initiates its own searches at (98,100), (99,99), (99,101), and (100,100), which is the same point where the search started. And each of these searches executes its own recursive search.
But since each search is looking for either a border, which terminates further recursion in that branch, or the target point, which also terminates recursion, this algorithm is not infinitely recursive. But, even with finite recursion, the number of active recursions does increase geometrically. Furthermore, each recursion requires its own register values to be pushed on to the stack, and this can very quickly lead to stack overflow. Even if the recursive procedure is very carefully designed, this can still be a problem.
An advantage of this approach is that a well-designed recursive search is absolutely certain to succeed. It will find the target location, even if it must check absolutely every location within a region. But a well-designed recursive search is not necessarily any faster than a drunkard’s walk search, and it consumes considerably more of the system’s resources. At its worst, the drunkard’s walk algorithm is sometimes a bit slower but only rarely and randomly so. In general, the drunkard’s walk algorithm tends to be faster, as well as more efficient in overall usage of system resources and, most important, of CPU time.
Finally, on the basis of simple aesthetics, the drunkard’s walk algorithm is far more satisfying to the soul (the programmer’s, at least, if not the machine’s) than the stolidly pedestrian recursive search. After all, getting there is half the fun, isn’t it?