I always thought the problem with a "purely" functional view is much more practical: From my limited Haskell experience, I gather that you have to use recursion instead of loops, since loops (and GOTOs) work by iteratively modifying some state, unlike recursion. But humans think in loops. If you look in a cookbook for a recipe, it will almost certainly contain loops and rarely any recursions.
Recursion programs are provably Turing equivalent to WHILE or GOTO programs, but that doesn't mean they are equally natural for our brain to think about. (Not to mention things like tail recursion, which is even less intuitive.)
