Functional languages WTF?

Take a look at this: http://www.fsharp.it/2009/08/26/functional-programming-interview-question/

Now, this is screaming  for an imperative implementation. Doing it in the functional way is not only more difficult, but yields a shittier solution, since the function is not tail recursive, so on large inputs it will result in stack overflow.

I know that in F# you can go on the imperative way too. But there are purely functional languages where you can't. So what is the benefit of using the functional paradigm in this case?

Also if we use local variables and not modifying state outside of our function, how the fuck does that hinder us in parallelism?

So does using recursion everywhere have a real benefit, or is it just unnecessary pretentiousness?

>>9
I'm not sure about F#, but Haskell's IO is pretty simple. You probably wouldn't know it was monadic, if you hadn't been told already. This assumes do notation as opposed to using >>=,etc

>>1
I'd have build up a list of strings tagged with their types instead of building two lists simultaneously, but otherwise my solution would be much the same.