Removendo a recursão - um olhar sobre a teoria nos bastidores

10

Eu sou novo neste site e essa pergunta certamente não é de nível de pesquisa - mas tudo bem. Eu tenho um pouco de experiência em engenharia de software e quase nenhum no CSTheory, mas acho atraente. Para resumir uma longa história, gostaria de uma resposta mais detalhada para o seguinte, se esta pergunta for aceitável neste site.

Então, eu sei que todo programa recursivo tem um analógico iterativo e eu meio que entendo a explicação popular que é oferecida, mantendo algo semelhante à "pilha do sistema" e pressionando as configurações do ambiente como endereço de retorno, etc. .

Sendo um pouco mais concreto, eu gostaria de (formalmente) ver como alguém prova essa afirmação nos casos em que você tem uma função que cadeia . Além disso, e se houver algumas instruções condicionais que possam levar um a chamar um ? Ou seja, o potencial gráfico de chamada de função possui alguns componentes fortemente conectados.F i F jF0F1FiFi+1FnF0FiFj

Gostaria de saber como essas situações podem ser tratadas, digamos algum conversor recursivo para iterativo. E a descrição ondulada à qual me referi anteriormente é realmente suficiente para esse problema? Quero dizer então porque é que acho fácil remover a recursão em alguns casos. Em particular, remover a recursão do percurso de pré-encomenda de uma árvore binária é realmente fácil - é uma pergunta de entrevista padrão, mas remover a recursão no caso de pós-pedido sempre foi um pesadelo para mim.

O que realmente estou perguntando é perguntas2

(1) Existe realmente uma prova mais formal (convincente?) De que a recursão pode ser convertida em iteração?

(2) Se essa teoria está realmente lá fora, então por que acho que, por exemplo, iteratizar a pré-encomenda mais fácil e a pós- encomenda mais difícil? (além da minha inteligência limitada)

Itachi Uchiha
fonte
11
como a palavra iteratizing :)
Akash Kumar
Não sei se entendi bem, mas se a recursão terminar em algum lugar, você poderá simular uma pilha do sistema usando sua própria pilha. Para a parte (2), os problemas não são diferentes em termos de complexidade computacional.
Singshumit 16/02/2012
Penso que esta pergunta teria sido mais adequada ao site de Ciência da Computação que ainda não está ativo. Quanto à sua segunda pergunta, você pode explicar por que acha que é mais difícil? O processo deve ser quase idêntico.
Raphael
obrigado a todos por seus comentários - acho que tenho bastante leitura para fazer.
Itachi Uchiha
@ Rafael - Um comentário sobre por que eu acho que iteratizing postorder é difícil (além de eu não ser capaz de fazê-lo). Eu estava lendo alguns artigos sobre remoção de recursão e encontrei algo chamado funções recursivas de cauda. Acontece que eles são mais fáceis de iterar. Ainda não entendo formalmente por que isso é verdade; mas há outra coisa que devo acrescentar. Ouvi dizer que a iteratização da pós-encomenda requer duas pilhas e não uma, mas não conheço os detalhes. E agora estou perdido - por que essa diferença entre esses dois modos de travessia? E por que a recursão da cauda é fácil de manusear?
Itachi Uchiha

Respostas:

6

Se bem entendi, você é claro sobre a conversão de funções que não contêm outras chamadas de função além de si mesmas.

Então assumir que temos uma "cadeia chamada" . Se, além disso, assumirmos que não são recursivos (porque já os convertemos), podemos incluir todas essas chamadas na definição de que se torna uma função diretamente recursiva com a qual já podemos lidar.FF1FnFF1,,FnF

Isso falha se algum possuir uma cadeia de chamadas recursiva na qual ocorre, ou seja, . Nesse caso, temos recursão mútua, o que requer outro truque para se livrar. A idéia é calcular as duas funções simultaneamente. Por exemplo, no caso trivial:FjFFjFFj

f(0) = a
f(n) = f'(g(n-1))

g(0) = b
g(n) = g'(f(n-1))

com f'e g'não-recursiva funções (ou, pelo menos, independente de fe g) se torna

h(0) = (a,b)
h(n) = let (f,g) = h(n-1) in (f'(g), g'(f)) end

f(n) = let (f, _) = h(n) in f end
g(n) = let (_, g) = h(n) in g end

Isso naturalmente se estende a mais funções envolvidas e funções mais complicadas.

Rafael
fonte
Ainda bem que pude ajudar. Lembre-se de aceitar sua resposta favorita clicando na marca de seleção ao lado.
Raphael
11
Raphel, seu truque funciona apenas quando ambas as funções recursivas aceitam argumentos do mesmo tipo. Se fe gaceitar diferentes tipos de tipos, é necessário um truque mais geral.
Andrej Bauer
@AndrejBauer boa observação, eu perdi totalmente isso. Eu realmente gostei da abordagem de Rafael, mas, como você observou em casos gerais, provavelmente precisamos de alguma idéia diferente. Você pode fazer outras sugestões?
Itachi Uchiha
@AndrejBauer True. Eu estava pensando do ponto de vista teórico da recursão; aqui só temos números naturais. Isso é suficiente porque podemos codificar tudo de maneira adequada. Mas seu argumento é muito válido para a prática. Acho que teríamos que reescrever fe gaté que eles compartilhem um esquema comum de codificação e recursão de entrada (não podemos ter um usando o e o outro ). n1n2
Raphael
Bem, veja minha resposta sobre como fazê-lo.
Andrej Bauer
8

Sim, existem razões convincentes para acreditar que a recursão pode ser transformada em iteração. É o que todo compilador faz quando converte o código-fonte em linguagem de máquina. Para a teoria, você deve seguir as sugestões de Dave Clarke. Se você deseja ver o código real que converte recursão em código não recursivo, dê uma olhada na machine.mllinguagem MiniML no meu PL Zoo (observe que a loopfunção na parte inferior, que realmente executa o código, é recursiva final e, portanto, pode trivialmente convertido em um loop real).

Mais uma coisa. O MiniML não suporta funções recursivas mutuamente. Mas isso não é um problema. Se você tiver recursão mútua entre funções

f1:A1B1
f2:A2B2
fn:AnBn

a recursão pode ser expressa em termos de um único mapa recursivo

f:A1++AnB1++Bn,
Andrej Bauer
fonte
8

Você pode querer olhar para a máquina SECD . Uma linguagem funcional (embora possa ser qualquer linguagem) é traduzida em uma série de instruções que gerenciam coisas como colocar argumentos de pilhas, "invocar" novas funções e assim por diante, todas gerenciadas por um loop simples.
Chamadas recursivas nunca são realmente chamadas. Em vez disso, as instruções do corpo da função que está sendo chamada são colocadas na pilha para execução.

Uma abordagem relacionada é a máquina CEK .

Estes já existem há muito tempo, por isso há muito trabalho neles. E, é claro, existem provas de que eles funcionam e o procedimento para "compilar" um programa nas instruções do SECD é linear no tamanho do programa (ele não precisa pensar no programa).

O ponto da minha resposta é que existe um procedimento automático para fazer o que você deseja. Infelizmente, a transformação não será necessariamente em termos de coisas que são imediatamente fáceis para um programador interpretar. Eu acho que a chave é que, quando você deseja iterar um programa, precisa armazenar na pilha o que o programa precisa fazer quando você retorna de uma chamada de função iterizada (isso é chamado de continuação). Para algumas funções (como funções recursivas de cauda), a continuação é trivial. Para outros, a continuação talvez seja muito complexa, especialmente se você precisar codificá-la.

Dave Clarke
fonte
eu serei honesto aqui. Eu realmente quero entender por que (e como) você pode iterar todos os programas recursivos. Mas acho difícil ler um artigo - eles geralmente não são acessíveis para mim. Quero dizer, quero uma razão mais profunda do que a descrição "ondulada" que mencionei na pergunta. mas eu também estou feliz com alguma coisa que me dá um novo insight - não tem que ser toda a prova em seus detalhes âmago da questão
Itachi Uchiha
[cntd] Quero dizer, gostarei da prova, se houver, para me dizer por que a iteratização de um programa é mais fácil que a outra. Mas, em certo sentido, o conversor recursivo para iterativo deve funcionar, independentemente do programa recursivo necessário como entrada. Claro, mas acho que fazer um conversor desse tipo pode ser tão difícil quanto o problema de parada? Estou apenas adivinhando aqui - mas eu gostaria que existisse um conversor recursivo para iterativo e, se existir, gostaria que ele explicasse a complexidade inerente da iteração de diferentes programas recursivos. não tenho certeza, mas devo editar a pergunta? Minha pergunta está clara?
Itachi Uchiha
@ ItachiUchiha - Não acho que seu problema seja indecidível. Veja a resposta de Andrej Bauer. Ele observa que todo compilador faz isso quando traduz o código fonte para a linguagem de máquina. Ele também acrescenta que você pode ver o código real que converte recursivo em não recursivo no idioma MiniM (a) l. Isso indica claramente que existe um procedimento de decisão para "iteratizar" a recursão. Não tenho certeza sobre a dificuldade / complexidade (conceitual) inerente de remover a recursão. Não entendo muito bem essa pergunta, mas parece interessante. Talvez você pode editar sua pergunta para obter melhor resposta
Akash Kumar
O ponto da minha resposta é que existe um procedimento automático para fazer o que você deseja. Infelizmente, a transformação não será necessariamente em termos de coisas que são imediatamente fáceis para um programador interpretar. Eu acho que a chave é que, quando você deseja iterar um programa, precisa armazenar na pilha o que o programa precisa fazer quando você retorna de uma chamada de função iterizada (isso é chamado de continuação). Para algumas funções (como funções recursivas de cauda), a continuação é trivial. Para outros, a continuação talvez seja muito complexa, especialmente se você precisar codificá-la.
21812 Dave Clarke
6

P : "Existe realmente uma prova mais formal (convincente?) De que a recursão pode ser convertida em iteração?"

A : A integridade de Turing de uma máquina de Turing :-)

Brincadeiras à parte, o modelo da máquina RASP (Programa de Acesso Aleatório Equivalente à Turing ) está próximo de como os microprocessadores reais funcionam e seu conjunto de instruções contém apenas um salto condicional (sem recursão). A possibilidade de auto-modificar dinamicamente o código facilita a tarefa de implementar sub-rotinas e chamadas recursivas.

Acho que você pode encontrar muitos artigos / artigos sobre a " conversão recursiva para iterativa " (consulte a resposta de Dave ou apenas as palavras-chave no Google), mas talvez uma abordagem menos conhecida (e prática ) seja a mais recente pesquisa sobre implementação de algoritmos recursivos em hardware ( usando a linguagem VHDL "compilada" diretamente em uma peça de hardware). Por exemplo, veja o artigo de V.Sklyarov " Implementação baseada em FPGA de algoritmos recursivos " ( O artigo sugere um novo método para implementar algoritmos recursivos em hardware ...). Duas aplicações práticas de algoritmos recursivos na área de classificação e compressão de dados foram estudadas. em detalhes .... ).

Marzio De Biasi
fonte
1

Se você estiver familiarizado com idiomas que suportam lambdas, um caminho é procurar a transformação do CPS. Remover o uso da pilha de chamadas (e a recursão em particular) é exatamente o que a transformação do CPS faz. Ele transforma um programa que contém chamadas de procedimento em um programa com apenas chamadas de cauda (você pode pensar nelas como gotos, que é uma construção iterativa).

A transformação do CPS está intimamente relacionada à manutenção explícita de uma pilha de chamadas em uma pilha tradicional baseada em matriz, mas, em vez de em uma matriz, a pilha de chamadas é representada com fechamentos vinculados.

Jules
fonte
0

na minha opinião, essa pergunta remonta às próprias origens das definições de computação e foi provada rigorosamente há muito tempo na época em que o cálculo lambda da igreja (que captura muito o conceito de recursão) mostrou-se equivalente às máquinas de Turing e está contido na terminologia ainda usada "linguagens / funções recursivas". aparentemente, também, uma referência-chave posterior, ao longo destas linhas, é a seguinte

Como apontado pelo artigo de Peter Landin, de 1965, Uma correspondência entre a ALGOL 60 e a notação Lambda de Church, as linguagens de programação de procedimentos sequenciais podem ser entendidas em termos do cálculo lambda, que fornece os mecanismos básicos para a abstração procedimental e a aplicação de procedimentos (subprogramas).

boa parte disso está nesta tese sobre a igreja na página da wikipedia . não tenho certeza das especificidades exatas, mas o artigo da Wikipedia parece indicar que foi Rosser (1939) quem primeiro provou essa equivalência entre o cálculo lambda e as máquinas de turing. talvez / presumivelmente seu artigo tenha um mecanismo semelhante a uma pilha para converter as chamadas lambda (possivelmente recursivas) para a construção tm?

Rosser, JB (1939). "Uma exposição informal de provas do teorema de Godel e do teorema da igreja". O Jornal da Lógica Simbólica (O Jornal da Lógica Simbólica, Vol. 4, Nº 2) 4 (2): 53–60. doi: 10.2307 / 2269059. JSTOR 2269059.

note, é claro, para qualquer pessoa interessada nos princípios, a moderna linguagem Lisp e o esquema variante têm intencionalmente uma forte semelhança com o cálculo lambda. estudar o código do intérprete para a avaliação da expressão leva a idéias que estavam originalmente contidas em documentos para a integridade do cálculo do lambda.

vzn
fonte
11
A prova de equivalência de Turing / lambda está no apêndice deste documento: www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
Radu GRIGore