[westurner]

> You still consume memory at the same rate, but now it is a heap-allocated stack that is programmatically controlled, instead of a stack-allocated stack that is automatically controlled

To be precise; with precision:

In C (and IIUC now Python, too), a stack frame is created for each function call (unless tail call optimization is applied by the compiler).

To avoid creating an unnecessary stack frame for each recursive function call, instead create a collections.deque and add traversed nodes to the beginning or end enqueued for processing in a loop within one non-recursive function.

Is Tail Call Optimization faster than collections.deque in a loop in one function scope stack frame?

[noelwelsh]

Yes, that is basically it. A tail call should be the same jump instruction as a loop, but performance really depends on the language implementation and is hard to make general statements about.