Connecting strings in a graph is a PSPACE problem
You say that you need to solve this "without Savitch", but what you're doing is (almost) implementing Savitch's proof within your algorithm.

That's perfectly fine, of course, as long as you're aware of that.

As for the space analysis of your algorithm - indeed, you present an exponential-space algorithm, in particular because you keep track of an exponential number of strings.

Consider the following change: in your subroutines (in the recursion), instead of limiting the set of vertices you're allowed to visit, how about limiting the number of steps you're allowed to take?

That is, define the subroutine that takes $&lt;M&gt;,x,z,t$ and checks whether $z$ is reachable from $x$ within $t$ steps, with $t$ encoded in binary.

Then, in the recursion, you can divide $t$ by $2$ at each step, thus obtaining a polynomial recursion depth.

This is, in fact, exactly how we prove Savitch's theorem, so it's no surprise that it works...