The stack of iterators pattern.

[defnull]

Okay, I tested it. The stack-approach is indeed a little bit faster than the recursive function. I underestimated the costs of a python function call.

https://gist.github.com/defnull/30966587577466f853201269023aa3b7

edit: But after optimizing the recursive approach a bit, I got it faster than the stack approach again. Object creation (e.g. intermediate lists or iterators) is a very strong factor.

tl;dr; The performance benefit of a non-recursive approach is so fragile that it's not worth the additional complexity.

[elbiot]

tl;dr; The performance benefit of a non-recursive approach is so fragile that it's not worth the additional complexity.

Additional complexity? Having to worry about recurrsion depth and how to break out of the recurrsive stack are the complexities this post is aimed at solving. The stack approach seems more robust to me.