# recursion – Can we rule out space usage of inputs of the recursive calls in space complexity of an Algorithm?

In Sipser ToC 3rd edt. (2012), Chapter 8 (Space complexity), Theorem 8.14 (p. 345), there is a Problem called GG:

$$GG={langle G,b rangle |$$Player $$I$$ has a winning strategy for the generalized geography played on graph $$G$$ starting at node $$b}$$

PROOF IDEA A recursive algorithm similar to the one used for $$TQBF$$ in Theorem 8.9 determines which player has a winning strategy.

The following algorithm decide whether Player $$I$$ has a winning strategy in instances of generalized geography … it runs in polynomial space.

$$M$$= “On input $$langle G,b rangle$$, where $$G$$ is a directed graph and $$b$$ is a node of $$G$$
1. If $$b$$ has outdegree $$0$$, $$textit{reject}$$ because Player $$I$$ loses immediately.
2. Remove node $$b$$ and all connected arrows to get a new graph $$G’$$.
3.For each of the nodes $$b_1,b_2,dots b_k$$ that $$b$$ originally pointed at, recursively call $$M$$ on $$langle G’,b_i rangle$$.
4. If all these accept, Player $$II$$ has a winning strategy in the original game, so $$textit{reject}$$. Otherwise, Playrr $$II$$ doesn’t have a winning strategy, so Player $$I$$ must; therefore, $$textit{accept}$$.”

The only space required by this algorithm is for storing recursion stack.

… the algorithm runs in linear space.

I could not understand how we can rule out the space for the inputs of recursion calls.

My question is, suppose work tape is sepersted from read-only input tape. For each recursive call $$M(langle G’,b_i rangle)$$ with $$G’ subset G$$ how we can distinguish $$G’$$ from $$G$$ without extra space ? Because the original input is $$langle G,b rangle$$ Unless we can fork unlimited instance of $$M$$ with seperated input tape, which is very odd, because in that way we have several Turing Machines which runs independently on the new input and pass the result to the Turing Machane which called them!

I calcuate the space usage $$n^2$$, not linear, but quadratic. Because i guess in every level of recursion we need at least $$O(n)$$ space in order to distinguish every subgraph $$G’$$ from $$G$$. Because we need to store $$G’$$ some how and we can not rely just on the original input tape.

If I missunderstood something, please clearify it for me.

Posted on Categories Articles