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

Question

A reddit fio trouxe uma pergunta aparentemente interessante:

funções recursivas cauda pode trivialmente ser convertidas em funções interativas. Outros, pode ser transformada usando uma pilha explícita. Podem todas recursão ser transformado em iteração?

A (? Contador) exemplo no post é 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))

Answer 1

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

Em muitos casos, a conversão de uma função recursiva é fácil. Knuth oferece várias técnicas em "The Art of Computer Programming". E, muitas vezes, uma coisa calculado de forma recursiva pode ser calculado por uma abordagem completamente diferente em menos tempo e espaço. O exemplo clássico é o número de Fibonacci ou sequências destes. Certamente você já encontrou este problema em seu plano de grau.

Por outro lado desta moeda, certamente podemos imaginar um sistema de programação tão avançada como para tratar uma definição recursiva de uma fórmula como um convite para memoize resultados anteriores, oferecendo assim o benefício de velocidade sem a necessidade de dizer ao computador exatamente quais os passos a seguir no cálculo de uma fórmula com uma definição recursiva. Dijkstra quase certamente fez imaginar tal sistema a. Ele passou muito tempo tentando separar a implementação da semântica de uma linguagem de programação. Então, novamente, suas não-determinísticos e multiprocessamento linguagens de programação estão em uma liga acima do programador profissional praticando.

Em última análise, muitas funções são simplesmente mais fácil de entender, ler e escrever em forma recursiva. A menos que haja uma razão convincente, você provavelmente não deveria (manualmente) converter estas funções para um algoritmo explicitamente iterativo. O seu computador vai lidar com esse trabalho corretamente.

Eu posso ver uma razão convincente. Suponha que você tem um protótipo de sistema em uma linguagem de nível super-alta como [ vestindo roupas íntimas de amianto ] Scheme, Lisp, Haskell, OCaml, Perl, ou Pascal. condições Suponha que são tais que você precisa de uma implementação em C ou Java. (Talvez seja política.) Em seguida, você poderia certamente ter algumas funções escritas de forma recursiva, mas que, traduzido literalmente, iria explodir o seu sistema de execução. Por exemplo, infinito recursão cauda é possível no Esquema, mas o mesmo idioma causa um problema para ambientes C existentes. Outro exemplo é o uso de funções lexically aninhados e escopo estático, que suporta Pascal, mas C não.

Nestas circunstâncias, você pode tentar superar a resistência política ao idioma original. Você pode encontrar-se reimplementar Lisp mal, como em (tongue-in-cheek) décimo lei de Greenspun. Ou você pode apenas encontrar uma abordagem completamente diferente para solução. Mas, em qualquer caso, não é certamente uma maneira.

Answer 2

É sempre possível escrever uma forma não-recursivo para cada função recursiva?

Sim. Uma prova formal simples é mostrar que tanto µ recursão e não cálculo recursivo, como GOTO são ambos Turing completa. Uma vez que todos os cálculos completos de Turing são estritamente equivalente em seu poder expressivo, todas as funções recursiva pode ser implementada pelo cálculo Turing completo não-recursiva.

Infelizmente, eu sou incapaz de encontrar um bom, definição formal de GOTO on-line por isso aqui está um:

programa Um GOTO é uma sequência de comandos P executado num registar máquina tal que P é um dos seguintes:

• HALT, que a execução pára
• r = r + 1 onde r é qualquer registo
• r = r – 1 onde r é qualquer registo
• GOTO x onde x é um rótulo
• IF r ≠ 0 GOTO x onde r é qualquer registo e x é um rótulo
• Uma etiqueta, seguido por qualquer um dos comandos acima.

No entanto, as conversões entre funções recursivas e não recursivas nem sempre é trivial (exceto pelo irracional re-implementação manual da pilha de chamadas).

Para mais informações consulte esta resposta .

Answer 3

A recursão é implementado como stacks ou construções semelhantes em que os intérpretes ou compiladores reais. Então você certamente pode converter uma função recursiva para uma contrapartida iterativo porque é assim que sempre fez (se automaticamente) . Você só vai ser duplicar o trabalho do compilador de forma ad-hoc e, provavelmente, de uma maneira muito feia e ineficiente.

Answer 4

Basicamente sim, em essência, o que você acaba tendo que fazer é substituir chamadas de método (que empurram implicitamente estado na pilha) em empurrões pilha explícitas para se lembrar onde a 'chamada anterior' havia se levantado para, em seguida, executar o ' chamado método' em vez.

Eu imagino que a combinação de um loop, uma pilha e um estado-máquina poderia ser usado para todos os cenários por, basicamente, simulando as chamadas de método. Seja ou não este vai ser 'melhor' (ou mais rápido, ou mais eficiente em algum sentido) não é realmente possível dizer em geral.

Answer 5

• fluxo de execução função recursiva pode ser representada como uma árvore.

• A mesma lógica pode ser feito por um loop, que utiliza uma estrutura de dados para atravessar aquela árvore.

• travessia em profundidade pode ser feito utilizando uma pilha, de passagem de primeira largura pode ser feito usando uma fila.

Assim, a resposta é: sim. Por:. https://stackoverflow.com/a/531721/2128327

Pode qualquer recursão ser feito 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. avaliá-lo,
3. Goto 1.

Answer 6

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

Answer 7

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

Answer 8

Em princípio, é sempre possível remover recursão e substituí-lo por iteração em uma língua que tem estado infinita tanto para estruturas de dados e para a pilha de chamadas. Esta é 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 é perfeitamente possível ter uma linguagem em que a quantidade de memória que pode ser alocada no programa é limitado, mas onde a quantidade de pilha de chamadas que pode ser usado é ilimitada (32-bit C onde o endereço de variáveis ??de pilha não é acessível). Neste caso, a recursividade é mais poderoso simplesmente porque tem mais memória que pode usar; não há suficiente memória explicitamente allocatable para emular a pilha de chamadas. Para uma discussão detalhada sobre este assunto, consulte este discussão .

Answer 9

Às vezes substituindo a recursividade é muito mais fácil do que isso. Recursão costumava ser a coisa da moda ensinado em CS na década de 1990, e assim um monte de desenvolvedores médios a partir desse momento percebi que se você resolveu alguma coisa com recursividade, era uma solução melhor. Então eles usariam recursão em vez de loop para trás a ordem inversa, ou coisas bobas como essa. Então, às vezes remover a recursividade é um simples "duh, isso era óbvio" tipo de exercício.

Isso é menos de um problema agora, como a moda mudou para outras tecnologias.

Answer 10

Todas as funções calculáveis ??pode ser calculado por Turing máquinas e, por conseguinte, os sistemas recursivos e máquinas de Turing (sistemas iterativos) são equivalentes.

Answer 11

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

A seguir casos estão entre os fácil:

• cauda recursão
• dirigir linear recursão

Answer 12

Appart da pilha explícita, um outro padrão para a conversão de recursão para iteração é com o uso de um trampolim.

Aqui, as funções, quer retornar o resultado final, ou um fechamento da chamada de função que de outra forma teria realizado. Em seguida, o iniciador (trampolim) função de manutenção invocando o fechamento retornou até o resultado final seja alcançado.

Essa abordagem funciona para funções mutuamente recursivas, mas eu tenho medo que só funciona para tail-chamadas.

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

Answer 13

Eu diria que sim - uma chamada de função não é senão um goto e uma operação de pilha (grosso modo). Tudo que você precisa fazer é imitar a pilha que é construído ao invocar funções e fazer algo semelhante como um goto (você pode imitar gotos com línguas que não têm explicitamente esta palavra-chave também).

Answer 14

Tenha um olhar para as seguintes entradas na Wikipedia, você pode usá-los como ponto de partida para encontrar uma resposta completa à sua pergunta.

• recursão no computador
• recorrência relação

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

Solução de um meio de obtenção de uma relação de recorrência -forma fechada solução : um não- função recursiva de n.

Também dê uma olhada no último parágrafo do esta entrada .

Answer 15

É possível converter qualquer algoritmo recursivo para um não-recursiva uma, mas muitas vezes a lógica é muito mais complexo e isso requer o uso de uma pilha. Na verdade, a própria recursão usa uma pilha: o função de pilha.

Mais detalhes: https://developer.mozilla.org / eN-US / docs / web / JavaScript / Guia / Funções

Answer 16

tazzego, meios de recursão que uma função irá chamar a si mesma, quer você goste ou não. Quando as pessoas estão falando sobre se deve ou não as coisas podem ser feitas sem recursão, eles querem dizer isso e você não pode dizer "não, isso não é verdade, porque eu não concordar com a definição de recursividade" como uma declaração válido.

Com isso em mente, quase tudo que você diz é absurdo. A única outra coisa que você dizer que não é absurdo é a idéia de que você não pode imaginar a programação sem uma pilha de chamadas. Isso é algo que tinha sido feito por décadas até usando um callstack tornou-se popular. Versões antigas do Fortran faltava uma pilha de chamadas e eles trabalharam muito bem.

A propósito, existem Turing completo línguas que só implementar recursividade (por exemplo SML) como um meio de looping. Existem também Turing completo idiomas que só implementam iteração como um meio de looping (por exemplo, Fortran IV). A tese de Church-Turing prova que qualquer coisa possível em línguas só de recursão pode ser feito em um não-recursiva linguagem e vica-versa pelo fato de que ambos têm a propriedade de Turing completude.

Answer 17

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