Todas as recursões podem ser convertidas em iteração?

Um tópico do reddit trouxe uma questão aparentemente interessante:

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

O exemplo (contador?) No post é o par:

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

Você pode sempre transformar uma function recursiva em uma iterativa? Sim, absolutamente, e a tese de Church-Turing prova que a memory 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 function recursiva. Knuth oferece várias técnicas em “The Art of Computer Programming”. E muitas vezes, uma coisa calculada recursivamente pode ser calculada por uma abordagem completamente diferente em menos tempo e espaço. O exemplo clássico disso é o número de Fibonacci ou suas seqüências. Você certamente encontrou esse problema em seu plano de graduação.

Por outro lado, podemos certamente imaginar um sistema de programação tão avançado a ponto de tratar uma definição recursiva de uma fórmula como um convite para memorizar resultados anteriores, oferecendo assim o benefício da velocidade sem o incômodo de dizer ao computador exatamente quais passos siga no cálculo de uma fórmula com uma definição recursiva. Dijkstra quase certamente imaginou tal sistema. Ele passou muito tempo tentando separar a implementação da semântica de uma linguagem de programação. Então, novamente, suas linguagens de programação não determinísticas e multiprocessadas 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 exista um motivo convincente, você provavelmente não deve (manualmente) converter essas funções em um algoritmo explicitamente iterativo. Seu computador irá lidar com esse trabalho corretamente.

Eu posso ver uma razão convincente. Suponha que você tenha um sistema 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 execução. Por exemplo, a recursion de cauda infinita é possível no Esquema, mas o mesmo idioma causa um problema para ambientes C existentes. Outro exemplo é o uso de funções lexicamente aninhadas e escopo estático, que Pascal suporta, mas C não suporta.

Nestas circunstâncias, você pode tentar superar a resistência política à língua original. Você pode se encontrar reimplementando Lisp mal, como na décima lei de Greenspun (irônico). Ou você pode simplesmente encontrar uma abordagem completamente diferente para a solução. Mas, de qualquer forma, há certamente um caminho.

É sempre possível escrever uma forma não recursiva para cada function recursiva?

Sim. Uma prova formal simples é mostrar que tanto a recursion µ como um cálculo não recursivo, como GOTO, são ambos 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 boa e formal de GOTO on-line, então aqui está uma:

Um programa GOTO é uma seqüência de comandos P executados em uma máquina registradora, de tal forma que P é um dos seguintes:

  • HALT , que interrompe a execução
  • r = r + 1 onde r é qualquer registrador
  • r = r – 1 onde r é qualquer registrador
  • GOTO x onde x é um label
  • IF r ≠ 0 GOTO x onde r é qualquer registro e x é um label
  • Um label, 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 irrelevante da pilha de chamadas).

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

Basicamente sim, em essência, o que você acaba tendo que fazer é replace as chamadas de método (que implicitamente enviam estado para a pilha) para explícitas de pilha para lembrar de onde a ‘chamada anterior’ chegou e então 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 poderia ser usada para todos os cenários, basicamente simulando as chamadas de método. Se isso vai ou não ser “melhor” (mais rápido, ou mais eficiente em algum sentido), não é realmente possível dizer em geral.

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

  • O stream de execução de function recursiva pode ser representado como uma tree.

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

  • A passagem em profundidade pode ser feita usando uma pilha, o primeiro percurso pode ser feito usando uma fila.

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

Qualquer recursion 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. avaliá-lo
  3. goto 1.

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

Em princípio, é sempre possível remover a recursion e substituí-la por iteração em uma linguagem que possui um estado infinito para estruturas de dados e para a pilha de chamadas. Esta é uma conseqüê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 uma linguagem onde a quantidade de memory que pode ser alocada no programa é limitada, mas onde a quantidade de pilha de chamadas que pode ser usada é ilimitada (C de 32 bits onde o endereço das variables ​​da pilha não é acessível). Nesse caso, a recursion é mais poderosa simplesmente porque tem mais memory que pode usar; não há memory alocável explicitamente suficiente para emular a pilha de chamadas. Para uma discussão detalhada sobre isso, veja esta discussão .

Às vezes, replace a recursion é muito mais fácil do que isso. A recursion costumava ser a coisa da moda ensinada em CS nos anos 90, e assim muitos desenvolvedores médios daquela época descobriram que se você resolvesse algo com recursion, seria uma solução melhor. Então, eles usariam recursion em vez de retroceder para inverter a ordem ou coisas bobas como essa. Então, às vezes, remover a recursion é um tipo de exercício simples “duh, que era óbvio”.

Este é um problema menor agora, já que a moda mudou para outras tecnologias.

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

Remover a recursion é um problema complexo e é viável sob circunstâncias bem definidas.

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

  • recursion da cauda
  • recursion linear direta

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

Aqui, as funções retornam o resultado final ou um fechamento da chamada de function que, de outra forma, teria realizado. Então, a function inicial (trampolining) continua invocando os closures retornados até que o resultado final seja alcançado.

Essa abordagem funciona para funções mutuamente recursivas, mas temo que funcione apenas para chamadas.

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

Eu diria que sim – uma chamada de function não é nada além de uma operação de goto e de pilha (grosso modo). Tudo o que você precisa fazer é imitar a pilha que é construída ao invocar funções e fazer algo semelhante a um goto (você pode imitar gotos com linguagens que não têm explicitamente essa palavra-chave também).

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

  • Recursão em ciência da computação
  • Relação de recorrência

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

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

Também dê uma olhada no último parágrafo desta input .

É possível converter qualquer algoritmo recursivo para um não-recursivo, mas muitas vezes a lógica é muito mais complexa e isso requer o uso de uma pilha. De fato, a própria recursion usa uma pilha: a pilha de funções.

Mais detalhes: https://developer.mozilla.org/pt-BR/docs/Web/JavaScript/Guide/Functions

tazzego, recursion significa que uma function vai 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 recursion, elas significam isso e você não pode dizer “não, isso não é verdade, porque eu não concordo com a definição de recursion” como uma afirmação válida.

Com isso em mente, quase tudo o que você diz é um triggerste. A única outra coisa que você diz que não é um absurdo é a ideia de que você não pode imaginar a programação sem um callstack. Isso é algo que foi feito por décadas até que o uso de um callstack se tornou popular. Versões antigas do FORTRAN não tinham um callstack e funcionavam muito bem.

A propósito, existem linguagens Turing-completas que apenas implementam recursion (por exemplo, SML) como um meio de looping. Existem também linguagens Turing-completas que apenas implementam iteração como um meio de looping (por exemplo, FORTRAN IV). A tese de Church-Turing prova que tudo o que é possível em uma linguagem recursiva somente pode ser feito em uma linguagem não recursiva e vica-versa pelo fato de que ambos têm a propriedade de completude.

Aqui está um algoritmo iterativo:

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

Uma pergunta: se, como primeira coisa, a function faz uma cópia de si mesma em um espaço de memory vazia aleatória e, em vez de chamar a si mesma, chamar a cópia, isso ainda é recursion? (1) Eu diria sim.

O uso explícito da pilha é uma maneira real de remover a recursion? (2) eu diria que não. Basicamente, não estamos imitando o que acontece quando usamos explicitamente recursion? Acredito que não podemos definir a recursion simplesmente como “uma function que se chama”, visto que também vejo recursion no “código de cópia” (1) e no “uso explícito de pilha” (2).

Além disso, não vejo como a CT demonstra que todos os algoritmos recursivos podem se tornar iterativos. Parece apenas dizer-me que “tudo” tendo o “poder” da máquina de Turing pode expressar todos os algoritmos que isso pode expressar. Se a máquina de Turing não pode recorrer, temos certeza que todo algoritmo recursivo tem sua tradução interativa … A máquina de Turing pode recursion? De acordo comigo, se pode ser “implementado” (por qualquer meio), então podemos dizer que tem. Tem isso? Eu não sei.

Todos os processadores reais que conheço podem recursion. Honestamente, não consigo ver como programar de verdade sem ter uma pilha de chamadas, e acho que isso é o que torna a recursion possível primeiro.

Evitando copiar (1) e “pilha imitada” (2), demonstramos que todo algoritmo recursivo pode ser, em máquinas reais, expresso iterativamente ?! Eu não posso ver onde nós demonstramos isso.