As linguagens funcionais são melhores na recursão?

TL; DR: As linguagens funcionais lidam melhor com a recursão do que as não-funcionais?

Atualmente, estou lendo o Código Completo 2. Em algum momento do livro, o autor nos adverte sobre recursão. Ele diz que deve ser evitado quando possível e que funções usando recursão são geralmente menos eficazes do que uma solução usando loops. Como exemplo, o autor escreveu uma função Java usando a recursão para calcular o fatorial de um número como esse (pode não ser exatamente o mesmo, pois não tenho o livro comigo no momento):

public int factorial(int x) {
    if (x <= 0)
        return 1;
    else
        return x * factorial(x - 1);
}

Isso é apresentado como uma solução ruim. No entanto, em linguagens funcionais, o uso da recursão costuma ser a maneira preferida de fazer as coisas. Por exemplo, aqui está a função fatorial em Haskell usando recursão:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

E é amplamente aceito como uma boa solução. Como já vi, Haskell usa a recursão com muita frequência, e não vi em nenhum lugar que ela seja desaprovada.

Então, minha pergunta é basicamente:

• As linguagens funcionais lidam melhor com a recursão do que as não funcionais?

EDIT: Estou ciente de que os exemplos que usei não são os melhores para ilustrar minha pergunta. Eu só queria salientar que Haskell (e linguagens funcionais em geral) usa recursão com muito mais frequência do que linguagens não funcionais.

Sim, eles fazem, mas não apenas porque podem , mas porque precisam .

O conceito-chave aqui é pureza : uma função pura é uma função sem efeitos colaterais e sem estado. As linguagens de programação funcional geralmente adotam a pureza por vários motivos, como raciocinar sobre código e evitar dependências não óbvias. Algumas linguagens, principalmente Haskell, chegam ao ponto de permitir apenas código puro; quaisquer efeitos colaterais que um programa possa ter (como executar E / S) são movidos para um tempo de execução não puro, mantendo o próprio idioma puro.

Não ter efeitos colaterais significa que você não pode ter contadores de loop (porque um contador de loop constituiria um estado mutável e modificá-lo seria um efeito colateral); portanto, o mais iterativo que uma linguagem funcional pura pode obter é iterar sobre uma lista ( essa operação é normalmente chamada foreachou map). A recursão, no entanto, é uma correspondência natural com a programação funcional pura - nenhum estado é necessário para repetir, exceto os argumentos da função (somente leitura) e um valor de retorno (somente gravação).

No entanto, não ter efeitos colaterais também significa que a recursão pode ser implementada com mais eficiência, e o compilador pode otimizá-la mais agressivamente. Eu não estudei nenhum desses compiladores em profundidade, mas, tanto quanto posso dizer, os compiladores da maioria das linguagens de programação funcionais realizam otimização de chamada de cauda, ​​e alguns podem até compilar certos tipos de construções recursivas em loops nos bastidores.

Você está comparando recursão versus iteração. Sem a eliminação da chamada de cauda , a iteração é realmente mais eficiente, porque não há chamada de função extra. Além disso, a iteração pode continuar para sempre, enquanto é possível ficar sem espaço na pilha de muitas chamadas de função.

No entanto, a iteração requer alteração de um contador. Isso significa que deve haver uma variável mutável , que é proibida em um ambiente puramente funcional. Portanto, as linguagens funcionais são especialmente projetadas para operar sem a necessidade de iteração, daí as chamadas de função simplificadas.

Mas nada disso explica por que seu exemplo de código é tão elegante. Seu exemplo demonstra uma propriedade diferente, que é a correspondência de padrões . É por isso que a amostra Haskell não possui condicionais explícitos. Em outras palavras, não é a recursão simplificada que torna seu código pequeno; é a correspondência de padrões.

Tecnicamente não, mas praticamente sim.

A recursão é muito mais comum quando você está adotando uma abordagem funcional para o problema. Assim, as linguagens projetadas para usar uma abordagem funcional geralmente incluem recursos que tornam a recursão mais fácil / melhor / menos problemática. Em cima da minha cabeça, existem três comuns:

1. Otimização de chamada de cauda. Conforme apontado por outros pôsteres, as linguagens funcionais geralmente exigem TCO.

2. Avaliação preguiçosa. Haskell (e algumas outras línguas) é avaliado preguiçosamente. Isso atrasa o 'trabalho' real de um método até que seja necessário. Isso tende a levar a estruturas de dados mais recursivas e, por extensão, métodos recursivos para trabalhar com elas.

3. Imutabilidade. A maioria das coisas com as quais você trabalha em linguagens de programação funcional é imutável. Isso facilita a recursão, porque você não precisa se preocupar com o estado dos objetos ao longo do tempo. Você não pode ter um valor alterado abaixo de você, por exemplo. Além disso, muitos idiomas são projetados para detectar funções puras . Como funções puras não têm efeitos colaterais, o compilador tem muito mais liberdade sobre a ordem em que as funções são executadas e outras otimizações.

Nenhuma dessas coisas é realmente específica das linguagens funcionais em comparação com outras, portanto, elas não são simplesmente melhores porque são funcionais. Mas, por serem funcionais, as decisões de design tomadas tenderão a esses recursos porque são mais úteis (e suas desvantagens menos problemáticas) na programação funcional.

Haskell e outras linguagens funcionais geralmente usam avaliação lenta. Esse recurso permite escrever funções recursivas sem fim.

Se você escrever uma função recursiva sem definir um caso base em que a recursão termina, você terá chamadas infinitas para essa função e fluxo de pilha.

Haskell também suporta otimizações de chamadas de função recursivas. Em Java, cada chamada de função seria acumulada e causaria sobrecarga.

Então, sim, as linguagens funcionais lidam melhor com a recursão do que outras.

A única razão técnica que conheço é que algumas linguagens funcionais (e algumas linguagens imperativas, se bem me lembro) têm o que chamamos de otimização de chamada de cauda, que permite que um método recursivo não aumente o tamanho da pilha a cada chamada recursiva (ou seja, a chamada recursiva mais ou menos substitui a chamada atual na pilha).

Observe que essa otimização não funciona em nenhuma chamada recursiva, apenas métodos recursivos de chamada de cauda (ou seja, métodos que não mantêm o estado no momento da chamada recursiva)

Você vai querer ver Garbage Collection is Fast, mas uma pilha é mais rápida , um artigo sobre o que os programadores em C considerariam "heap" para os quadros de pilha no C. compilado. Acredito que o autor tenha mexido com o Gcc para fazer isso. . Não é uma resposta definitiva, mas isso pode ajudá-lo a entender alguns dos problemas com recursão.

A linguagem de programação Alef , que costumava acompanhar o Plano 9 da Bell Labs, tinha uma declaração "tornar-se" (consulte a seção 6.6.4 desta referência ). É uma espécie de otimização explícita da recursão de chamada de cauda. O "mas ele usa pilha de chamadas!" argumento contra recursão poderia ser eliminado.

TL; DR: Sim, eles fazem A
recursão é uma ferramenta essencial na programação funcional e, portanto, muito trabalho foi feito na otimização dessas chamadas. Por exemplo, o R5RS exige (nas especificações!) Que todas as implementações tratem chamadas de recursão não acopladas sem que o programador se preocupe com o estouro de pilha. Para comparação, por padrão, o compilador C não fará nem mesmo uma otimização óbvia de chamada de cauda (tente uma reversão recursiva de uma lista vinculada) e, após algumas chamadas, o programa será encerrado (o compilador será otimizado, se você usar - O2).

Obviamente, em programas que são horrivelmente escritos, como o famoso fibexemplo exponencial, o compilador tem poucas ou nenhuma opção para fazer sua 'mágica'. Portanto, deve-se tomar cuidado para não impedir os esforços do compilador na otimização.

EDIT: Pelo exemplo de fib, quero dizer o seguinte:

(define (fib n)
 (if (< n 3) 1 
  (+ (fib (- n 1)) (fib (- n 2)))
 )
)

Linguagens funcionais são melhores em dois tipos muito específicos de recursão: recursão de cauda e recursão infinita. Eles são tão ruins quanto outros idiomas em outros tipos de recursão, como no seu factorialexemplo.

Isso não quer dizer que não haja algoritmos que funcionem bem com recursão regular nos dois paradigmas. Por exemplo, qualquer coisa que exija uma estrutura de dados semelhante a uma pilha, como uma pesquisa em árvore em profundidade, é mais simples de implementar com recursão.

A recursão surge com mais frequência da programação funcional, mas também é muito usada, especialmente para iniciantes ou em tutoriais para iniciantes, talvez porque a maioria dos iniciantes em programação funcional já tenha usado a recursão antes na programação imperativa. Existem outras construções de programação funcional, como compreensão de lista, funções de ordem superior e outras operações em coleções, que geralmente são muito mais adequadas conceitualmente, por estilo, concisão, eficiência e capacidade de otimizar.

Por exemplo, a sugestão de delnan factorial n = product [1..n]não é apenas mais concisa e fácil de ler, mas também altamente paralelelizável. O mesmo para usar um foldou reducese o seu idioma não tiver um productjá incorporado. A recursão é a solução de último recurso para esse problema. O principal motivo para vê-lo resolvido recursivamente nos tutoriais é como um ponto de partida antes de obter melhores soluções, não como um exemplo de uma prática recomendada.