Last week, I posed a problem: Given 2ⁿ points, each of which might be connected to any of the others, figure out if there is a path between two given points using no more than O(n) space, measured in n-bit words.

One reader claimed that recursion could not be used to solve this problem, because that would use more than O(n) space. However, this claim is not true if the recursion depth is limited to n, and each recursive call uses no more than a constant number of n-bit integers. What is true is that the common form of recursion, in which each call reduces the size of the problem by 1, is ruled out by the space constraints.

With this in mind, let's see if we can figure out how to solve the problem of determining whether there is a path from point

p to point q. Note that we cannot even store the path if there is one, because it might be longer than n elements; so we are limited to figuring out whether a path exists.

Our first observation is that if a path exists at all, then there must be a path with no more than 2ⁿ-1 steps. The reason is that there are only 2ⁿ distinct points, so any path with 2ⁿ or more steps must visit at least one point more than once. Moreover, the maximum length of the path gives a value that we can use to control recursion.

We can therefore revise our problem slightly: Instead of determining whether there is a path from p to q, we will try to determine whether there is a path from p to q that contains no more than k steps. We will use the notation path(p, q, k) to represent a function that determines whether there is a path from p to q with no more than k steps. Our original problem then becomes a call to path(p, q, 2n-1).

We can tackle the easy cases first. path(p, q, 0) is true if and only if p and q are the same point; path(p, q, 1) is true if path(p, q, 0) is true or there is a direct connection from p to q. Now we have to consider the more general case.

The usual way to solve a problem of this sort recursively is to look for a solution with a smaller value of k. In this case, we have already determined that we cannot use k-1 as the value for the recursive call, because that will cause a recursion depth of k, which will be greater than n. The next logical value to try is k/2. What would that value mean? It would mean that we are trying to get from p to q by getting halfway there (recursively), then getting the rest of the way there (also recursively). Dividing the problem in half this way is a promising approach, because it would limit the recursion depth to log₂(k), which, of course, is n.

So we can now reformulate the problem: path(p, q, k) is true if and only if there exists a point r such that

• There exists a path with no more than k/2 steps from p to r — i.e., path(p, r, k/2) is true.
• There exists a path with no more than k-(k/2) steps from r to q — i.e., path(r, q, k-(k/2)) is true.