This requires changing the simple, composable functions that you could reuse forever, to complex ones that have to split the work into multiple stages.
Another source of inherent complexity which has nothing to do with the solution of the problem itself, is the handling of the input or runtime issues. Input cannot be guaranteed to be always coherent, and runtime issues may arise while running (user interrupt). At this point, interrupting the computation is easy, but as an user I want maybe:
* know why the function stopped, with a meaning answer (not just a stack trace)
* know the location of the error in the input data
* the possibility to resume the computation
If you've ever programmed functionally, you know how hard is to do something as simple as give meaningful error messages buried into a series of fold/map calls.
Keeping state is a simple (and I would say equally elegant) solution to this recurrent problem. Please consider that I'm saying this from a functional programming perspective (as in: objects as localized state containers not necessarily breaking the purity assumption).
Another issue is that we, as humans, are based on a stateful world. Stateful user interfaces are sometimes more efficient due to the way _we_ work. This can be seen in something as simple as "now select a file", which brings up a dedicated section of stateful code to navigate a tree. As such, you are constantly faced with the problem of keeping state.