# 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 '14 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). – orezvani Oct 31 '14 at 10:20
• If it's easy, can you show me? – Dr.Doofus Oct 31 '14 at 13:18
• Google a proof that WHILE-programs (which have no recursion) are Turing-complete. – Raphael Oct 31 '14 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
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}

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).

Suppose, for sake of contradiction, that each call of function is interpreted as queue, and each return of function is interpreted as dequeue. Upon the first dequeue, you will return the result of the original function call, and that result is independent of the results of other calls on the function. However, a recursion is dependent on function calls with "smaller" arguments. Hence we reach a contradiction.

You could just play around with the problem and used a stack for simple recursion problem, such as solving factorial, and it will become clearer.

• This only provides a vague hint that using queues in the same way as stacks won't work. But can we do something else? – Raphael Oct 31 '14 at 9:54
• If we are not restricting to using it the same way as stack, we could just use 2 queues like a single stack and the problem become trivial. – nexolute Oct 31 '14 at 11:41