Toda recursão pode ser convertida em iteração?

181

Um tópico do reddit trouxe uma pergunta aparentemente interessante:

Funções recursivas de cauda podem ser convertidas trivialmente em funções iterativas. Outros, podem ser transformados usando uma pilha explícita. Toda recursão pode ser transformada em iteração?

O exemplo (contador?) Da postagem é o par:

(define (num-ways x y)
  (case ((= x 0) 1)
        ((= y 0) 1)
        (num-ways2 x y) ))

(define (num-ways2 x y)
  (+ (num-ways (- x 1) y)
     (num-ways x (- y 1))
Tordek
fonte
3
Não vejo como isso é um contra-exemplo. A técnica de pilha funcionará. Não vai ser bonito e não vou escrever, mas é factível. Parece que o akdas reconhece isso no seu link.
Matthew Flaschen
Seu (número de maneiras xy) é apenas (x + y) choosex = (x + y)! / (X! Y!), Que não precisa de recursão.
#
3
Duplicado de: stackoverflow.com/questions/531668
Henk Holterman
Eu diria que a recursão é apenas uma conveniência.
e2-e4

Respostas:

181

Você sempre pode transformar uma função recursiva em iterativa? Sim, absolutamente, e a tese de Church-Turing prova se a memória serve. Em termos leigos, afirma que o que é computável por funções recursivas é computável por um modelo iterativo (como a máquina de Turing) e vice-versa. A tese não diz exatamente como fazer a conversão, mas diz que é definitivamente possível.

Em muitos casos, é fácil converter uma função recursiva. Knuth oferece várias técnicas em "The Art of Computer Programming". E, frequentemente, algo calculado recursivamente pode ser calculado por uma abordagem completamente diferente em menos tempo e espaço. O exemplo clássico disso são os números de Fibonacci ou suas seqüências. Você certamente encontrou esse problema em seu plano de graduação.

Por outro lado, certamente podemos imaginar um sistema de programação tão avançado que trate uma definição recursiva de uma fórmula como um convite para memorizar resultados anteriores, oferecendo assim o benefício de velocidade sem o incômodo de informar ao computador exatamente quais etapas siga no cálculo de uma fórmula com uma definição recursiva. Dijkstra quase certamente imaginou esse sistema. Ele passou muito tempo tentando separar a implementação da semântica de uma linguagem de programação. Por outro lado, suas linguagens de programação não determinísticas e de multiprocessamento estão em uma liga acima do programador profissional praticante.

Na análise final, muitas funções são simplesmente mais fáceis de entender, ler e escrever de forma recursiva. A menos que haja um motivo convincente, você provavelmente não deve (manualmente) converter essas funções em um algoritmo explicitamente iterativo. Seu computador manipulará esse trabalho corretamente.

Eu posso ver uma razão convincente. Suponha que você tenha um sistema de protótipo em uma linguagem de nível super alto, como [ vestindo roupas íntimas de amianto ] Scheme, Lisp, Haskell, OCaml, Perl ou Pascal. Suponha que as condições sejam tais que você precise de uma implementação em C ou Java. (Talvez seja política.) Então você certamente poderia ter algumas funções escritas recursivamente, mas que, traduzidas literalmente, explodiriam seu sistema de tempo de execução. Por exemplo, a recursão infinita da cauda é possível no esquema, mas o mesmo idioma causa um problema para os ambientes C existentes. Outro exemplo é o uso de funções lexicamente aninhadas e escopo estático, que Pascal suporta, mas C não.

Nessas circunstâncias, você pode tentar superar a resistência política ao idioma original. Você pode se reimplementar mal com o Lisp, como na décima lei de Greenspun. Ou você pode apenas encontrar uma abordagem completamente diferente da solução. Mas, de qualquer forma, certamente há um caminho.

Ian
fonte
10
Church-Turing ainda não foi provado?
Liran Orevi 08/07/2009
15
@eyelidlessness: Se você pode implementar A em B, isso significa que B tem pelo menos tanta potência quanto A. Se você não pode executar alguma instrução de A na implementação A de B, não é uma implementação. Se A pode ser implementado em B e B pode ser implementado em A, potência (A)> = potência (B) e potência (B)> = potência (A). A única solução é potência (A) == potência (B).
Tordek 01/01
6
re: 1º parágrafo: Você está falando sobre equivalência de modelos de computação, e não a tese de Church-Turing. A equivalência foi comprovada pelo AFAIR por Church e / ou Turing, mas não é a tese. A tese é um fato experimental de que tudo intuitivamente computável é computável em estrito sentido matemático (por máquinas de Turing / funções recursivas etc.). Poderia ser refutado se, usando leis da física, pudéssemos construir alguns computadores não clássicos, computando algo que as máquinas de Turing não podem fazer (por exemplo, interromper o problema). Enquanto a equivalência é um teorema matemático, e não será refutado.
Sdcvvc
7
Como diabos essa resposta obteve votos positivos? Primeiro, ele mistura a perfeição de Turing com a tese de Church-Turing, e depois faz várias manobras incorretas, mencionando sistemas "avançados" e eliminando a recursão preguiçosa e infinita da cauda (o que você pode fazer em C ou em qualquer idioma completo de Turing porque ... uh. alguém sabe o que significa Turing completo?). Então uma conclusão esperançosa, como se isso fosse uma pergunta sobre Oprah e tudo que você precisa é ser positivo e edificante? Resposta horrível!
Ex0du5
8
E o bs sobre semântica ??? Realmente? Esta é uma pergunta sobre transformações sintáticas e, de alguma maneira, tornou-se uma ótima maneira de nomear Dijkstra e sugerir que você sabe algo sobre o cálculo pi. Deixe-me esclarecer: se olharmos para a semântica denotacional de uma linguagem ou algum outro modelo não terá influência na resposta a essa pergunta. Se a linguagem é assembly ou uma linguagem de modelagem de domínio generativa, nada significa. Trata-se apenas da conclusão de Turing e da transformação de "variáveis ​​de pilha" em "uma pilha de variáveis".
Ex0du5
43

É sempre possível escrever um formulário não recursivo para todas as funções recursivas?

Sim. Uma prova formal simples é mostrar que a recursão µ e um cálculo não recursivo, como o GOTO, são Turing completos. Como todos os cálculos completos de Turing são estritamente equivalentes em seu poder expressivo, todas as funções recursivas podem ser implementadas pelo cálculo não-recursivo de Turing-completo.

Infelizmente, não consigo encontrar uma definição formal boa do GOTO online, então aqui está uma:

Um programa GOTO é uma sequência de comandos P executados em uma máquina de registro, de modo que P seja um dos seguintes:

  • HALT, o que interrompe a execução
  • r = r + 1onde restá algum registro
  • r = r – 1onde restá algum registro
  • GOTO xonde xestá um rótulo
  • IF r ≠ 0 GOTO xonde rexiste qualquer registro e xé um rótulo
  • Um rótulo, seguido por qualquer um dos comandos acima.

No entanto, as conversões entre funções recursivas e não recursivas nem sempre são triviais (exceto pela reimplementação manual irracional da pilha de chamadas).

Para mais informações, consulte esta resposta .

Konrad Rudolph
fonte
Ótima resposta! No entanto, na prática, tenho grande dificuldade em transformar algos recursivos em iterativos. Por exemplo, eu era incapaz até agora de virar a typer monomórfica aqui apresentado community.topcoder.com/... em um algoritmo iterativo
Nils
31

A recursão é implementada como pilhas ou construções semelhantes nos intérpretes ou compiladores reais. Portanto, você certamente pode converter uma função recursiva em uma contraparte iterativa, porque é assim que sempre é feita (se automaticamente) . Você apenas duplicará o trabalho do compilador de maneira ad-hoc e provavelmente de uma maneira muito feia e ineficiente.

Vinko Vrsalovic
fonte
13

Basicamente, sim, em essência o que você acaba fazendo é substituir as chamadas de método (que implicitamente colocam o estado na pilha) em pushs explícitos da pilha para lembrar onde a 'chamada anterior' chegou e depois executar o 'método chamado' em vez de.

Eu imagino que a combinação de um loop, uma pilha e uma máquina de estado possa ser usada para todos os cenários, basicamente simulando as chamadas de método. Se isso será ou não "melhor" (mais rápido ou mais eficiente em algum sentido) não é realmente possível dizer em geral.

jerryjvl
fonte
9
  • O fluxo de execução da função recursiva pode ser representado como uma árvore.

  • A mesma lógica pode ser feita por um loop, que usa uma estrutura de dados para percorrer a árvore.

  • O primeiro percurso de profundidade pode ser feito usando uma pilha, o primeiro percurso de largura pode ser feito usando uma fila.

Então a resposta é sim. Por que: https://stackoverflow.com/a/531721/2128327 .

Qualquer recursão pode ser feita em um único loop? Sim, porque

uma máquina de Turing faz tudo o que faz executando um único loop:

  1. buscar uma instrução,
  2. avalie
  3. ir para 1.
Khaled.K
fonte
7

Sim, usando explicitamente uma pilha (mas a recursão é muito mais agradável de ler, IMHO).

dfa
fonte
17
Eu não diria que é sempre mais agradável de ler. A iteração e a recursão têm seu lugar.
Matthew Flaschen
6

Sim, sempre é possível escrever uma versão não recursiva. A solução trivial é usar uma estrutura de dados da pilha e simular a execução recursiva.

Heinzi
fonte
O que derrota o objetivo se a estrutura de dados da pilha estiver alocada na pilha ou leva muito mais tempo se estiver alocada no heap, não? Isso parece trivial, mas ineficiente para mim.
conradkleinespel
1
@conradk Em alguns casos, é uma coisa prática a fazer se você precisar executar alguma operação recursiva em árvore em um problema que seja suficientemente grande para esgotar a pilha de chamadas; a memória heap é geralmente muito mais abundante.
Jamesdlin 27/12/16
4

Em princípio, é sempre possível remover a recursão e substituí-la pela iteração em uma linguagem que possui um estado infinito, tanto para estruturas de dados quanto para a pilha de chamadas. Essa é uma consequência básica da tese de Church-Turing.

Dada uma linguagem de programação real, a resposta não é tão óbvia. O problema é que é bem possível ter um idioma em que a quantidade de memória que pode ser alocada no programa seja limitada, mas em que a quantidade de pilha de chamadas que pode ser usada seja ilimitada (C de 32 bits em que o endereço das variáveis ​​da pilha não é acessível). Nesse caso, a recursão é mais poderosa simplesmente porque possui mais memória que pode usar; não há memória explicitamente alocável para emular a pilha de chamadas. Para uma discussão detalhada sobre isso, consulte esta discussão .

Zayenz
fonte
2

Todas as funções computáveis ​​podem ser calculadas pelas Máquinas de Turing e, portanto, os sistemas recursivos e as máquinas de Turing (sistemas iterativos) são equivalentes.

JOBBINE
fonte
1

Às vezes, substituir a recursão é muito mais fácil do que isso. A recursão costumava ser a coisa da moda ensinada no CS na década de 90, e muitos desenvolvedores comuns da época pensavam que se você resolvesse algo com recursão, era uma solução melhor. Então eles usariam recursão em vez de voltar para trás para ordem inversa, ou coisas tolas assim. Às vezes, remover a recursão é um tipo simples de exercício "duh, isso era óbvio".

Agora isso é menos problemático, pois a moda mudou para outras tecnologias.

Matthias Wandel
fonte
0

A remoção da recursão é um problema complexo e é viável em circunstâncias bem definidas.

Os casos abaixo estão entre os fáceis:

Nick Dandoulakis
fonte
0

Além da pilha explícita, outro padrão para converter recursão em iteração é com o uso de um trampolim.

Aqui, as funções retornam o resultado final ou um encerramento da chamada de função que, de outra forma, teria sido executada. Então, a função inicial (trampolim) continua invocando os fechamentos retornados até que o resultado final seja alcançado.

Essa abordagem funciona para funções recursivas mutuamente, mas receio que só funcione para chamadas de cauda.

http://en.wikipedia.org/wiki/Trampoline_(computadores)

Chris Vest
fonte
0

Eu diria que sim - uma chamada de função nada mais é do que um goto e uma operação de pilha (grosso modo). Tudo o que você precisa fazer é imitar a pilha criada enquanto invoca funções e fazer algo semelhante ao goto (você pode imitar o gotos com idiomas que não possuem explicitamente essa palavra-chave também).

sfussenegger
fonte
1
Eu acho que o OP está à procura de uma prova ou algo mais substancial
Tim
0

Dê uma olhada nas seguintes entradas na wikipedia, você pode usá-las como ponto de partida para encontrar uma resposta completa à sua pergunta.

Segue um parágrafo que pode lhe dar uma dica sobre por onde começar:

Resolver uma relação de recorrência significa obter uma solução de forma fechada : uma função não recursiva de n.

Veja também o último parágrafo desta entrada .

Alberto Zaccagni
fonte
-1

No entanto, recursão significa que uma função se chamará, quer você goste ou não. Quando as pessoas estão falando sobre se as coisas podem ou não ser feitas sem recursão, elas querem dizer isso e você não pode dizer "não, isso não é verdade, porque eu não concordo com a definição de recursão" como uma declaração válida.

Com isso em mente, praticamente tudo o que você diz não faz sentido. A única outra coisa que você diz que não é bobagem é a ideia de que você não pode imaginar programar sem uma pilha de chamadas. Isso é algo que foi feito há décadas até que o uso de uma pilha de chamadas se tornou popular. As versões antigas do FORTRAN não tinham uma pilha de chamadas e funcionavam muito bem.

A propósito, existem linguagens completas de Turing que implementam apenas a recursão (por exemplo, SML) como um meio de loop. Também existem linguagens completas de Turing que implementam apenas a iteração como um meio de loop (por exemplo, FORTRAN IV). A tese de Church-Turing prova que tudo o que é possível em idiomas somente com recursão pode ser feito em um idioma não recursivo e vica-versa pelo fato de que ambos têm a propriedade de garantir a integridade.

Richard
fonte
-3

Aqui está um algoritmo iterativo:

def howmany(x,y)
  a = {}
  for n in (0..x+y)
    for m in (0..n)
      a[[m,n-m]] = if m==0 or n-m==0 then 1 else a[[m-1,n-m]] + a[[m,n-m-1]] end
    end
  end
  return a[[x,y]]
end
Jules
fonte