Um loop while é intrinsecamente uma recursão?

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?

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.

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.

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.

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.

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á.

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".

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.

É 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.

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

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.

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".