A iteração pode substituir a recursão?

42

Tenho visto em todo estouro de pilha, por exemplo, aqui , aqui , aqui , aqui , aqui e alguns outros eu não me importo de mencionar, que "qualquer programa que usa recursão pode ser convertido em um programa usando apenas iteração".

Havia até mesmo um altamente upvoted fio com um altamente upvoted resposta que disse sim, é possível.

Agora não estou dizendo que eles estão errados. É que essa resposta contraria meu escasso conhecimento e compreensão sobre computação.

Acredito que todas as funções iterativas podem ser expressas como recursão, e a Wikipedia tem uma declaração nesse sentido. No entanto, duvido que o inverso seja verdadeiro. Por um lado, duvido que funções recursivas não primitivas possam ser expressas iterativamente.

Também duvido que as hiperoperações possam ser expressas iterativamente.

Em sua resposta (que não entendo a propósito) à minha pergunta, o YuvalFIlmus disse que não é possível converter nenhuma sequência de operações matemáticas em uma sequência de adições.

Se a resposta de YF estiver realmente correta (acho que está, mas o raciocínio dele estava acima da minha cabeça), isso não significa que nem toda recursão pode ser convertida em iteração? Como se fosse possível converter todas as recursões em iterações, eu seria capaz de expressar todas as operações como uma sequência de adições.

Minha pergunta é esta:

Toda recursão pode ser convertida em iteração e por quê?

Por favor, responda que um colegial brilhante ou um aluno do primeiro ano do ensino médio entenderão. Obrigado.

PS: Eu não sei o que é recursiva primitiva (eu sei sobre a função Ackermann, e que ela não é recursiva primitiva, mas ainda é computável. AL1 meu conhecimento sobre isso vem da página da Wikipedia na função Ackermann).

PPS: Se a resposta for sim, você poderia, por exemplo, escrever uma versão iterativa de uma função não primitiva-recursiva. Por exemplo, Ackermann na resposta. Isso vai me ajudar a entender.

Tobi Alafin
fonte
21
Tudo o que você executa em uma CPU é iterativo. Você pode escrevê-lo recursivamente em uma linguagem de ordem superior, mas é compilado em várias instruções iterativas do assembler de qualquer maneira. Tão literalmente, o compilador faz exatamente o que você está perguntando, e converte toda a sua recursão sofisticada em várias instruções iterativas para uma CPU.
Davor
6
Em um nível baixo, a maioria de nós sabe que recursão é igual a iteração mais pilha. Gramáticas livres de contexto modelam recursão, enquanto autômatos de empilhamento são "programas" iterativos com memória de pilha.
Hendrik Jan
2
Apenas salientando que geralmente é uma boa ideia aguardar pelo menos 24 horas para ver se outras respostas aparecem. A pergunta aceita parece muito longa e complicada para mim, francamente, e parece complicar deliberadamente mais do que o necessário. A resposta básica para sua pergunta é "a pilha usada para recursão pode ser explicitamente implementada de maneira iterativa" e não precisa ser muito mais complicada do que isso. Considerações sobre a memória ser ilimitada ou não entrar em jogo, pois esse recurso também é necessário para pilhas de recursão.
AnoE
é possível implementar emulador de máquina de Turing com apenas iteração
Sarge Borsch
Em uma aula de linguagens comparativas que eu tirei há muito tempo, tivemos que escrever a função de Ackermann em assembly, em FORTRAN (não o Fortran moderno) e em uma linguagem recursiva de sua escolha. Então, sim, é possível na prática. E é claro que é possível em teoria. Veja, por exemplo, a pergunta que prova que as máquinas de Turing e o cálculo lambda são equivalentes .
David Hammen

Respostas:

52

É possível substituir a recursão por iteração mais memória ilimitada .

Se você possui apenas iteração (digamos, enquanto loops) e uma quantidade finita de memória, tudo o que você tem é um autômato finito. Com uma quantidade finita de memória, o cálculo possui um número finito de etapas possíveis, portanto é possível simular todas elas com um autômato finito.

Ter memória ilimitada muda o negócio. Essa memória ilimitada pode assumir várias formas que acabam tendo um poder expressivo equivalente. Por exemplo, uma máquina de Turing mantém as coisas simples: há uma única fita e o computador pode avançar ou retroceder a fita um passo de cada vez - mas isso é suficiente para fazer qualquer coisa que você possa fazer com funções recursivas.

Uma máquina de Turing pode ser vista como um modelo idealizado de um computador (máquina de estado finito) com algum armazenamento extra que cresce sob demanda. Observe que é crucial que não apenas não exista um limite finito na fita, mas mesmo com a entrada, você não pode prever com segurança a quantidade de fita necessária. Se você pudesse prever (ou seja, computar) quanta fita é necessária a partir da entrada, poderia decidir se o cálculo seria interrompido calculando o tamanho máximo da fita e tratando todo o sistema, incluindo a fita agora finita, como uma máquina de estado finito .

Outra maneira de simular uma máquina de Turing com computadores é a seguinte. Simule a máquina de Turing com um programa de computador que armazena o início da fita na memória. Se o cálculo chegar ao final da parte da fita que cabe na memória, substitua o computador por um computador maior e execute o cálculo novamente.

Agora, suponha que você queira simular uma computação recursiva com um computador. As técnicas para executar funções recursivas são bem conhecidas: cada chamada de função possui um pedaço de memória, chamado de quadro de pilha . Fundamentalmente, funções recursivas podem propagar informações através de várias chamadas, passando variáveis ​​por aí. Em termos de implementação em um computador, isso significa que uma chamada de função pode acessar o quadro de pilha de uma chamada principal (grande) * .

Um computador é um processador - uma máquina de estados finitos (com um grande número de estados, mas estamos fazendo a teoria da computação aqui, então tudo o que importa é que é finito) - juntamente com uma memória finita. O microprocessador executa um loop while gigante: “enquanto a energia estiver ligada, leia uma instrução da memória e execute-a”. (Processadores reais são muito mais complexos que isso, mas isso não afeta o que eles podem calcular, apenas a rapidez e conveniência de fazê-lo.) Um computador pode executar funções recursivas com esse loop while para fornecer iteração, além do mecanismo para acessar a memória, incluindo a capacidade de aumentar o tamanho da memória à vontade.

Se você restringir a recursão à recursividade primitiva, poderá restringir a iteração à iteração limitada . Ou seja, em vez de usar loops while com um tempo de execução imprevisível, você pode usar loops nos quais o número de iterações é conhecido no início do loop¹. O número de iterações pode não ser conhecido no início do programa: ele próprio pode ter sido calculado por loops anteriores.

Não vou nem esboçar uma prova aqui, mas há uma relação intuitiva entre ir da recursão primitiva à recursão total e passar de loops para loops enquanto: em ambos os casos, envolve não saber antecipadamente quando você vai Pare. Com recursão total, isso é feito com o operador de minimização, onde você continua até encontrar um parâmetro que satisfaça a condição. Com os loops while, isso é feito continuando até que a condição do loop seja satisfeita.

forwhilen

Gilles 'SO- parar de ser mau'
fonte
Aceitar a explicação detalhada, mantida no nível solicitado.
Tobi Alafin
12
Acho que vale a pena notar que, em computadores reais, a recursão também consome memória (pilha crescente de chamadas). Portanto, em aplicações práticas, não há necessidade de memória ilimitada (porque tudo é limitado por ela igualmente). E a recursão geralmente precisa de mais memória que iteração.
Agent_L
@Agent_L Sim, a recursão precisa de memória ilimitada para armazenar todos os quadros da pilha. Com uma abordagem de recursão, há um requisito de memória ilimitada, mas não é intuitivamente separável do seqüenciamento de operações, como nas iterações.
Gilles 'SO- stop be evil'
11
Talvez seja interessante a tese de Church-Turing. Máquinas de Turing são máquinas altamente iterativas sem nenhum conceito (inerente) de recursão. O cálculo Lambda é uma linguagem criada para expressar cálculos de maneira recursiva. A tese de Church-Turing mostrou que todas as expressões lambda podiam ser avaliadas em uma máquina de Turing, vinculando recursão e iteração.
Cort Ammon
11
@BlackVegetable Se um método recursivo não possui variáveis ​​internas e a única memória usada é a pilha de chamadas (o que pode ser otimizada pelo TCO), sua versão iterativa provavelmente também não terá variáveis ​​internas e usará apenas uma quantidade constante de memória ( variáveis) compartilhadas em todas as iterações, como contador.
Agent_L 30/12
33

Toda recursão pode ser convertida em iteração, conforme testemunhado por sua CPU, que executa programas arbitrários usando uma iteração infinita de busca e execução. Essa é uma forma do teorema de Böhm-Jacopini . Além disso, muitos modelos de computação completos de Turing não têm recursão, por exemplo, máquinas de Turing e contra-máquinas .

Funções recursivas primitivas correspondem a programas usando iteração limitada , ou seja, você precisa especificar o número de iterações que um loop é executado com antecedência. A iteração limitada não pode simular recursão em geral, pois a função Ackermann não é recursiva primitiva. Mas a iteração ilimitada pode simular qualquer função parcialmente computável.

Yuval Filmus
fonte
25

a(n,m)

s

push(s,x)xxpop(s)empty(s)

Ackermann(n0,m0):

  • s= (inicializa a pilha vazia)
  • push(s,n0)
  • push(s,m0)
  • while(true):
    • mpop(s)
    • if(empty(s)):
      • return m (isso encerra o loop)
    • npop(s)
    • if(n=0):
      • push(s,m+1)
    • else if(m=0):
      • push(s,n1)
      • push(s,1)
    • else:
      • push(s,n1)
      • push(s,n)
      • push(s,m1)

Eu implementei isso no Ceilão, você pode executá-lo no WebIDE , se quiser. (Ele gera a pilha no início de cada iteração do loop.)

Obviamente, isso acabou de mover a pilha de chamadas implícita da recursão para uma pilha explícita com os parâmetros e valores de retorno.

Paŭlo Ebermann
fonte
15
Eu acho que esse é um ponto importante. Você mostrou explicitamente que a recursão não é nada de especial e que pode ser removida apenas mantendo o controle da pilha de chamadas, em vez de permitir que o compilador faça isso. A recursão é apenas um recurso do compilador que facilita a escrita desse tipo de programa.
David Richerby
4
Obrigado por se esforçar para escrever o programa solicitado.
precisa
16

Já existem ótimas respostas (com as quais não posso nem competir), mas eu gostaria de apresentar essa explicação simples.

Recursão é apenas a manipulação da pilha de tempo de execução. A recursão adiciona um novo quadro de pilha (para a nova chamada da função recursiva) e o retorno remove um quadro de pilha (para a inovação recém-concluída da função recursiva). A recursão fará com que algum número de quadros de pilha seja adicionado / removido, até que eventualmente todos saiam (espero!) E o resultado seja retornado ao chamador.

Agora, o que aconteceria se você fizesse sua própria pilha, substituísse as chamadas de função recursiva por empurrar para a pilha, substituísse o retorno das funções recursivas por estourar a pilha e tivesse um loop while que funcionasse até que a pilha estivesse vazia?

Alexander
fonte
2

Tanto quanto eu sei, e na minha própria experiência, você pode implementar qualquer recursão como uma iteração. Como mencionado acima, a recursão usa a pilha, que é conceitualmente ilimitada, mas praticamente limitada (você já recebeu uma mensagem de estouro de pilha?). Nos meus primeiros dias de programação (no terceiro trimestre do século passado do último milênio) eu estava usando linguagens não recursivas implementando algoritmos recursivos e não tive problemas. Eu não tenho certeza de como alguém poderia provar isso, no entanto.

Louis Giokas
fonte