56

Recentemente descobri as famosas (ou não tão famosas assim) Funções Recursivas e achei bem interessante o conceito. Porém ao longo da minha leitura me surgiram algumas dúvidas com relação ao uso de tal.

1ª Qual a vantagem de usarmos uma Função Recursiva? Pois eu não consigo entender a vantagem disto:

<?php
function recursiveFunction($num)
{
    if ($num != 0) {
        echo "O valor é $num. <br>";
        recursiveFunction(--$num);
    }
}
recursiveFunction(10);

sobre isto:

<?php
function recursiveFunction($num)
{
    for ($i = $num; $i != 0; $i--) {
        echo "O valor é $i <br>";
    }
}
recursiveFunction(10);

2ª Como fica o consumo de memória? Pois pelo que eu entendi uma função recursiva é executada dentro de outra função (fazendo então um Laço de Repetição). Dependendo do tamanho do cálculo, o uso de uma função recursiva poderia prejudicar o desempenho da minha aplicação?

3ª Eu devo utilizar uma função recursiva ao invés de um Loop de Repetição comum (e.g. for/while)? Quais seriam as situações ideais para o uso de funções recursivas?

4
  • 2
    @BrunoCosta você notou a tag PHP e por isso não faria sentido falar sobre o que está desejando?
    – Maniero
    Commented 16/12/2016 às 19:32
  • @bigown Notei tarde demais mesmo. Ainda assim, se faz ou nao sentido cabe inteiramente ao autor da resposta. Commented 16/12/2016 às 19:45
  • 1
    @BrunoCosta depois eu colocarei alguma coisa, mas aqui ñ faz sentido :)
    – Maniero
    Commented 16/12/2016 às 19:47
  • Alem dos casos citados nas respostas, em aplicações Desktop(talvez não só nessas), utilizamos recursividade quando perdemos a conexão com os Servidores, Serviços, Base de dados. As vezes com esquema de tentativas/timeout. Commented 22/12/2016 às 10:59

5 Respostas 5

52
+50

Realmente recursão é sobrevalorizada.

Eu percebo que o ensinamento de função recursiva não costuma ser feito do jeito certo (na minha opinião, claro) quando o exemplo sempre usado é para fazer algo que é sequencial e não recursivo. Claro que ele pode ser recursivo, mas recursão vai bem quando você vai explodindo execuções subsequentes usando o mesmo critério. Eu até entendo que simular uma sequência recursivamente é a forma mais simples de ensinar, mas cria o vício de que isso é o que tem de melhor na recursão.

Consumo

Se a linguagem não prover uma otimização o consumo de memória e processamento pode ser muito maior que a versão de laço. Pode causar problemas em tempo de execução, como o estouro de pilha. PHP atual (na data desta resposta) não faz otimização.

Chamadas de função custam caro nos dois vetores analisados. Sem considerar o algoritmo em si cada chamada tem um custo principalmente para preparar o ambiente da função e voltar ao estado original. E para garantir que possa voltar ao estado original recursos da pilha da aplicação vão sendo consumidos.

Note que as linguagens que otimizam transformam a recursão em iteração. Portando a iteração é melhor para o computador. A recursão pode ser melhor para o humano entender, em alguns casos.

Essa otimização é só para eliminar as chamadas e o custo citado acima, não para mudar a forma como o algoritmo é executado.

É importante notar que isso não afeta a complexidade do algoritmo. Ambos são lineares, logarítmicos, exponenciais ou outra forma, de acordo com a necessidade específica do algoritmo, nada tem a ver com o fato de serem recursivos ou iterativos.

É possível fazer otimização manual, como memoização por exemplo. No iterativo é uma ajuda, na recursão pode ser obrigatório e mesmo assim não resolver tudo. Ela é uma forma de evitar que a recursão ocorra ou diminua sua profundidade que pode ser a diferença entre ela funcionar ou não.

Onde é interessante

Funções recursivas são interessantes quando vai executar um algoritmo inerentemente recursivo. Trabalhar em árvores de dados, por exemplo, costuma ser melhor expressado de forma recursiva.

O exemplo da pergunta claramente é pior feito recursivamente. É uma sequência simples que não precisa da complicação da recursão (há quem discorde).

Se não é óbvio que deveria ser recursivo é provável que não deva ser mesmo. O intuito da recursividade é poder fazer algo como você pensa o problema. Quando força a barra está abusando da linguagem para parecer mais inteligente. Se o mecanismo é difícil de entender e não traz uma vantagem clara é melhor não usar. Use quando achar natural. Se estudar bem e estiver ciente da utilidade vai perceber quando deve usar.

A não ser que a linguagem não tenha o recurso do laço a recursão só deve ser usada quando claramente vai deixar o código mais legível para todos, não apenas os acadêmicos que costumam preferir a recursão. Principalmente em linguagens que não possuem otimização.

Mais informações

Não vou entrar em detalhes porque quase tudo já foi respondido em pergunta que eu já fiz sobre o assunto. Embora a resposta do utluiz lá responda mais diretamente à questão considero mais interessante a resposta do mgibsonbr para o contexto aqui.

Coloquei no GitHub para referência futura.

27

TL;DR

Todo código recursivo pode ser traduzida numa forma iterativa, porém alguns algoritmos são naturalmente recursivos e mais facilmente representados desta forma.

Pense, por exemplo, em percorrer todos os nós de uma árvore ou grafo, processar todos os arquivos de um diretório e subdiretórios e assim por diante.

No modo iterativo você é responsável por gerenciar manualmente o estado de cada etapa do algoritmo usando alguma estrutura de dados, muitas vezes uma pilha, enquanto no modo recursivo você delega esta função à sua linguagem de programação, ao fazer uso de variáveis e parâmetros que são automaticamente alocadas na pilha de execução no início de cada execução do método método.

Exemplo

Para responder às perguntas, considere algo um pouquinho mais complexo. Extraí o pseudo-código para percorrer árvores da Wikipédia.

Método recursivo

postorder(node)
  if node == null then return
  postorder(node.left)
  postorder(node.right)
  visit(node)

Método iterativo

iterativePostorder(node)
  parentStack = empty stack  
  lastnodevisited = null 
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null)
      parentStack.push(node)
      node = node.left
    else
      peeknode = parentStack.peek()
      if (peeknode.right ≠ null and lastnodevisited ≠ peeknode.right) 
        node = peeknode.right
      else
        visit(peeknode)
        lastnodevisited = parentStack.pop() 

Respostas

1ª Qual a vantagem de usarmos uma Função Recursiva?

No seu exemplo há pouca vantagem, mas no que coloquei acima, vemos claramente que o método recursivo:

  • Expressa melhor a funcionalidade. Programação funcionar faz tudo pesado desse dessa capacidade.
  • É mais compacto. Menos código significa manutenção mais fácil, menor possibilidade de erros e assim por diante.
  • Gerenciamento automático do estado. No exemplo iterativo foi usada uma pilha (stack). Pense agora em linguagens onde o gerenciamento de memória não é automático. Em C, por exemplo, você teria que adicionar código para alocar e liberar elementos da pilha em cada iteração.

2ª Como fica o consumo de memória?

Depende da função. Geralmente você deveria fazer uma análise de complexidade de memória e tempo para analisar as diferenças, mas é um tanto óbvio que, na grande maioria dos casos, as rotinas recursivas consomem mais memória e necessitam de mais ciclos de execução.

Rotinas recursivas geralmente usam mais memória por realocar as variáveis a cada chamada recursiva, mas rotinas iterativas podem usar a mesma quantidade de memória se os valores forem salvos em listas ou pilhas, por exemplo.

No modo iterativo você tem o controle, para o bem ou para o mal. Existe a possibilidade de criar uma rotina mais otimizada que a versão recursiva. Mas não se deve tomar isso como uma regra, afinal existem excelentes implementações recursivas que são mais eficientes do que a média das implementações iterativas.

Além disso, a eficiência depende grandemente do número de execuções e do nível de recursão. Assim como rotinas de ordenação, algumas implementações funcionam melhor quando há poucas iterações e outras quando há mais iterações. Algumas implementações recursivas são melhores para processamentos pequenos. Veja, por exemplo, neste site que o desempenho para o Fibonacci onde n <= 5 foi melhor para a versão recursiva.

Num exemplo bem simples, a função recursiva de Fibonacci tem complexidade exponencial enquanto a versão pode ser implementada com duas ou três variáveis simples e, portanto, tem uso de memória constante.

Por outro lado, quase sempre as rotinas recursivas acabam precisando ser reescritas em sua versão iterativa quando o número de elementos ou números processados é grande, afinal a recursividade tem um limite sensível tanto de memória quanto de empilhamento de dados.

E além de tudo isso, existem técnicas que podem melhoram o desempenho e a capacidade das rotinas recursivas, sendo exemplos disso:

3ª Eu devo utilizar uma função recursiva ao invés de um Loop de Repetição comum (e.g. for/while)? Quais seriam as situações ideais para o uso de funções recursivas?

Deve apenas se o algoritmo for melhor expresso recursivamente e se o uso geral daquele algoritmo não vai exceder os limites de recursividade.

Acredito que as situações ideais tenham sido exemplificadas acima, isto é:

  • Algoritmos inerentemente recursivos, melhor expressos neste formato
  • Uso computacional é moderado, de modo a não exceder os limites de recursão
1
  • 1
    +1, Parecia meu professor de Estrutura de dados falando, só faltou dizer "Então implementa essa arvore Red Black sem recursividade" hauhauah Commented 11/01/2016 às 12:34
12
  1. Funções recursivas são uma vantagem para casos em que o problema seja naturalmente definido em função de si mesmo, e em que a solução recursiva seja a mais simples. No início isso pode parecer estranho já que recursão parece complicada e confusa, mas com o tempo e com o entendimento (muita prática também) você aprende a identificar problemas em que ela é a melhor solução.
  2. Geralmente recursão representa um gasto adicional de memória, isso ocorre pois cada chamada de uma função aloca um quadro na Pilha de chamada, sendo assim cada nova invocação que a função recursiva faz a si própria aloca um novo quadro na pilha e cada novo quadro acumula mais memória, toda essa memória só é libereda quando todas as chamdas recursivas alcançam o ponto de parada (quando $num for == 0 no seu exemplo). Caso a função recursiva faça chamadas demais a si mesma (acumule "quadros" demais na pilha) vai ocorrer um "Stack Overflow" (estouro de pilha). Recomendo que você leia esta pergunta e as respostas fornecidas caso queira uma maior compreensão sobre o que é a pilha de chamada e como um stack overflow pode ocorrer.
  3. Como a vida é difícil a resposta é, depende. Como já comentei antes a vantagem de recursão é para problemas recursivos por natureza e para os quais uma solução recursiva seja a mais simples e direta, um exemplo clássico é a manipulação de Árvores binárias, uma estrutura de dados inerentemente recursiva. Minha sugestão final é: aprenda recursão, entenda como funciona, pratique, eventualmente você vai saber a melhor hora de usar.
5

Quem não experimenta na prática acaba não entendendo a teoria. Então é sempre bom mostrar um exemplo prático de uso no "mundo real".

Uma dica básica para saber quando implantar é, quando precisa executar vários laços de repetição de número variável.

Quando você tiver certeza que pode resolver algo com X número de laços de repetição, então é lógico que o mais sensato é aplicar múltiplos laços, desde que não sejam muitos. Por exemplo, 10 laços é muita coisa então seria o caso de se pensar no uso de recursividade.

Imagine

while(){
    while(){
        while(){
            while(){
                while(){
                    while(){
                        while(){
                            while(){
                                while(){
                                    while(){

Como isso ficaria numa recursividade?

function foo()
    while(){
       foo();

Abaixo, um exemplo prático de uso.

Nessa situação precisei criar uma função para normalizar um path (filesystem). No PHP existe a função realpath() porém, essa função normaliza somente um path existente. A função abaixo faz o mesmo que realpath() com a diferença de que ignora se o path existe ou não. A finalidade é apenas normalizar.

Isso é um exemplo prático de uso de recursividade. Aqui nesse caso não caberia usar múltiplos laços manualmente.

$path_canonicalize = function($str, $started = false) use(&$path_canonicalize)
{
    $str = str_replace('/', DIRECTORY_SEPARATOR, $str).DIRECTORY_SEPARATOR;

    if (!$started)
        $str = preg_replace("/".preg_quote(DIRECTORY_SEPARATOR, "'".DIRECTORY_SEPARATOR."'")."{2,}/", DIRECTORY_SEPARATOR, $str);

    $pos = strpos($str, '..'.DIRECTORY_SEPARATOR);
    if ($pos !== false)
    {
        $part = trim(substr($str, 0, $pos), DIRECTORY_SEPARATOR);
        $str = $path_canonicalize(trim(substr($part, 0, strrpos($part, DIRECTORY_SEPARATOR)), DIRECTORY_SEPARATOR).DIRECTORY_SEPARATOR.trim(substr($str, $pos+3), DIRECTORY_SEPARATOR), true);
    }
    return rtrim($str, DIRECTORY_SEPARATOR);
};

/*
Try those cases to check the consistency:
$str = __DIR__.'/template//////../header//..';
$str = __DIR__.'/template///..///../header//..';
$str = __DIR__.'/template/../header/..';
$str = __DIR__.'/template/../header/../';
$str = __DIR__.'/template/../header/..//';
$str = __DIR__.'/template/../header/..///';
$str = __DIR__.'/template/../header/..///..';
$str = __DIR__.'/template/../header/..///../';
$str = __DIR__.'/template\\..\\header\\..';
*/
$str = __DIR__.'/template/../header/..///..//';
echo 'original: '.$str.PHP_EOL;
echo 'normalized: '.$path_canonicalize($str).PHP_EOL;
3
  • 1
    Parece que sua resposta se desviou do caminho em certo ponto, focando demais no problema específico que você resolveu. Eu entendo que ele sirva como exemplo, mas talvez os iniciantes se percam aí. Pode ser o motivo dos votos negativos que a resposta recebeu.
    – bfavaretto
    Commented 12/01/2016 às 1:19
  • Percebi, @bfavaretto. Não tem problema. Quem tem bom senso sabe discernir as coisas. Commented 12/01/2016 às 6:32
  • votei +1 porque a resposta é útil sim, o exemplo prático é horrível para quem é iniciante, mas a explicação já deixa claro que há um ponto importante na recursividade que é a iteração que pode variar dependendo dos parâmetros iniciais Commented 21/12/2016 às 18:40
1

Além do que foi dito nas outras respostas, funções recursivas são especialmente vantajosas em casos onde é possível dividir o problema pela metade. Isso fica evidente ao trabalhar com árvores binárias, mas não está limitado a isso.

Considere as duas funções abaixo para calcular a multiplicação a partir de sucessivas somas. Enquanto a solução iterativa tem complexidade O(n), a solução recursiva tem complexidade O(log(n)). Isso deve compensar a sobrecarga para chamada de métodos.

Desculpe pelo código em Python, era a linguagem que eu tava trabalhando, mas acho que dá pra expressar o conceito. Se tiver tempo mais tarde, posso tentar traduzir pra PHP.

def multIterativa(a, b):
    total = 0
    for i in range(b):
        total += a
    return total

def multRecursiva(a, b):    
    if b == 0:
        return 0
    if b == 1:
        return a
    total = multRecursiva(a, int(b / 2))
    total += total
    if b % 2 != 0:
        total += a
    return total

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .