Um loop while é intrinsecamente uma recursão?

37

Gostaria de saber se um loop while é intrinsecamente uma recursão?

Eu acho que é porque um loop while pode ser visto como uma função que se chama no final. Se não é recursão, então qual é a diferença?

adeus
fonte
13
Você pode converter recursão em iteração e vice-versa, sim. Isso não significa que eles são os mesmos, eles apenas têm os mesmos recursos. Há momentos em que a recursão é mais natural e há momentos em que a iteração é mais natural.
precisa
18
@MooingDuck Você pode provar por indução que qualquer recursão pode ser escrita como iteração e vice-versa. Sim, parecerá muito diferente, mas você pode fazê-lo.
Polygnome
6
O que intrinsecamente o mesmo significa aqui? Na programação, usar recursão significa algo específico, diferente da iteração (loops). No CS, quando você se aproxima do lado teórico da matemática, essas coisas começam a significar coisas um pouco diferentes.
Hyde
3
@MooingDuck A conversão de recursiva para iterativa é realmente bastante trivial. Você apenas mantém uma pilha de parâmetros de chamada de função e uma pilha de resultados para as chamadas de função. Você substitui as chamadas recursivas adicionando os parâmetros à pilha de chamadas. Certifique-se de que toda a manipulação da pilha rompe um pouco a estrutura do algoritmo, mas depois que você entende isso é muito fácil ver que o código faz a mesma coisa. Basicamente, você está escrevendo explicitamente a pilha de chamadas implícita nas definições recursivas.
Bakuriu 25/07/2016

Respostas:

116

Loops são muito não recursão. De fato, eles são o principal exemplo do mecanismo oposto : iteração .

O ponto de recursão é que um elemento do processamento chama outra instância de si mesmo. O máquinas de controle de loop apenas salta de volta ao ponto onde começou.

Pulando no código e chamando outro bloco de código são operações diferentes. Por exemplo, quando você pula para o início do loop, a variável de controle do loop ainda tem o mesmo valor que tinha antes do salto. Mas se você chamar outra instância da rotina em que está, a nova instância terá cópias novas e não relacionadas de todas as suas variáveis. Efetivamente, uma variável pode ter um valor no primeiro nível de processamento e outro valor em um nível inferior.

Esse recurso é crucial para o funcionamento de muitos algoritmos recursivos, e é por isso que você não pode emular a recursão via iteração sem também gerenciar uma pilha de quadros chamados, que monitora todos esses valores.

Kilian Foth
fonte
10
@Giorgio Isso pode ser verdade, mas é um comentário sobre uma reivindicação que a resposta não fez. "Arbitrariamente" não está presente nesta resposta e altera significativamente o significado.
hvd 24/07
12
@hvd Em princípio, a recursão da cauda é recursiva total como qualquer outra. Compiladores inteligentes podem otimizar a parte real "criando um novo quadro de pilha" para que o código gerado seja muito semelhante a um loop, mas os conceitos sobre os quais estamos falando se aplicam ao nível do código-fonte. Eu considero a forma que um algoritmo tem como código fonte a coisa mais importante, então eu ainda chamaria de recursão #
Kilian Foth
15
@Giorgio "é exatamente isso que a recursão faz: se chama com novos argumentos" - exceto a chamada. E os argumentos.
Hbbs
12
@Giorgio Você está usando definições diferentes de palavras que a maioria aqui. As palavras, você sabe, são a base da comunicação. Isso é programadores, não CS Stack Exchange. Se usássemos palavras como "argumento", "chamada", "função" etc. da maneira que você sugere, seria impossível discutir sobre o código real.
Hyde
6
@Giorgio Estou olhando para o conceito abstrato. Existe o conceito em que você se repete e o conceito em que se repete. Eles são conceitos diferentes . Hobbs está 100% correto de que não há argumentos e não há chamada. Eles são fundamental e abstratamente diferentes. E isso é bom porque eles resolvem problemas diferentes. Por outro lado, você está vendo como implementar loops quando sua única ferramenta é a recursão. Irônico, você está dizendo a Hobbs que pare de pensar em implementação e comece a examinar conceitos quando sua metodologia for a que realmente precisa de reavaliação.
corsiKa
37

Dizer que X é intrinsecamente Y só faz sentido se você tiver em mente algum sistema (formal) de que está expressando X. Se você definir a semântica de whileem termos do cálculo lambda, poderá mencionar recursão *; se você o definir em termos de uma máquina de registro, provavelmente não o fará.

Em qualquer um dos casos, as pessoas provavelmente não o entenderão se você chamar uma função recursiva apenas porque ela contém um loop while.

* Embora talvez apenas indiretamente, por exemplo, se você o definir em termos de fold.

Anton Golov
fonte
4
Para ser justo, a função não é recursiva em nenhuma definição. Ele apenas contém um elemento recursivo, o loop.
Luaan 25/07/16
@Luaan: Definitivamente, mas como em linguagens com uma whilerecursividade de construto geralmente é uma propriedade de funções, simplesmente não consigo pensar em outra coisa para descrever como "recursiva" nesse contexto.
Anton Golov 26/07/16
36

Isso depende do seu ponto de vista.

Se você observar a teoria da computabilidade , a iteração e a recursão são igualmente expressivas . O que isso significa é que você pode escrever uma função que calcula algo e, não importa se você faz isso de forma recursiva ou iterativa, poderá escolher as duas abordagens. Não há nada que você possa calcular recursivamente que você não possa calcular iterativamente e vice-versa (embora o funcionamento interno do programa possa ser diferente).

Muitas linguagens de programação não tratam a recursão e a iteração da mesma forma, e por boas razões. Geralmente , recursão significa que o idioma / compilador lida com a pilha de chamadas e iteração significa que você pode ter que manipular a pilha sozinho.

No entanto, existem linguagens - especialmente linguagens funcionais - nas quais coisas como loops (para, enquanto) são realmente apenas açúcar sintático para recursão e implementadas nos bastidores dessa maneira. Isso geralmente é desejável em linguagens funcionais, porque elas geralmente não têm o conceito de loop, e adicioná-lo tornaria o cálculo mais complexo por pouco motivo prático.

Portanto, não, eles não são intrinsecamente iguais . Eles são igualmente expressivos , o que significa que você não pode calcular algo iterativamente, não pode recursivamente e vice-versa, mas é isso, no caso geral (de acordo com a tese de Church-Turing).

Observe que estamos falando de programas recursivos aqui. Existem outras formas de recursão, por exemplo, em estruturas de dados (por exemplo, árvores).


Se você olhar para isso do ponto de vista da implementação , a recursão e a iteração não serão iguais. A recursão cria um novo quadro de pilha para cada chamada. Cada passo da recursão é independente, obtendo os argumentos para o cálculo do chamado (ele mesmo).

Os loops, por outro lado, não criam quadros de chamadas. Para eles, o contexto não é preservado em cada etapa. Para o loop, o programa simplesmente retorna ao início do loop até que a condição do loop falhe.

Isso é muito importante saber, pois pode fazer diferenças bastante radicais no mundo real. Para recursão, todo o contexto deve ser salvo em todas as chamadas. Para iteração, você tem um controle preciso sobre quais variáveis ​​estão na memória e o que é salvo onde.

Se você olhar dessa maneira, verá rapidamente que, para a maioria dos idiomas, a iteração e a recursão são fundamentalmente diferentes e têm propriedades diferentes. Dependendo da situação, algumas das propriedades são mais desejáveis ​​do que outras.

A recursão pode tornar os programas mais simples e fáceis de testar e comprovar . Converter uma recursão em iteração geralmente torna o código mais complexo, aumentando a probabilidade de falha. Por outro lado, a conversão para iteração e a redução da quantidade de quadros da pilha de chamadas podem economizar a memória necessária.

Polygnome
fonte
Um idioma com variáveis ​​locais e recursão, mas nenhuma matriz pode executar tarefas que não poderiam ser executadas por uma linguagem iterativa com variáveis ​​locais e sem matrizes. Por exemplo, relate se uma entrada contém uma sequência alfanumérica de comprimento desconhecido seguida por um espaço em branco e, em seguida, os caracteres da sequência original na ordem inversa.
Supercat
3
Enquanto o idioma estiver completo, ele pode. Uma matriz pode ser facilmente substituída por uma lista vinculada (duplamente), por exemplo. Falar sobre iteração ou recursão e se são iguais só faz sentido se você comparar dois idiomas completos completos.
Polygnome
Eu quis dizer não ter nada além de variáveis ​​estáticas ou automáticas simples, ou seja, não estar completo em Turing. Uma linguagem puramente iterativa seria limitada às tarefas que podem ser realizadas por meio de autômato finito determinístico simples, enquanto uma linguagem recursiva adicionaria a capacidade de executar tarefas que exigiriam pelo menos um autômato finito determinístico de pushdown.
Supercat 25/07
11
Se o idioma não estiver completo, é inútil começar. Os DFAs não podem fazer iterações arbitrárias nem recursões.
Polygnome
2
Nenhuma implementação é realmente completa para Turing, e idiomas que não são completos para Turing podem ser úteis para muitos propósitos. Qualquer programa que possa ser executado com um número finito de variáveis ​​com um intervalo finito pode ser acomodado por um DFA, em que toda combinação possível de valores é um estado discreto.
26616
12

A diferença é a pilha implícita e a semântica.

Um loop while que "se chama no final" não tem pilha para rastrear de volta quando terminar. Sua última iteração define qual será o estado ao terminar.

Entretanto, a recursão não pode ser feita sem essa pilha implícita que lembra o estado do trabalho realizado anteriormente.

É verdade que você pode resolver qualquer problema de recursão com iteração, se você der acesso explícito a uma pilha. Mas fazê-lo dessa maneira não é o mesmo.

A diferença semântica tem a ver com o fato de que olhar para o código recursivo transmite uma idéia de uma maneira completamente diferente do código iterativo. O código iterativo faz as coisas um passo de cada vez. Ele aceita qualquer estado que veio antes e só funciona para criar o próximo estado.

Código recursivo divide um problema em fractais. Essa pequena parte se parece com essa grande parte, para que possamos fazer exatamente isso e da mesma maneira. É uma maneira diferente de pensar sobre os problemas. É muito poderoso e leva tempo para se acostumar. Muito pode ser dito em poucas linhas. Você simplesmente não pode tirar isso de um loop while, mesmo que ele tenha acesso a uma pilha.

candied_orange
fonte
5
Eu acho que "pilha implícita" é enganosa. A recursão faz parte da semântica de uma linguagem, não um detalhe de implementação. (Concedido, a maioria dos idiomas de suporte à recursão usa uma pilha de chamadas; mas, em primeiro lugar, alguns desses idiomas não, e segundo, mesmo nos idiomas que o fazem, nem todas as chamadas recursivas necessariamente se anexam à pilha de chamadas, já que muitos idiomas suportam otimizações como como a eliminação da chamada final .) Entender a implementação usual / simples pode ser útil para controlar a abstração, mas você não deve se enganar pensando que é a história toda.
Ruakh 25/07/16
2
@ruakh Eu diria que uma função que é executada em espaço constante usando a eliminação de chamada de cauda realmente é um loop. Aqui a pilha não é o detalhe da implementação, é a abstração que permite acumular estados diferentes para diferentes níveis de recursão.
Cimbali
@ruakh: qualquer estado dentro de uma única chamada recursiva será armazenado em uma pilha implícita, a menos que a recursão possa ser convertida pelo compilador em um loop iterativo. A eliminação da chamada de cauda é um detalhe de implementação, o qual você precisa conhecer se deseja reorganizar sua função para ser recursiva da cauda. Além disso, "alguns desses idiomas não" - você pode fornecer um exemplo de idiomas que não precisam de uma pilha para chamadas recursivas?
Groo
11
@Groo: consulte en.wikipedia.org/wiki/Continuation-passing_style .
Ruakh 26/07
@ruakh: O CPS, por si só, cria a mesma pilha implícita, por isso deve contar com a eliminação de chamadas finais para fazer sentido (o que torna trivial devido à maneira como é construído). Até o artigo da wikipedia ao qual você vinculou diz o mesmo: Usar o CPS sem otimização de chamada de cauda (TCO) fará com que não apenas a continuação construída aumente potencialmente durante a recursão, mas também a pilha de chamadas .
Groo
7

Tudo depende do uso intrínseco do termo . No nível da linguagem de programação, eles são sintática e semanticamente diferentes e têm desempenho e uso de memória bastante diferentes. Mas se você se aprofundar o suficiente na teoria, elas podem ser definidas em termos uma da outra e, portanto, "são iguais" em algum sentido teórico.

A verdadeira questão é: quando faz sentido distinguir entre iteração (loops) e recursão e quando é útil pensar nela como as mesmas coisas? A resposta é que, ao programar de fato (ao contrário de escrever provas matemáticas), é importante distinguir entre iteração e recursão.

A recursão cria um novo quadro de pilha, ou seja, um novo conjunto de variáveis ​​locais para cada chamada. Isso tem sobrecarga e ocupa espaço na pilha, o que significa que uma recursão profunda o suficiente pode sobrecarregar a pilha, causando a falha do programa. A iteração, por outro lado, modifica apenas as variáveis ​​existentes, geralmente é mais rápida e ocupa apenas uma quantidade constante de memória. Portanto, essa é uma distinção muito importante para um desenvolvedor!

Em idiomas com recursão de chamada de cauda (normalmente idiomas funcionais), o compilador pode otimizar chamadas recursivas de maneira que elas ocupem apenas uma quantidade constante de memória. Nesses idiomas, a distinção importante não é a iteração x recursão, mas a versão sem cauda-recursão e a iteração.

Conclusão: você precisa saber a diferença, caso contrário, seu programa falhará.

JacquesB
fonte
3

whileloops são uma forma de recursão, veja, por exemplo, a resposta aceita para esta pergunta . Eles correspondem ao operador μ na teoria da computabilidade (veja, por exemplo, aqui ).

Todas as variações de forloops que iteram em um intervalo de números, uma coleção finita, uma matriz e assim por diante, correspondem à recursão primitiva, veja, por exemplo, aqui e aqui . Observe que os forloops de C, C ++, Java e assim por diante são na verdade açúcar sintático para um whileloop e, portanto, não correspondem à recursão primitiva. O forloop Pascal é um exemplo de recursão primitiva.

Uma diferença importante é que a recursão primitiva sempre termina, enquanto a recursão generalizada ( whileloops) pode não terminar.

EDITAR

Alguns esclarecimentos sobre comentários e outras respostas. "A recursão ocorre quando uma coisa é definida em termos de si mesma ou de seu tipo". (consulte a Wikipedia ). Tão,

Um loop while é intrinsecamente uma recursão?

Como você pode definir um whileloop em termos de si mesmo

while p do c := if p then (c; while p do c))

então, sim , um whileloop é uma forma de recursão. Funções recursivas são outra forma de recursão (outro exemplo de definição recursiva). Listas e árvores são outras formas de recursão.

Outra questão que é implicitamente assumida por muitas respostas e comentários é

Os loops while e as funções recursivas são equivalentes?

A resposta a esta pergunta é não : um whileloop corresponde a uma função recursiva de cauda, ​​em que variáveis ​​acessadas pelo loop correspondem aos argumentos da função recursiva implícita, mas, como outros já apontaram, funções não recursivas de cauda não pode ser modelado por um whileloop sem usar uma pilha extra.

Portanto, o fato de "um whileloop ser uma forma de recursão" não contradiz o fato de que "algumas funções recursivas não podem ser expressas por um whileloop".

Giorgio
fonte
2
@morbidCode: recursão primitiva e μ-recursão são formas de recursão com restrições específicas (ou falta delas), estudadas, por exemplo, na teoria da computabilidade. Acontece que uma linguagem com apenas um FORloop pode computar exatamente todas as funções recursivas primitivas, e uma linguagem com apenas um WHILEloop pode computar exatamente todas as funções recursivas µ (e as funções recursivas µ são exatamente aquelas funções que uma máquina de Turing pode calcular). Ou, para encurtar: recursão primitiva e recursão µ são termos técnicos da teoria da matemática / computabilidade.
Jörg W Mittag
2
Eu pensei que "recursão" implicava uma função que se chamava, resultando no estado de execução atual sendo empurrado para a pilha e assim por diante; portanto, a maioria das máquinas tem um limite prático de quantos níveis você pode obter. Embora os loops não tenham esses limites, eles usariam internamente algo como um "JMP" e não usariam a pilha. Apenas o meu entendimento, pode estar errado.
Jay
13
Esta resposta está usando uma definição completamente diferente para a palavra "recursiva" do que o OP estava usando e, portanto, é altamente enganadora.
Mooing Duck
2
@DavidGrinberg: Citação: "o C, C ++, Java para loops não é um exemplo de recursão primitiva. Recursividade primitiva significa que o número máximo de iterações / profundidade de recursão é corrigido antes de iniciar o loop." Giorgio está falando sobre as primitivas da teoria da computabilidade . Não relacionado a linguagens de programação.
Mooing Duck
3
Eu tenho que concordar com o Mooing Duck. Embora a teoria da computabilidade possa ser interessante no CS teórico, acho que todos concordam que o OP estava falando sobre o conceito de linguagens de programação.
Voo 24/07
2

Uma chamada de cauda (ou chamada recursiva de cauda) é implementada exatamente como um "ir com argumentos" (sem pressionar nenhum quadro de chamada adicional na pilha de chamadas ) e em algumas linguagens funcionais (notavelmente Ocaml) é a maneira usual de fazer um loop.

Portanto, um loop while (em idiomas que os possui) pode ser visto como terminando com uma chamada de cauda para o corpo (ou para o teste da cabeça).

Da mesma forma, chamadas recursivas comuns (sem chamada de cauda) podem ser simuladas por loops (usando alguma pilha).

Leia também sobre continuações e estilo de passagem de continuação .

Portanto, "recursão" e "iteração" são profundamente equivalentes.

Basile Starynkevitch
fonte
1

É verdade que tanto a recursão quanto os looping ilimitado são equivalentes em termos de expressividade computacional. Ou seja, qualquer programa gravado recursivamente pode ser reescrito em um programa equivalente usando loops e vice-versa. Ambas as abordagens são completas , ou podem ser usadas para calcular qualquer função computável.

A diferença fundamental em termos de programação é que a recursão permite que você use dados armazenados na pilha de chamadas. Para ilustrar isso, suponha que você queira imprimir os elementos de uma lista vinculada individualmente usando um loop ou recursão. Vou usar C para o código de exemplo:

 typedef struct List List;
 struct List
 {
     List* next;
     int element;
 };

 void print_list_loop(List* l)
 {
     List* it = l;
     while(it != NULL)
     {
          printf("Element: %d\n", it->element);
          it = it->next;
     }
 }

 void print_list_rec(List* l)
 {
      if(l == NULL) return;
      printf("Element: %d\n", l->element);
      print_list_rec(l->next);
 }

Simples, certo? Agora vamos fazer uma pequena modificação: imprima a lista na ordem inversa.

Para a variante recursiva, essa é uma modificação quase trivial da função original:

void print_list_reverse_rec(List* l)
{
    if (l == NULL) return;
    print_list_reverse_rec(l->next);
    printf("Element: %d\n", l->element);
}

Para a função de loop, porém, temos um problema. Nossa lista é vinculada individualmente e, portanto, só pode ser encaminhada para a frente. Mas, como estamos imprimindo no sentido inverso, precisamos começar a imprimir o último elemento. Quando alcançamos o último elemento, não podemos mais voltar ao penúltimo elemento.

Portanto, é necessário refazer a travessia ou construir uma estrutura de dados auxiliar que rastreie os elementos visitados e a partir da qual podemos imprimir com eficiência.

Por que não temos esse problema com recursão? Como na recursão, já temos uma estrutura de dados auxiliar: A pilha de chamadas de função.

Como a recursão nos permite retornar à chamada anterior da chamada recursiva, com todas as variáveis ​​locais e o estado dessa chamada ainda intactos, obtemos certa flexibilidade que seria tedioso para modelar no caso iterativo.

ComicSansMS
fonte
11
Obviamente, a segunda função recursiva não é recursiva de cauda - é muito mais difícil otimizar o espaço, pois você não pode usar o TCO para reutilizar a pilha. A implementação de uma lista duplamente vinculada tornaria os dois algoritmos triviais de qualquer maneira, ao custo do espaço de um ponteiro / referência por elemento.
precisa
@Baldrickk O engraçado da recursão de cauda é que você acaba com uma versão muito mais próxima da aparência da versão em loop, pois novamente remove sua capacidade de armazenar o estado na pilha de chamadas. Uma lista duplamente vinculada o resolveria, mas redesenhar a estrutura de dados geralmente não é uma opção ao se deparar com esse problema. Embora o exemplo aqui seja um pouco artificialmente restrito, ele ilustra um padrão que aparece frequentemente em linguagens funcionais no contexto de tipos algébricos recursivos.
ComicSansMS
Meu ponto era que, se você tiver este problema, é mais baixo a uma falta de design funcional, de que construções de linguagem que você usa para implementá-lo, e cada escolha tem seus próprios pontos positivos e negativos :)
Baldrickk
0

Os loops são uma forma especial de recursão para realizar uma tarefa específica (principalmente a iteração). Pode-se implementar um loop em um estilo recursivo com o mesmo desempenho [1] em várias línguas. e no SICP [2], você pode ver que os loops são descritos como "açúcar sintático". Na maioria das linguagens de programação imperativas, os blocos for e while estão usando o mesmo escopo que sua função pai. No entanto, na maioria das linguagens de programação funcionais, não existem nem nem nem existem loops porque não há necessidade deles.

A razão pela qual as linguagens imperativas têm loops for / while é que eles estão lidando com estados, modificando-os. Mas, na verdade, se você olhar de uma perspectiva diferente, se você pensar em um bloco while como uma função, pegar parâmetro, processá-lo e retornar um novo estado - que também poderia ser a chamada da mesma função com parâmetros diferentes - você pode pensar em loop como uma recursão.

O mundo também pode ser definido como mutável ou imutável. se definirmos o mundo como um conjunto de regras e chamarmos uma função suprema que tomará todas as regras e o estado atual como parâmetros, e retornaremos o novo estado de acordo com esses parâmetros com a mesma funcionalidade (gerar o próximo estado na mesma maneira), poderíamos dizer que é uma recursão e um loop.

no exemplo a seguir, life is the function usa dois parâmetros "rules" e "state", e um novo estado será construído na próxima vez que marcar.

life rules state = life rules new_state
    where new_state = construct_state_in_time rules state

[1]: a otimização de chamada de cauda é uma otimização comum em linguagens de programação funcional para usar a pilha de funções existente em chamadas recursivas, em vez de criar uma nova.

[2]: Estrutura e Interpretação de Programas de Computador, MIT. https://mitpress.mit.edu/books/structure-and-interpretation-computer-programs

zeawee
fonte
4
@ Giorgio Não é meu voto negativo, mas apenas um palpite: acho que a maioria dos programadores sente que a recursão implica em uma chamada de função recursiva, porque, bem, é isso que é a recursão, uma função que se chama. Em um loop, não há chamada de função recursiva. Dizer que um loop sem chamada de função recursiva é uma forma especial de recursão seria flagrantemente errado, se seguir essa definição.
Hyde
11
Bem, talvez olhar para ele de um ponto de vista mais abstrato, o que parecem ser coisas diferentes, seja na verdade conceitualmente o mesmo. Acho muito desanimador e triste pensar que as pessoas votam negativamente nas respostas apenas porque não correspondem às suas expectativas, em vez de tê-las como uma chance de aprender algo. Todas as respostas que tentam dizer: "Ei, veja, essas coisas parecem diferentes na superfície, mas na verdade são as mesmas em um nível mais abstrato" foram negadas.
Giorgio
3
@Georgio: O objetivo deste site é obter respostas para perguntas. Respostas úteis e corretas merecem votos positivos, respostas confusas e inúteis merecem votos negativos. Uma resposta que usa sutilmente uma definição diferente de um termo comum sem deixar claro que definição diferente é usada é confusa e inútil. As respostas que só fazem sentido se você já souber a resposta, por assim dizer, não são úteis e servem apenas para mostrar aos escritores uma compreensão superior da terminologia.
JacquesB
2
@ JacquesB: "Respostas que só fazem sentido se você já sabe a resposta, por assim dizer, não são úteis ...": Isso também pode ser dito de respostas que apenas confirmam o que o leitor já sabe ou pensa saber. Se uma resposta introduzir uma terminologia que não esteja clara, é possível escrever comentários para solicitar mais detalhes antes da votação.
Giorgio
4
Os loops não são uma forma especial de recursão. Veja a teoria da computabilidade e, por exemplo, a linguagem WHILE teórica e o cálculo µ. Sim, alguns idiomas usam loops como açúcar sintático para realmente usar a recursão nos bastidores, mas podem fazer isso porque a recursão e a iteração são igualmente expressivas , não porque são iguais.
Polygnome
-1

Um loop while é diferente de recursão.

Quando uma função é chamada, ocorre o seguinte:

  1. Um quadro de pilha é adicionado à pilha.

  2. O ponteiro de código se move para o início da função.

Quando um loop while está no final, ocorre o seguinte:

  1. Uma condição pergunta se algo é verdadeiro.

  2. Nesse caso, o código pula para um ponto.

Em geral, o loop while é semelhante ao seguinte pseudocódigo:

 if (x)

 {

      Jump_to(y);

 }

Mais importante, recursão e loops têm diferentes representações de código de montagem e representações de código de máquina. Isso significa que eles não são os mesmos. Eles podem ter os mesmos resultados, mas o código de máquina diferente prova que não são 100% a mesma coisa.

O grande pato
fonte
2
Você está falando sobre a implementação de uma chamada de procedimento e de um loop while e, como eles são implementados de maneira diferente, você conclui que eles são diferentes. No entanto, conceitualmente, são muito semelhantes.
Giorgio
11
Dependendo do compilador, uma chamada de recursão otimizada e embutida pode produzir o mesmo assembly, como loop simples.
Hyde
@hyde ... que é apenas um exemplo do fato conhecido de que um pode ser expresso através do outro; não significa que eles são idênticos. Um pouco como massa e energia. É claro que se pode argumentar que todas as formas de produzir resultados idênticos são "iguais". Se o mundo fosse finito, todos os programas seriam finalizados.
Peter - Restabelece Monica
@Giorgio Nah, é uma descrição lógica, não uma implementação. Sabemos que as duas coisas são equivalentes ; mas equivalência não é identidade , porque a pergunta (e as respostas) é exatamente como chegamos ao resultado, ou seja, elas contêm necessariamente descrições algorítmicas (que podem ser expressas em termos de pilha e variável etc.).
Peter - Restabelece Monica
11
@ PeterA.Schneider Sim, mas esta resposta indica "Mais importante de tudo ... código de montagem diferente", o que não está certo.
Hyde
-1

Apenas a iteração é insuficiente para ser geralmente equivalente à recursão, mas a iteração com uma pilha é geralmente equivalente. Qualquer função recursiva pode ser reprogramada como um loop iterativo com uma pilha e vice-versa. No entanto, isso não significa que seja prático e, em qualquer situação específica, uma ou outra forma pode ter benefícios claros sobre a outra versão.

Não sei por que isso é controverso. Recursão e iteração com uma pilha são o mesmo processo computacional. Eles são o mesmo "fenômeno", por assim dizer.

A única coisa em que consigo pensar é que, ao considerá-las "ferramentas de programação", eu concordaria que você não deveria pensar nelas como a mesma coisa. Eles são equivalentes "matematicamente" ou "computacionalmente" (novamente iteração com uma pilha , não iteração em geral), mas isso não significa que você deva abordar problemas com o pensamento de que qualquer um deles fará. Do ponto de vista da implementação / resolução de problemas, alguns problemas podem funcionar melhor de uma maneira ou de outra, e seu trabalho como programador é decidir corretamente qual é o mais adequado.

Para esclarecer, a resposta para a pergunta O loop while é intrinsecamente uma recursão? é um não definitivo , ou pelo menos "não, a menos que você tenha uma pilha também".

Dave Cousineau
fonte