Recursive methods with stacks

Question

I'm doing some practice papers for revision for my finals and I came across this question:

"This question is about recursion. A recursive method can always be implemented by an iterative method that uses a stack to keep track of intermediate values. Could the stack be replaced by, for example, a queue? Explain (no explanation means no marks)."

And their answer is: "No, a stack is needed to reuse the results of the recursive calls, which means we need a LIFO (i.e., reversed) order. A stack is perfect since each call can be interpreted as a push and each return as a pop of the result."

Now this is sort of confusing me. Couldn't you also say that a queue is also okay because each call can be interpreted as an append and each return can be interpreted as a serve?

• Raphael: They don't give any concinving argument. In fact, you don't need either; loops are completely sufficient to computer everyting Turing machines can.
• orezvani: It doesn't look like an appropriate exercise! I can easily prove that the answer is yes; You can do the same thing using a single array or list (instead of stack).
• Dr.Doofus: If it's easy, can you show me?
• Raphael: Google a proof that WHILE-programs (which have no recursion) are Turing-complete.

Answer 1

If you are allowed to use one extra variable, then a queue can simulate a stack, so in this model a queue plus a single extra storage location will suffice.

The idea is to represent a stack, say $[\ a\ b\ c\ $(top), as a queue, (tail) $\langle c\ b\ a\rangle$ (head). Then the operation $\mathtt{push(x)}$ would correspond to $\mathtt{enque(x)},ドル so $$ [\ a\ b\ c\quad \stackrel{\mathtt{push(x)}}{\longrightarrow}\quad[\ a\ b\ c\ x $$ would be simulated as $$ \langle\ c\ b\ a \rangle\quad \stackrel{\mathtt{enque(x)}}{\longrightarrow}\quad\langle\ x\ c\ b\ a\ \rangle $$ The $\mathtt{pop()}$ operation is a bit more complicated. We first enqueue a marker, #, and then keep pulling elements off the head of the queue and placing them back on the tail until we come to the marker, indicating that the last element we pulled off corresponds to the top of the stack, so we don’t replace that element on the queue and we finish by removing the marker. In pseudocode, what we do is:

enque(#)
v = head() ; save the head element
deque() ; remove it
while (head() != #)
 enque(v) ; put the element back on the tail
 v = head() ; save the next element
 deque() ; remove it
deque() ; finally, remove the marker

For example, starting with $\langle c\ b\ a\rangle,ドル we'd have $$\begin{align} \langle\ c\ b\ a\ \rangle &\longrightarrow \langle\ \mathtt{\#}\ c\ b\ a\ \rangle \\ &\longrightarrow \langle\ a\ \mathtt{\#}\ c\ b\ \rangle \\ &\longrightarrow \langle\ b\ a\ \mathtt{\#}\ c\ \rangle \\ &\longrightarrow \langle\ b\ a\ \mathtt{\#}\ \rangle \\ &\longrightarrow \langle\ b\ a\ \rangle \end{align}$$

Answer 2

I have no idea what "intermediary values" means.

The stack is used to keep the execution environment of the caller, so that this execution can be resumed when the callee returns. Since the first call to return is the most recent call, the stack LIFO strategy is naturally adapted for that purpose, event though there may be other ways of encoding this behavior (actually one while loop and an infinite tape is enough according to Alan Turing and Alonzo Church).

This is so true that, when the recursive call is the last thing done by the caller (other than returning the result), the recursion can be replaced by an iteration very simply and without a stack. This is a standard "optimization" in compiling code (see Stackoverflow and Wikipedia).