Por que paradigma funcional é mais lento do que imperativo?

Alguém procurou no Google por que paradigma funcional é mais lento do que imperativo e caiu na página do Walter.

É uma pergunta interessante e a resposta não é muito difícil.

Se você programar recursivamente usando paradigma imperativo, vai ficar ainda mais lento do que funcional.

No paradigma funcional, recursividade é um recurso muito usado, enquanto que no paradigma imperativo é comum o uso de ciclos de repetição condicional – loops – para resolver os problemas por meio de reiteração – apesar de corrente, o uso do estrangeirismo iteração não é correto.

[update 2008-04-23]Eduardo Willians avisou que o dicionário Houaiss data a palavra «iteração» de 1858. Vide comentários abaixo.[/update]

Algoritmos reiterativos são conhecidamente mais eficientes do que algoritmos recursivos. Mesmo a recursão linear, sabidamente rápida, é ligeiramente mais lenta do que seu equivalente reiterativo.

Linguagens funcionais são otimizadas para trabalhar com recursividade, portanto mais eficientes em recursões do que linguagens imperativas, no entanto tal otimização não compensa a diferença de desempenho entre algoritmos recursivo e reiterativo.

No entanto o paradigma funcional não é necessariamente mais lento do que o imperativo para todos os casos.

Em procedimentos que exigem muita álgebra ou inteligência artificial, linguagens funcionais são mais eficientes, especialmente quando se faz a substituição dos algoritmos recursivos por funções fechadas.

Funções fechadas são difíceis de serem definidas, mas extremamente eficientes, muito mais do que reiterações. Combinadas com a otimização para recursividade, o uso de funções fechadas pode tornar o paradigma funcional mais eficiente do que o imperativo para casos específicos.

[]'s
Cacilhas, La Batalema