# Recursive methods with stacks

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?

• They don't give any concinving argument. In fact, you don't need either; loops are completely sufficient to computer everyting Turing machines can.
– Raphael
Oct 31, 2014 at 9:54
• 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). Oct 31, 2014 at 10:20
• If it's easy, can you show me? Oct 31, 2014 at 13:18
• Google a proof that WHILE-programs (which have no recursion) are Turing-complete.
– Raphael
Oct 31, 2014 at 13:46

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(#)
deque()                 ; remove it

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}