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

41

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.

marco-fiset
fonte
10
Caso em questão: muitas linguagens funcionais fazem uso pesado da otimização de chamada de cauda, ​​enquanto muito poucas linguagens de procedimentos fazem isso. Isso significa que a recursão da chamada de cauda é muito mais barata nessas linguagens funcionais.
Joachim Sauer
7
Na verdade, a definição de Haskell que você deu é muito ruim. factorial n = product [1..n]é mais sucinto, mais eficiente e não sobrecarrega a pilha por muito tempo n(e se você precisar de memorização, são necessárias opções totalmente diferentes). producté definido em termos de alguns fold, que é definido recursivamente, mas com extremo cuidado. A recursão é uma solução aceitável na maioria das vezes, mas ainda é fácil fazer errado / abaixo do ideal.
1
@JoachimSauer - Com um pouco de embelezamento, seu comentário seria uma resposta válida.
Mark Booth
Sua edição indica que você não percebeu meu desvio. A definição que você deu é um exemplo perfeito de recursão ruim mesmo em linguagens funcionais . Minha alternativa também é recursiva (embora esteja em uma função de biblioteca) e muito eficiente, apenas como ela se repete faz a diferença. Haskell também é um caso estranho, pois a preguiça quebra as regras usuais (caso em questão: as funções podem sobrecarregar a pilha enquanto são recursivas de cauda e são muito eficientes sem serem recursivas de cauda).
@ delnan: Obrigado pelo esclarecimento! Vou editar a minha edição;)
marco-Fiset

Respostas:

36

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.

tdammers
fonte
2
Para o registro, a eliminação de chamadas não depende de pureza.
Scarfridge
2
@scarfridge: Claro que não. No entanto, quando a pureza é um dado, é muito mais fácil para um compilador reordenar seu código para permitir chamadas finais.
Tdammers 20/05/12
O GCC faz um trabalho de TCO muito melhor que o GHC, porque você não pode fazer o TCO através da criação de uma conversão.
dan_waterworth
18

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.

chrisaycock
fonte
Eu já sei o que é a correspondência de padrões e acho que é um recurso incrível em Haskell que sinto falta nos idiomas que uso!
Marco-fiset 18/05/12
@marcof Meu argumento é que toda a conversa sobre recursão vs iteração não aborda a elegância do seu exemplo de código. É realmente sobre correspondência de padrões versus condicionais. Talvez eu devesse ter colocado isso na minha resposta.
Chrisaycock
Sim, eu também entendi: P
marco-fiset
@chrisaycock: Seria possível ver a iteração como recursão de cauda, ​​na qual todas as variáveis ​​usadas no corpo do loop são argumentos e valores de retorno das chamadas recursivas?
Giorgio
@Giorgio: Sim, faça sua função assumir e retornar uma tupla do mesmo tipo.
precisa saber é o seguinte
5

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.

Telastyn
fonte
1
Re: 1. Os retornos antecipados não têm nada a ver com chamadas de cauda. Você pode retornar mais cedo com uma chamada final e ter o retorno "tardio" também com uma chamada final, e você pode ter uma única expressão simples com a chamada recursiva fora da posição final (consulte a definição fatorial do OP).
@ delnan: Obrigado; é cedo e já faz um bom tempo que não estudei a coisa.
Telastyn 18/05
1

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.

Mert Akcakaya
fonte
5
Haskell está entre as poucas línguas não estritas - toda a família ML (além de algumas derivações de pesquisa que adicionam preguiça), todos os populares Lisps, Erlang etc. são rigorosos. Além disso, o segundo parágrafos parece fora - como você indicar corretamente no primeiro parágrafo, a preguiça não permite recursão infinita (o prelúdio Haskell tem o imensamente útil forever a = a >> forever a, por exemplo).
@deinan: Até onde eu sei, o SML / NJ também oferece avaliação preguiçosa, mas é uma adição ao SML. Eu também queria nomear duas das poucas linguagens funcionais preguiçosas: Miranda e Clean.
Giorgio
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 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)

Steven Evers
fonte
1
(1) Essa otimização só se aplica em casos muito específicos - o exemplo do OP não é esse e muitas outras funções diretas precisam de algum cuidado extra para se tornar recursivas na cauda. (2) A otimização real da chamada de cauda não apenas otimiza as funções recursivas, mas remove o espaço adicional de qualquer chamada que é imediatamente seguida por um retorno.
@ delnan: (1) Sim, é verdade. Na minha 'versão original' dessa resposta, eu tinha mencionado que :( (2) Sim, mas dentro do contexto da pergunta, eu pensei que seria estranho a menção.
Steven Evers
Sim, (2) é apenas uma adição útil (embora indispensável ao estilo de passagem de continuação), as respostas não precisam ser mencionadas.
1

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.

Bruce Ediger
fonte
0

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)))
 )
)
K.Steff
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 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.

Karl Bielefeldt
fonte