That's not really what functional programming is about. Functional programming is more about avoiding state and referential transparency. Most programmers do not attempt to do this in mainstream programming languages.
That and everything being an expression that returns a value.
Mainstream languages are slowly moving towards more and more functional concepts. The progress towards referential transparency is slow, but ongoing.
But with partial application and currying you could pass the state in at any point in the program, so all the functions on the inside are pure, while state exists on the edges.
Whether or not the state is hidden is not one of the distinguishing features of functional programming.
Referential transparency and being able to declare certain "values" to be immutable even though there are some mutable values around are. For example, if some code is referentially transparent, putting it into continuation-passing style preserves the referential transparency.
BTW, some say that being able to specify the result that you want rather than needing to specify how those results are computed -- which is sometimes called "declarative programming" -- is what makes functional programming powerful, but I disagree: it is being referentially-transparent (or more precisely, more referentially-transparent that imperative code) and giving the programmer the ability to credibly assert that this or that data structure is immutable, combined with language and library support for working with immutable data structures.
Another distinguishing feature of functional programming: being able to rely on (or hope for) certain compiler optimizations not available in imperative languages. (It is because of this feature that Scheme is considered by some to be a functional language.) Referential transparency might be necessary to make these optimizations tractable.
OOP approach hides state because it uses private variables that might be modified in the body of the function. Yet there is nothing in the type signature that states that this function is not referentially transparent!
Some algorithms are hard to express in pure, strict functional settings. (There's even an impossibility theorem for a few algorithms, but that theorem doesn't apply to pure, lazy languages.) That being said, the worst asymptotic slowdown is logarithmic---because you can always simulate random access memory.
On a more practical side, you have constant factors to worry about, and things like caches. Look at eg Don Stewarts work for how to deal with these in a functional language.
(And, in practice, there's no shame in throwing in the towel and either interfacing with other languages, or even switching to them.)