Existe alguma coisa que possa ser feita com recursão que não possa ser feita com loops?

123

Há momentos em que o uso de recursão é melhor que o uso de um loop e os horários em que o uso de um loop é melhor do que o uso de recursão. Escolher a opção "certa" pode economizar recursos e / ou resultar em menos linhas de código.

Existe algum caso em que uma tarefa só pode ser feita usando recursão, em vez de um loop?

    
por Pikamander2 22.11.2015 / 05:45
fonte

11 respostas

162

Sim e não. Em última análise, não há nada que a recursão possa calcular que o loop não possa, mas o loop requer muito mais encanamento. Portanto, a única coisa que a recursão pode fazer é que os loops não facilitam algumas tarefas.

Tome andando uma árvore. Andar numa árvore com recursão é estúpido e fácil. É a coisa mais natural do mundo. Andar em uma árvore com loops é muito menos direto. Você precisa manter uma pilha ou alguma outra estrutura de dados para acompanhar o que você fez.

Muitas vezes, a solução recursiva para um problema é mais bonita. Esse é um termo técnico e é importante.

    
por 22.11.2015 / 07:00
fonte
76

Não.

Descendo para os fundamentos muito dos mínimos necessários para calcular, você só precisa ser capaz de fazer um loop (isso por si só não é suficiente, mas sim é um componente necessário). Não importa como .

Qualquer linguagem de programação que possa implementar uma máquina de Turing é chamada de Turing complete . E há muitos idiomas que estão em andamento.

Minha língua favorita no caminho de "isso realmente funciona?" A completude de Turing é a de FRACTRAN , que é Turing completo . Tem uma estrutura de loop e você pode implementar uma máquina de Turing nela. Assim, qualquer coisa que seja computável, pode ser implementada em uma linguagem que não tenha recursão. Portanto, não há nada que a recursão possa dar a você em termos de computabilidade que um loop simples não pode.

Isso realmente se resume a alguns pontos:

  • Tudo o que é computável é computável em uma máquina de Turing
  • Qualquer linguagem que possa implementar uma máquina de Turing (chamada Turing completa), pode computar qualquer coisa que qualquer outra linguagem possa
  • Como existem máquinas de Turing em linguagens que não têm recursão (e há outras que apenas têm recursão quando você entra em algumas das outras), é necessariamente verdade que não há nada que você pode fazer com a recursão que você não pode fazer com um loop (e nada que você possa fazer com um loop que você não pode fazer com a recursão).

Isso não quer dizer que existem algumas classes de problemas que são mais facilmente pensadas com recursão do que com looping, ou com loop ao invés de recursão. No entanto, essas ferramentas também são igualmente poderosas.

E enquanto eu levei isso para o extremo 'esolang' (principalmente porque você pode encontrar coisas que são Turing completas e implementadas de maneiras bastante estranhas), isso não significa que as esolangs sejam de alguma forma opcionais. Há toda uma lista de coisas que são acidentalmente Turing completas incluindo os modelos Magic the Gathering, Sendmail, MediaWiki e o Sistema de tipo Scala. Muitos deles estão longe de ser ideais quando se trata de fazer algo prático, é apenas que você pode calcular qualquer coisa que seja computável usando essas ferramentas.

Essa equivalência pode ser particularmente interessante quando você entra em um tipo particular de recursão conhecido como chamada final .

Se você tem, digamos, um método fatorial escrito como:

int fact(int n) {
    return fact(n, 1);
}

int fact(int n, int accum) {
    if(n == 0) { return 1; }
    if(n == 1) { return accum; }
    return fact(n-1, n * accum);
}

Este tipo de recursão será reescrito como um loop - nenhuma pilha usada. Tais abordagens são de fato mais elegantes e fáceis de entender do que o laço equivalente sendo escrito, mas novamente, para cada chamada recursiva pode haver um laço equivalente escrito e para cada laço pode haver uma chamada recursiva escrita.

Há também momentos em que a conversão do loop simples em uma chamada recursiva de chamada final pode ser complicada e mais difícil de entender.

Se você quer entrar no lado teórico, veja a tese de Church Turing . Você também pode encontrar a tese da igreja no CS.SE para ser útil.

    
por 22.11.2015 / 06:11
fonte
30

Are there any cases where a task can only be done using recursion, rather than a loop?

Você sempre pode transformar algoritmo recursivo em um loop, que usa uma estrutura de dados Last-In-First-Out (pilha AKA) para armazenar estado temporário, porque chamada recursiva é exatamente isso, armazenando estado atual em uma pilha, continuando com o algoritmo, depois restaurando o estado. Portanto, a resposta curta é: Não, não existem casos assim .

No entanto, um argumento pode ser feito para "sim". Vamos dar um exemplo concreto e fácil: mesclar ordenação. Você precisa dividir os dados em duas partes, mesclar as partes e depois combiná-las. Mesmo se você não fizer uma chamada de função de linguagem de programação real para mesclar a ordenação para fazer a mesclagem das partes, você precisará implementar uma funcionalidade que é idêntica a fazer uma chamada de função (empurre o estado para sua pilha, pule para início de loop com diferentes parâmetros de partida, depois pop o estado da sua pilha).

É a recursão, se você implementar a chamada de recursão, como etapas separadas de "push state" e "jump to beginning" e "pop state"? E a resposta para isso é: Não, ainda não é chamado de recursão, é chamado de iteração com pilha explícita (se você quiser usar a terminologia estabelecida).

Note que isso também depende da definição de "tarefa". Se a tarefa é classificar, você pode fazer isso com muitos algoritmos, muitos dos quais não precisam de nenhum tipo de recursão. Se a tarefa é implementar um algoritmo específico, como a merge sort, então a ambigüidade acima se aplica.

Então, vamos considerar a questão, existem tarefas gerais, para as quais existem apenas algoritmos recursivos. Do comentário de @WizardOfMenlo sob a pergunta, a função Ackermann é um exemplo simples disso. Portanto, o conceito de recursão é independente, mesmo que possa ser implementado com uma construção de programa de computador diferente (iteração com pilha explícita).

    
por 22.11.2015 / 14:23
fonte
20

Depende de quão estritamente você define "recursão".

Se exigimos estritamente que envolva a pilha de chamadas (ou qualquer mecanismo para manter o estado do programa usado), então podemos sempre substituí-lo por algo que não o faça. De fato, as linguagens que levam naturalmente ao uso pesado da recursão tendem a ter compiladores que fazem uso pesado da otimização da cauda, então o que você escreve é recursivo, mas o que você executa é iterativo.

Mas vamos considerar um caso em que fazemos uma chamada recursiva e usamos o resultado de uma chamada recursiva para essa chamada recursiva.

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  if (m == 0)
    return  n+1;
  if (n == 0)
    return Ackermann(m - 1, 1);
  else
    return Ackermann(m - 1, Ackermann(m, n - 1));
}

Fazer a primeira chamada recursiva iterativa é fácil:

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
restart:
  if (m == 0)
    return  n+1;
  if (n == 0)
  {
    m--;
    n = 1;
    goto restart;
  }
  else
    return Ackermann(m - 1, Ackermann(m, n - 1));
}

Podemos, então, limpar remover o goto para afastar velociraptors e a sombra de Dijkstra:

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  while(m != 0)
  {
    if (n == 0)
    {
      m--;
      n = 1;
    }
    else
      return Ackermann(m - 1, Ackermann(m, n - 1));
  }
  return  n+1;
}

Mas, para remover as outras chamadas recursivas, teremos que armazenar os valores de algumas chamadas em uma pilha:

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  Stack<BigInteger> stack = new Stack<BigInteger>();
  stack.Push(m);
  while(stack.Count != 0)
  {
    m = stack.Pop();
    if(m == 0)
      n = n + 1;
    else if(n == 0)
    {
      stack.Push(m - 1);
      n = 1;
    }
    else
    {
      stack.Push(m - 1);
      stack.Push(m);
      --n;
    }
  }
  return n;
}

Agora, quando consideramos o código-fonte, certamente transformamos nosso método recursivo em um método iterativo.

Considerando para o que isso foi compilado, transformamos o código que usa a pilha de chamadas para implementar a recursão no código que não faz (e ao fazer isso transformou o código que lançará uma exceção de estouro de pilha para valores até mesmo pequenos no código que vai demorar um tempo muito longo para voltar [ver Como posso evitar que minha função Ackerman transborde a pilha? para algumas otimizações adicionais que realmente retornam para muitas outras entradas possíveis].

Considerando como a recursão é implementada em geral, transformamos o código que usa a pilha de chamadas em um código que usa uma pilha diferente para manter as operações pendentes. Poderíamos, portanto, argumentar que ainda é recursivo, quando considerado nesse nível baixo.

E a esse nível, não existem outras maneiras de contornar isso. Então, se você considerar esse método como recursivo, então, de fato, não podemos fazer nada sem ele. Geralmente, porém, não rotulamos esse código como recursivo. O termo recursão é útil porque abrange um certo conjunto de abordagens e nos dá uma maneira de falar sobre elas, e não estamos mais usando uma delas.

Claro, tudo isso pressupõe que você tenha uma escolha. Há duas linguagens que proíbem chamadas recursivas e idiomas que não possuem as estruturas de loop necessárias para iterar.

    
por 23.11.2015 / 14:13
fonte
9

A resposta clássica é "não", mas permita-me elaborar porque eu acho que "sim" é uma resposta melhor.

Antes de prosseguir, vamos tirar algo do caminho: de uma computabilidade & ponto de vista da complexidade:

  • A resposta é "não" se você tiver permissão para ter uma pilha auxiliar ao fazer um loop.
  • A resposta é "sim" se não for permitido nenhum dado extra ao fazer o loop.

Ok, agora, vamos colocar um pé na terra prática, mantendo o outro pé na terra da teoria.

A pilha de chamadas é uma estrutura controle , enquanto uma pilha manual é uma estrutura data . Controle e dados são não conceitos iguais, mas são equivalentes no sentido em que podem ser reduzidos uns aos outros (ou "emulados" através de um outro) de um ponto de vista computabilidade ou complexidade.

Quando essa distinção pode ser importante? Quando você está trabalhando com ferramentas do mundo real. Aqui está um exemplo:

Digamos que você esteja implementando o N-way mergesort . Você pode ter um loop for que passa por cada um dos segmentos N , chama mergesort separadamente e mescla os resultados.

Como você pode paralelizar isso com o OpenMP?

No reino recursivo, é extremamente simples: basta colocar #pragma omp parallel for em torno do seu loop que vai de 1 a N e pronto. No reino iterativo, você não pode fazer isso. Você precisa gerar threads manualmente e passar os dados apropriados manualmente para que eles saibam o que fazer.

Por outro lado, existem outras ferramentas (como vetorizadores automáticos, por exemplo, #pragma vector ) que funcionam com loops, mas são totalmente inúteis com recursão.

Ponto de ser, só porque você pode provar que os dois paradigmas são equivalentes matematicamente, isso não significa que eles são iguais na prática. Um problema que pode ser trivial para automatizar em um paradigma (digamos, paralelismo de loop) pode ser muito mais difícil de resolver no outro paradigma.

, por exemplo: As ferramentas para um paradigma não são traduzidas automaticamente para outros paradigmas.

Consequentemente, se você precisar de uma ferramenta para resolver um problema, é provável que a ferramenta funcione apenas com um tipo específico de abordagem e, consequentemente, você não conseguirá resolver o problema com uma abordagem diferente, mesmo se puder comprovar matematicamente o problema pode ser resolvido de qualquer forma.

    
por 24.11.2015 / 12:05
fonte
8

Deixando de lado o raciocínio teórico, vamos dar uma olhada em como a recursão e os loops se parecem do ponto de vista de uma máquina (hardware ou virtual). Recursão é uma combinação de fluxo de controle que permite iniciar a execução de algum código e retornar na conclusão (em uma visão simplista quando sinais e exceções são ignorados) e de dados que são passados para esse outro código (argumentos) e que são retornados de isso (resultado). Geralmente não há gerenciamento explícito de memória, no entanto, há alocação implícita de memória stack para salvar endereços de retorno, argumentos, resultados e dados locais intermediários.

Um loop é uma combinação de fluxo de controle e dados locais. Comparando isso à recursão, podemos ver que a quantidade de dados nesse caso é fixa. A única maneira de quebrar essa limitação é usar a memória dinâmica (também conhecida como heap ) que pode ser alocada (e liberada) sempre que necessário.

Para resumir:

  • Caso de recursão = fluxo de controle + pilha (+ pilha)
  • Caso de loop = fluxo de controle + heap

Supondo que a parte de fluxo de controle é razoavelmente poderosa, a única diferença está nos tipos de memória disponíveis. Então, ficamos com 4 casos (o poder de expressividade está listado entre parênteses):

  1. Sem pilha, sem heap: recursão e estruturas dinâmicas são impossíveis. (recursão = loop)
  2. Stack, no heap: a recursão é OK, estruturas dinâmicas são impossíveis. (recursão > loop)
  3. Sem pilha, heap: a recursão é impossível, estruturas dinâmicas são OK. (recursão = loop)
  4. Pilha, heap: recursão e estruturas dinâmicas estão OK. (recursão = loop)

Se as regras do jogo são um pouco mais restritas e a implementação recursiva não é permitida para usar loops, recebemos isso:

  1. Sem pilha, sem heap: recursão e estruturas dinâmicas são impossíveis. (recursão < loop)
  2. Stack, no heap: a recursão é OK, estruturas dinâmicas são impossíveis. (recursão > loop)
  3. Sem pilha, heap: a recursão é impossível, estruturas dinâmicas são OK. (recursão < loop)
  4. Pilha, heap: recursão e estruturas dinâmicas estão OK. (recursão = loop)

A principal diferença com o cenário anterior é que a falta de memória de pilha não permite recursão sem loops para fazer mais etapas durante a execução do que linhas de código.

    
por 22.11.2015 / 11:53
fonte
2

Sim. Existem várias tarefas comuns que são fáceis de realizar usando a recursão, mas impossíveis com apenas loops:

  • Provocando estouro de pilha.
  • Programadores iniciantes totalmente confusos.
  • Criando funções de aparência rápida que, na verdade, são O (n ^ n).
por 24.11.2015 / 07:09
fonte
1

Há uma diferença entre funções recursivas e funções recursivas primitivas. Funções recursivas primitivas são aquelas que são calculadas usando loops, onde a contagem máxima de iteração de cada loop é calculada antes do início da execução do loop. (E "recursivo" aqui não tem nada a ver com o uso da recursão).

Funções recursivas primitivas são estritamente menos poderosas que funções recursivas. Você obteria o mesmo resultado se tomasse funções que usam recursão, onde a profundidade máxima da recursão deve ser calculada antecipadamente.

    
por 22.11.2015 / 14:47
fonte
1

Se você está programando em c ++, e usa c ++ 11, então há uma coisa que tem que ser feita usando recursions: constexpr functions. Mas o padrão limita isso a 512, conforme explicado em esta resposta . Usar loops neste caso não é possível, pois nesse caso a função não pode ser constexpr, mas isso é alterado em c ++ 14.

    
por 25.11.2015 / 11:28
fonte
0
  • Se a chamada recursiva for a primeira ou última declaração (excluindo a verificação de condição) de uma função recursiva, é muito fácil traduzir em uma estrutura em loop.
  • Mas se a função fizer algumas outras coisas antes e depois da chamada recursiva , seria complicado convertê-la em loops.
  • Se a função tiver várias chamadas recursivas, a conversão para o código que estiver usando apenas loops será praticamente impossível. Alguma pilha será necessária para acompanhar os dados. Na recursão, a própria pilha de chamadas funcionará como pilha de dados.
por 27.11.2015 / 07:37
fonte
-6

Concordo com as outras perguntas. Não há nada que você possa fazer com a recursão que você não pode fazer com um loop.

MAS , na minha opinião a recursão pode ser muito perigosa. Primeiro, para alguns, é mais difícil entender o que realmente está acontecendo no código. Segundo, pelo menos para C ++ (Java, não tenho certeza), cada etapa de recursão tem um impacto na memória, porque cada chamada de método causa acumulação de memória e inicialização do cabeçalho de métodos. Desta forma, você pode explodir sua pilha. Simplesmente tente a recursão dos números de Fibonacci com um alto valor de entrada.

    
por 22.11.2015 / 10:42
fonte