Okay, but in doing so, it's not pushing an extra stack frame with each step, but rather just jmping its way along, correct? That's what most people think of as being iterative (or tail-recursive), rather than simply recursive, behaviour, and it can apply equally to a lazy algorithm.
No, you can't simply apply that analysis to lazy algorithms. foldr is not a tail-recursive function in a strict language. However, in a lazy language, foldr may not push O(n) frames on the stack.
The code you are looking at here is NOT tail-recursive. Haskell's implementation of ++, in a strict language, will always push O(n) frames on the stack.
But it IS true that this code is O(1) in stack consumption with Haskell's execution model.
Yes, it can apply. Developing an intuition for when Haskell produces strict code and when the compiler is not smart enough to remove the lazyness, helps tremendously in programming bigger programs. I am still in the process of acquiring said intuition.
