Of course, it all depends on definitions; in this case things are fuzzy. Functional programming means a lot of things to a lot of people. "Supports higher-order functions" is necessary for pretty much any definition of FP, but it sets a very low bar.
My definition would have to include "supports pure functions idiomatically", which means it must be practical to write the bulk of your programs without side-effects. This is really only possible if you have persistent data structures that can efficiently share structure internally; otherwise avoiding side-effects involves lots of wasteful copying. (See http://technomancy.us/132 for an explanation of persistent data structures.)
Of course, if you asked a Haskell programmer, they would be mortified that you would leave monadic computation out of your definition, so no single definition is going to please everyone.
My definition would have to include "supports pure functions idiomatically", which means it must be practical to write the bulk of your programs without side-effects. This is really only possible if you have persistent data structures that can efficiently share structure internally; otherwise avoiding side-effects involves lots of wasteful copying. (See http://technomancy.us/132 for an explanation of persistent data structures.)
Of course, if you asked a Haskell programmer, they would be mortified that you would leave monadic computation out of your definition, so no single definition is going to please everyone.