O loop while é intrinsecamente uma recursão?

Os loops não são muito não recursivos. Na verdade, eles são o principal exemplo do mecanismo oposto : iteração .

O ponto de recursão é que um elemento de processamento chama outra instância de si mesmo. A maquinaria de controle de loop simplesmente pula 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 de loop ainda tem o mesmo valor que tinha antes do salto. Mas se você chamar outra instância da rotina em que está, então a nova instância tem 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 que muitos algoritmos recursivos funcionem, e é por isso que você não pode emular a recursão por meio da iteração sem também gerenciar uma pilha de quadros chamados que registra todos esses valores.

Dizer que X é intrinsecamente Y só faz sentido se você tem algum sistema (formal) em mente que você está expressando X dentro. Se você definir a semântica de while em termos do cálculo lambda, você pode mencionar recursão*; se você defini-lo em termos de uma máquina registradora, você 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ê defini-lo em termos de fold .

Isso depende do seu ponto de vista.

Se você olhar para a teoria da computabilidade , a iteração e a recursão são igualmente expressivas . O que isto significa é que você pode escrever uma função que calcula algo, e não importa se você o faz recursivamente ou iterativamente, você será capaz de escolher ambas as abordagens. Não há nada que você possa calcular recursivamente, o qual você não pode 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, , a recursão significa que o compilador / linguagem lida com a pilha de chamadas, e iteração significa que você pode ter que lidar com as pilhas sozinho.

No entanto, existem linguagens - especialmente linguagens funcionais - em que coisas como loops (for, while) são de fato apenas açúcar sintático para recursão e implementadas por trás do cenas dessa maneira. Isso geralmente é desejável em linguagens funcionais, porque elas geralmente não têm o conceito de loop, e adicioná-lo tornaria seu cálculo mais complexo, por uma pequena razão prática.

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

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

Se você olhar de um ponto de vista da implementação , a recursão e a iteração não serão as mesmas. A recursão cria um novo quadro de pilha para cada chamada. Cada passo da recursão é independente, obtendo os argumentos para a computação do próprio receptor.

Os loops, por outro lado, não criam quadros de chamada. 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, já que pode fazer diferenças bastante radicais no mundo real. Para recursão, todo o contexto deve ser salvo em todas as chamadas. Para a iteração, você tem um controle preciso sobre quais variáveis estão na memória e o que é salvo no local.

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 possuem 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 prova . 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 a iteração e a redução da quantidade de quadros de pilha de chamadas podem economizar muita memória necessária.

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

Um loop while que "chama a si mesmo no final" não tem nenhuma pilha para rastrear quando terminar. É a última iteração que define o estado que será quando terminar.

No entanto, 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 conceder acesso a uma pilha explicitamente. Mas fazer assim 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 ideia de um modo completamente diferente do código iterativo. O código iterativo faz as coisas um passo de cada vez. Aceita qualquer estado que veio antes e só funciona para criar o próximo estado.

O código recursivo divide um problema em fractais. Essa pequena parte parece ser a parte mais importante para que possamos fazer exatamente isso e da mesma maneira. É uma maneira diferente de pensar em problemas. É muito poderoso e demora para se acostumar. Muito pode ser dito em poucas linhas. Você simplesmente não pode tirar isso de um loop while, mesmo que tenha acesso a uma pilha.

Tudo depende do seu uso do termo intrinsecamente . 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ê cavar fundo o suficiente na teoria, eles podem ser definidos em termos um do outro, e é, portanto, "o mesmo" em algum sentido teórico.

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 pode sobrecarregar a pilha, o que causa a falha do programa. A iteração, por outro lado, apenas modifica as variáveis existentes, de modo que é geralmente mais rápida e ocupa apenas uma quantidade constante de memória. Então, essa é uma distinção muito importante para um desenvolvedor!

Em idiomas com recursão tail-call (tipicamente linguagens funcionais), o compilador pode otimizar as chamadas recursivas de tal forma que elas só ocupam uma quantidade constante de memória. Nessas linguagens, a distinção importante não é a iteração versus a recursão, mas a recursão e recursão da chamada não-recursiva da cauda.

Conclusão: você precisa ser capaz de dizer a diferença, caso contrário, o seu programa irá falhar.

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

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

Uma diferença importante é que a recursão primitiva sempre termina, enquanto a recursão generalizada ( while loops) não pode 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." (veja wikipedia ). Então,

Is a while loop intrinsically a recursion?

Como você pode definir um loop while em termos de si mesmo

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

então, sim , um loop while é 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 implicitamente assumida por muitas respostas e comentários é

Are while loops and recursive functions equivalent?

A resposta para esta pergunta é no : Um loop while corresponde a uma função recursiva final, onde as variáveis acessadas pelo loop correspondem aos argumentos da função recursiva implícita, mas , como outros apontaram, funções recursivas não-tail não podem ser modeladas por um loop while sem usar uma pilha extra.

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

Uma chamada final (ou chamada recursiva final) é implementada exatamente como um "goto com argumentos" (sem pressionar nenhum adicional quadro de chamadas na pilha de chamadas ) e em alguns idiomas funcionais (Ocaml notavelmente) é o maneira usual de looping.

Assim, um loop while (em linguagens com eles) pode ser visto como terminando com uma chamada final para seu corpo (ou seu teste de cabeça).

Da mesma forma, chamadas recursivas comuns (chamadas não-finais) podem ser simuladas por loops (usando alguma pilha).

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

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

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

A diferença fundamental em termos de programação é que a recursão permite que você faça uso de dados que são armazenados na pilha de chamadas. Para ilustrar isso, suponha que você queira imprimir os elementos de uma lista vinculada individualmente usando um loop ou uma recursão. Usarei 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, esta é uma modificação quase trivial para a 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 loop, porém, temos um problema. Nossa lista é ligada individualmente e, portanto, só pode ser percorrida para frente. Mas como estamos imprimindo ao contrário, precisamos começar a imprimir o último elemento. Quando chegamos ao último elemento, não podemos mais voltar ao segundo para o último elemento.

Por isso, temos que fazer um grande número de retrocessos, ou temos que construir uma estrutura de dados auxiliares que rastreie os elementos visitados e a partir dos quais possamos imprimir com eficiência.

Por que não temos esse problema com recursão? Porque na recursão já temos uma estrutura de dados auxiliares: a pilha de chamadas de funções.

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, ganhamos alguma flexibilidade que seria entediante modelar no caso iterativo.

Os loops são uma forma especial de recursão para alcançar uma tarefa específica (principalmente iteração). Pode-se implementar um loop em um estilo recursivo com o mesmo desempenho [1] em vários idiomas. 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, para e enquanto os blocos estão usando o mesmo escopo de sua função pai. No entanto, na maioria das linguagens de programação funcionais não existem nem nem existem ciclos porque não há necessidade deles.

A razão pela qual linguagens imperativas têm loops / while é que elas estão manipulando estados, alterando-as. Mas, na verdade, se você olhar de uma perspectiva diferente, se pensar em um bloco while como uma função em si, pegando o parâmetro, processando-o e retornando um novo estado - que poderia também ser a chamada da mesma função com parâmetros diferentes 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 final que tome todas as regras, e o estado atual como parâmetros, e retornar o novo estado de acordo com esses parâmetros que tenham a mesma funcionalidade (gerar o próximo estado no mesmo podemos dizer que é uma recursão e um loop.

No exemplo a seguir, a vida é a função leva dois parâmetros "regras" e "estado", e novo estado será construído no próximo tempo tick.

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

[1]: a otimização da chamada final é uma otimização comum em linguagens de programação funcionais 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. link

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 do 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. Se sim, o código salta para um ponto.

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

 if (x)

 {

      Jump_to(y);

 }

Apenas iteração é insuficiente para ser geralmente equivalente a recursão, mas iteração com uma pilha é geralmente equivalente. Qualquer função recursiva pode ser reprogramada como um loop iterativo com uma pilha e vice-versa. Isso não significa que é prático, no entanto, e em qualquer situação particular, 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 como "ferramentas de programação", eu concordaria que você não deveria pensar nelas como a mesma coisa. Eles são "matematicamente" ou "computacionalmente" equivalentes (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 que qualquer um fará. Do ponto de vista da implementação / solução de problemas, alguns problemas podem funcionar melhor de uma forma ou de outra, e seu trabalho como programador é decidir corretamente qual deles é mais adequado.

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