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

39

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 alerta sobre a recursão. Ele diz que isso deve ser evitado sempre que possível e que as funções que usam a recursão geralmente são menos eficazes que uma solução usando loops. Como exemplo, o autor escreveu uma função Java usando recursão para calcular o fatorial de um número assim (pode não ser exatamente o mesmo, já que eu 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 eu já vi, Haskell usa recursão com muita freqüência, e eu não vi em nenhum lugar que é desaprovado.

Então, minha pergunta é basicamente:

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

EDIT: Estou ciente de que os exemplos que usei não são os melhores para ilustrar a 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.

    
por marco-fiset 18.05.2012 / 14:41
fonte

8 respostas

35

Sim, eles fazem, mas não só porque eles 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, mais notavelmente Haskell, chegam ao ponto de permitir somente 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 a própria linguagem pura.

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

No entanto, não ter efeitos colaterais significa que a recursão pode ser implementada de maneira mais eficiente, e o compilador pode otimizá-la de forma mais agressiva. Eu não estudei nenhum desses compiladores em profundidade, mas, até onde eu sei, a maioria dos compiladores de linguagens de programação funcionais executam a otimização de chamada final, e alguns podem até compilar certos tipos de construções recursivas em loops nos bastidores.

    
por 18.05.2012 / 17:09
fonte
18

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

No entanto, a iteração requer a alteração de um contador. Isso significa que deve haver uma variável mutável , que é proibida em uma configuração 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 sua amostra de código é tão elegante. Seu exemplo demonstra uma propriedade diferente, que é correspondência de padrões . É por isso que o exemplo 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.

    
por 18.05.2012 / 15:05
fonte
5

Tecnicamente não, mas praticamente sim.

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

  1. Otimização de chamada de cauda. Como apontado por outros cartazes, os idiomas funcionais geralmente exigem TCO.

  2. Preguiçoso Avaliação. Haskell (e alguns outros idiomas) é 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 nelas.

  3. Imutabilidade. A maioria das coisas com as quais você trabalha em linguagens de programação funcionais é imutável. Isso torna a recursão mais fácil porque você não precisa se preocupar com o estado dos objetos ao longo do tempo. Você não pode ter um valor alterado por baixo de você, por exemplo. Além disso, muitos idiomas são projetados para detectar funções puras . Como as 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 para linguagens funcionais versus outras, então elas não são simplesmente melhores porque são funcionais. Mas como elas são funcionais, as decisões de design feitas tenderão para esses recursos porque são mais úteis (e suas desvantagens menos problemáticas) ao programar funcionalmente.

    
por 18.05.2012 / 15:13
fonte
1

Haskell e outras linguagens funcionais geralmente usam avaliação preguiçosa. Este recurso permite que você escreva funções recursivas não finais.

Se você escrever uma função recursiva sem definir um caso base no qual a recursão termina, você acaba tendo chamadas infinitas para essa função e para o stackoverflow.

O Haskell também suporta otimizações de chamadas de função recursivas. Em Java, cada chamada de função empilhava e causava sobrecarga.

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

    
por 18.05.2012 / 14:59
fonte
1

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 é chamado Otimização de chamada final que permite que um método recursivo não aumente o tamanho da pilha com cada chamada recursiva (ou seja, a chamada recursiva mais ou menos substitui a chamada atual na pilha).

Note que esta otimização não funciona em qualquer chamada recursiva qualquer, somente os métodos recursivos tail-call (ou seja, métodos que não mantêm estado no momento da chamada recursiva)

    
por 18.05.2012 / 14:54
fonte
1

Você vai querer olhar para Coleta de lixo é rápida, mas uma pilha é mais rápida , um artigo sobre usando o que os programadores C pensariam como "heap" para os quadros de pilha no C. compilado Acredito que o autor mexeu com o Gcc para fazer isso. Não é uma resposta definitiva, mas isso pode ajudá-lo a entender alguns dos problemas com a recursão.

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

    
por 18.05.2012 / 18:49
fonte
0

TL; DR: Sim, eles fazem
A recursão é uma ferramenta fundamental na programação funcional e, portanto, muito trabalho foi feito para otimizar essas chamadas. Por exemplo, o R5RS requer (na especificação!) Que todas as implementações lidem com chamadas de recursividade de cauda não conectadas 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 óbvia otimização de cauda (tente uma reversão recursiva de uma lista encadeada) e após algumas chamadas, o programa terminará (O compilador otimizará, no entanto, se você usar - O2).

Naturalmente, em programas que são terrivelmente escritos, como o famoso exemplo de fib que é exponencial, o compilador tem pouca ou nenhuma opção para fazer sua 'mágica'. Portanto, deve-se tomar cuidado para não prejudicar os esforços do compilador na otimização.

EDIT: Pelo exemplo fib, quero dizer o seguinte:

(define (fib n)
 (if (< n 3) 1 
  (+ (fib (- n 1)) (fib (- n 2)))
 )
)
    
por 18.05.2012 / 14:55
fonte
0

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 o seu factorial example.

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

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

Por exemplo, a sugestão de delnan de factorial n = product [1..n] não é apenas mais concisa e mais fácil de ler, também é altamente paralelizável. O mesmo vale para usar um fold ou reduce se seu idioma não tiver um product já incorporado. A recursão é a solução de último recurso para esse problema. A principal razão pela qual você vê isso resolvido recursivamente nos tutoriais é como um ponto de partida antes de chegar a soluções melhores, não como um exemplo de uma melhor prática.

    
por 28.08.2014 / 15:18
fonte