A recursão é cada vez mais rápida que o loop?

Sei que a recursão às vezes é muito mais limpa do que o loop, e não estou perguntando nada sobre quando devo usar a recursão sobre a iteração, sei que já existem muitas perguntas sobre isso.

O que estou perguntando é: a recursão é cada vez mais rápida que um loop? Para mim, parece que você sempre seria capaz de refinar um loop e fazê-lo executar mais rapidamente do que uma função recursiva, porque o loop está ausente constantemente configurando novos quadros de pilha.

Estou procurando especificamente se a recursão é mais rápida em aplicativos em que a recursão é a maneira correta de lidar com os dados, como em algumas funções de classificação, em árvores binárias etc.

Isso depende do idioma que está sendo usado. Você escreveu 'independente da linguagem', então vou dar alguns exemplos.

Em Java, C e Python, a recursão é bastante cara em comparação com a iteração (em geral) porque requer a alocação de um novo quadro de pilha. Em alguns compiladores C, pode-se usar um sinalizador de compilador para eliminar essa sobrecarga, que transforma certos tipos de recursão (na verdade, certos tipos de chamadas finais) em saltos, em vez de chamadas de função.

Nas implementações funcionais da linguagem de programação, às vezes, a iteração pode ser muito cara e a recursão, muito barata. Em muitos, a recursão é transformada em um salto simples, mas alterar a variável do loop (que é mutável) às vezes requer algumas operações relativamente pesadas, especialmente em implementações que suportam vários encadeamentos de execução. A mutação é cara em alguns desses ambientes devido à interação entre o mutador e o coletor de lixo, se ambos estiverem em execução ao mesmo tempo.

Eu sei que em algumas implementações de esquema, a recursão geralmente será mais rápida do que o loop.

Em suma, a resposta depende do código e da implementação. Use o estilo que você preferir. Se você estiver usando uma linguagem funcional, a recursão poderá ser mais rápida. Se você estiver usando uma linguagem imperativa, a iteração provavelmente será mais rápida. Em alguns ambientes, os dois métodos resultam na geração da mesma montagem (coloque-a no seu cachimbo e fume).

Adendo: Em alguns ambientes, a melhor alternativa não é recursão nem iteração, mas funções de ordem superior. Isso inclui "mapa", "filtro" e "redução" (também chamado de "dobra"). Esses estilos não são apenas os preferidos, além de frequentemente serem mais limpos, mas em alguns ambientes essas funções são as primeiras (ou únicas) a obter um impulso da paralelização automática - para que possam ser significativamente mais rápidas que a iteração ou a recursão. O Data Parallel Haskell é um exemplo desse ambiente.

A compreensão de lista é outra alternativa, mas geralmente são apenas açúcar sintático para funções de iteração, recursão ou ordem superior.

a recursão é cada vez mais rápida que um loop?

Não, a iteração sempre será mais rápida que a recursão. (em uma arquitetura Von Neumann)

Explicação:

Se você criar as operações mínimas de um computador genérico a partir do zero, a "Iteração" vem primeiro como um bloco de construção e consome menos recursos do que a "recursão", e a ergo é mais rápida.

Construindo uma pseudo-máquina de computação a partir do zero:

Pergunte a si mesmo : O que você precisa para calcular um valor, ou seja, seguir um algoritmo e alcançar um resultado?

Estabeleceremos uma hierarquia de conceitos, começando do zero e definindo em primeiro lugar os conceitos básicos e básicos, depois construindo conceitos de segundo nível com esses e assim por diante.

1. Primeiro conceito: células de memória, armazenamento, estado . Para fazer algo, você precisa de lugares para armazenar valores de resultado finais e intermediários. Vamos supor que temos uma matriz infinita de células "inteiras", chamadas Memória , M [0..Infinito].

2. Instruções: faça alguma coisa - transforme uma célula, altere seu valor. alterar estado . Toda instrução interessante realiza uma transformação. As instruções básicas são:

   a) Definir e mover células de memória

   • armazena um valor na memória, por exemplo: armazena 5 m [4]
   • copie um valor para outra posição: por exemplo: armazenar m [4] m [8]

   b) Lógica e aritmética

   • e, ou, xor, não
   • adicionar, sub, mul, div. por exemplo, adicione m [7] m [8]

3. Um agente de execução : um núcleo em uma CPU moderna. Um "agente" é algo que pode executar instruções. Um agente também pode ser uma pessoa seguindo o algoritmo no papel.

4. Ordem dos passos: uma sequência de instruções : ie: faça isso primeiro, faça depois, etc. Uma sequência imperativa de instruções. Mesmo as expressões de uma linha são "uma sequência imperativa de instruções". Se você tiver uma expressão com uma "ordem de avaliação" específica, terá etapas . Isso significa que mesmo uma única expressão composta possui "etapas" implícitas e também possui uma variável local implícita (vamos chamá-la de "resultado"). por exemplo:

   4 + 3 * 2 - 5
   (- (+ (* 3 2) 4 ) 5)
   (sub (add (mul 3 2) 4 ) 5)  
   

   A expressão acima implica 3 etapas com uma variável implícita "resultado".

   // pseudocode
   
          1. result = (mul 3 2)
          2. result = (add 4 result)
          3. result = (sub result 5)
   

   Portanto, mesmo expressões infix, como você tem uma ordem específica de avaliação, são uma sequência imperativa de instruções . A expressão implica uma sequência de operações a serem feitas em uma ordem específica e, como existem etapas , também há uma variável intermediária implícita "resultado".

5. Ponteiro de instrução : Se você tiver uma sequência de etapas, também terá um "ponteiro de instrução" implícito. O ponteiro da instrução marca a próxima instrução e avança após a leitura da instrução, mas antes da execução da instrução.

   Nesta pseudo-máquina de computação, o ponteiro de instruções faz parte da memória . (Nota: normalmente o ponteiro de instruções será um "registro especial" no núcleo da CPU, mas aqui simplificaremos os conceitos e assumiremos que todos os dados (registros incluídos) fazem parte de "Memória")

6. Pular - Depois de ter um número ordenado de etapas e um ponteiro de instruções , você pode aplicar a instrução " armazenar " para alterar o valor do ponteiro de instruções. Chamaremos esse uso específico de instrução de loja com um novo nome: Jump . Usamos um novo nome porque é mais fácil pensar nele como um novo conceito. Alterando o ponteiro de instruções, instruímos o agente a "ir para a etapa x".

7. Iteração Infinita : Ao voltar, agora você pode fazer o agente "repetir" um certo número de etapas. Neste ponto, temos iteração infinita.

                      1. mov 1000 m[30]
                      2. sub m[30] 1
                      3. jmp-to 2  // infinite loop
   

8. Condicional - Execução condicional de instruções. Com a cláusula "condicional", você pode executar condicionalmente uma das várias instruções com base no estado atual (que pode ser definido com uma instrução anterior).

9. Iteração adequada : Agora, com a cláusula condicional , podemos escapar do loop infinito da instrução de retorno . Agora temos um loop condicional e, em seguida, iteração adequada

   1. mov 1000 m[30]
   2. sub m[30] 1
   3. (if not-zero) jump 2  // jump only if the previous 
                           // sub instruction did not result in 0
   
   // this loop will be repeated 1000 times
   // here we have proper ***iteration***, a conditional loop.
   

10. Nomeação : atribuir nomes a um local específico da memória contendo dados ou mantendo uma etapa . Esta é apenas uma "conveniência" de ter. Não adicionamos novas instruções por ter a capacidade de definir "nomes" para locais de memória. "Nomear" não é uma instrução para o agente, é apenas uma conveniência para nós. A nomeação torna o código (neste ponto) mais fácil de ler e mais fácil de alterar.

       #define counter m[30]   // name a memory location
       mov 1000 counter
    loop:                      // name a instruction pointer location
        sub counter 1
        (if not-zero) jmp-to loop  
    

11. Sub-rotina de um nível : suponha que haja uma série de etapas que você precisa executar com freqüência. Você pode armazenar as etapas em uma posição nomeada na memória e, em seguida, pular para essa posição quando precisar executá-las (chamada). No final da sequência, você precisará retornar ao ponto de chamada para continuar a execução. Com esse mecanismo, você cria novas instruções (sub-rotinas) compondo as instruções principais.

    Implementação: (não são necessários novos conceitos)

    • Armazene o ponteiro de instruções atual em uma posição de memória predefinida
    • pule para a sub-rotina
    • no final da subrotina, você recupera o ponteiro de instruções do local predefinido da memória, retornando efetivamente à instrução a seguir da chamada original

    Problema com a implementação em um nível : Você não pode chamar outra sub-rotina a partir de uma sub-rotina. Se o fizer, substituirá o endereço de retorno (variável global), para não aninhar chamadas.

    Para ter uma melhor implementação de sub-rotinas: Você precisa de uma PILHA

12. Pilha : você define um espaço de memória para funcionar como uma "pilha", pode "empurrar" os valores na pilha e também "pop" o último valor "empurrado". Para implementar uma pilha, você precisará de um ponteiro de pilha (semelhante ao ponteiro de instruções) que aponta para o "cabeçalho" real da pilha. Quando você pressiona um valor, o ponteiro da pilha diminui e você armazena o valor. Quando você "pop", você obtém o valor no ponteiro da pilha real e, em seguida, o ponteiro da pilha é incrementado.

13. Sub-rotinas Agora que temos uma pilha , podemos implementar sub-rotinas adequadas, permitindo chamadas aninhadas . A implementação é semelhante, mas em vez de armazenar o Ponteiro de Instruções em uma posição de memória predefinida, "pressionamos" o valor do IP na pilha . No final da sub-rotina, apenas "pop" o valor da pilha, retornando efetivamente à instrução após a chamada original . Essa implementação, ter uma “pilha” permite chamar uma sub-rotina de outra sub-rotina. Com essa implementação, podemos criar vários níveis de abstração ao definir novas instruções como sub-rotinas, usando instruções principais ou outras sub-rotinas como blocos de construção.

14. Recursão : o que acontece quando uma sub-rotina se chama? Isso é chamado de "recursão".

    Problema: Substituindo os resultados intermediários locais que uma sub-rotina pode estar armazenando na memória. Como você está chamando / reutilizando as mesmas etapas, se o resultado intermediário for armazenado em locais de memória predefinidos (variáveis ​​globais), eles serão substituídos nas chamadas aninhadas.

    Solução: Para permitir recursão, as sub-rotinas devem armazenar resultados intermediários locais na pilha ; portanto, a cada chamada recursiva (direta ou indireta), os resultados intermediários são armazenados em diferentes locais da memória.

...

tendo atingido a recursão , paramos aqui.

Conclusão:

Em uma arquitetura de Von Neumann, claramente "Iteração" é um conceito mais simples / básico que "Recursão" .Temos uma forma de "Iteração" no nível 7, enquanto "Recursão" está no nível 14 da hierarquia de conceitos.

A iteração sempre será mais rápida no código da máquina, pois implica menos instruções e, portanto, menos ciclos de CPU.

Qual é o melhor"?

• Você deve usar a "iteração" quando estiver processando estruturas de dados sequenciais simples e em todos os lugares um "loop simples" funcionará.

• Você deve usar "recursão" quando precisar processar uma estrutura de dados recursiva (gosto de chamá-los de "estruturas de dados fractal") ou quando a solução recursiva for claramente mais "elegante".

Conselho : use a melhor ferramenta para o trabalho, mas entenda o funcionamento interno de cada ferramenta para escolher com sabedoria.

Por fim, observe que você tem muitas oportunidades de usar recursão. Você tem estruturas de dados recursivas em todos os lugares, agora está vendo uma: partes do DOM que suportam o que você está lendo são um RDS, uma expressão JSON é um RDS, o sistema de arquivos hierárquico no seu computador é um RDS, ou seja: você um diretório raiz, contendo arquivos e diretórios, todo diretório que contém arquivos e diretórios, cada um desses diretórios que contém arquivos e diretórios ...

A recursão pode muito bem ser mais rápida quando a alternativa é gerenciar explicitamente uma pilha, como nos algoritmos de classificação ou de árvore binária mencionados.

Eu tive um caso em que reescrever um algoritmo recursivo em Java tornou mais lento.

Portanto, a abordagem correta é primeiro escrevê-la da maneira mais natural, otimizar apenas se a criação de perfis mostrar que é crítica e depois medir a suposta melhoria.

A recursão da cauda é tão rápida quanto o loop. Muitas linguagens funcionais possuem recursão de cauda implementada nelas.

Considere o que absolutamente deve ser feito para cada iteração e recursão.

• iteração: um salto para o início do loop
• recursão: um salto para o início da função chamada

Você vê que não há muito espaço para diferenças aqui.

(Presumo que a recursão seja uma chamada final e o compilador esteja ciente dessa otimização).

A maioria das respostas aqui esquece o culpado óbvio por que a recursão geralmente é mais lenta que as soluções iterativas. Ele está vinculado à criação e desmontagem de quadros de pilha, mas não é exatamente isso. Geralmente, há uma grande diferença no armazenamento da variável automática para cada recursão. Em um algoritmo iterativo com um loop, as variáveis ​​geralmente são mantidas em registradores e, mesmo se derramarem, residirão no cache do Nível 1. Em um algoritmo recursivo, todos os estados intermediários da variável são armazenados na pilha, o que significa que eles gerarão muito mais derramamentos na memória. Isso significa que, mesmo que faça a mesma quantidade de operações, ele terá muitos acessos à memória no hot loop e, o que piora, essas operações de memória têm uma taxa de reutilização ruim, tornando os caches menos eficazes.

Os algoritmos recursivos TL; DR geralmente apresentam um comportamento de cache pior do que os iterativos.

A maioria das respostas aqui estão erradas . A resposta certa é que depende . Por exemplo, aqui estão duas funções C que percorrem uma árvore. Primeiro, o recursivo:

static
void mm_scan_black(mm_rc *m, ptr p) {
    SET_COL(p, COL_BLACK);
    P_FOR_EACH_CHILD(p, {
        INC_RC(p_child);
        if (GET_COL(p_child) != COL_BLACK) {
            mm_scan_black(m, p_child);
        }
    });
}

E aqui está a mesma função implementada usando a iteração:

static
void mm_scan_black(mm_rc *m, ptr p) {
    stack *st = m->black_stack;
    SET_COL(p, COL_BLACK);
    st_push(st, p);
    while (st->used != 0) {
        p = st_pop(st);
        P_FOR_EACH_CHILD(p, {
            INC_RC(p_child);
            if (GET_COL(p_child) != COL_BLACK) {
                SET_COL(p_child, COL_BLACK);
                st_push(st, p_child);
            }
        });
    }
}

Não é importante entender os detalhes do código. São apenas pnós e isso P_FOR_EACH_CHILDfaz a caminhada. Na versão iterativa, precisamos de uma pilha explícitast na qual os nós são enviados por push e, em seguida, pop-up e manipulados.

A função recursiva roda muito mais rápido que a iterativa. O motivo é que, no último, para cada item, é necessário um CALLpara a função st_pushe depois outro parast_pop .

No primeiro, você só tem o recurso recursivo CALL para cada nó.

Além disso, acessar variáveis ​​no callstack é incrivelmente rápido. Isso significa que você está lendo da memória, que provavelmente sempre estará no cache mais interno. Uma pilha explícita, por outro lado, deve ser apoiada pormalloc : memória ed do heap, que é muito mais lenta para acessar.

Com otimização cuidadosa, como inlining st_pushest_pop , posso alcançar uma paridade aproximada com a abordagem recursiva. Mas, pelo menos no meu computador, o custo de acessar a memória heap é maior que o custo da chamada recursiva.

Mas essa discussão é principalmente discutida porque o passeio recursivo pelas árvores está incorreto . Se você tiver uma árvore grande o suficiente, ficará sem espaço de pilha de chamadas, motivo pelo qual um algoritmo iterativo deve ser usado.

Em geral, não, a recursão não será mais rápida que um loop em qualquer uso realista que tenha implementações viáveis ​​em ambas as formas. Quero dizer, com certeza, você pode codificar loops que levam uma eternidade, mas existem maneiras melhores de implementar o mesmo loop que podem superar qualquer implementação do mesmo problema via recursão.

Você bate no prego na cabeça em relação ao motivo; criar e destruir quadros de pilha é mais caro do que um simples salto.

No entanto, observe que eu disse que "tem implementações viáveis ​​nas duas formas". Para coisas como muitos algoritmos de classificação, tende a não haver uma maneira muito viável de implementá-los que não configura efetivamente sua própria versão de uma pilha, devido à geração de "tarefas" filho que são inerentemente parte do processo. Assim, a recursão pode ser tão rápida quanto tentar implementar o algoritmo via loop.

Editar: Esta resposta está assumindo linguagens não funcionais, onde os tipos de dados mais básicos são mutáveis. Não se aplica a linguagens funcionais.

Em qualquer sistema realista, não, criar um quadro de pilha sempre será mais caro que um INC e um JMP. É por isso que bons compiladores transformam automaticamente a recursão final em uma chamada para o mesmo quadro, ou seja, sem sobrecarga, para que você obtenha a versão mais legível da fonte e a versão compilada mais eficiente. Um compilador muito, muito bom deve ser capaz de transformar a recursão normal em recursão final, sempre que possível.

A programação funcional é mais sobre "o que " e não " como ".

Os implementadores de linguagem encontrarão uma maneira de otimizar como o código funciona por baixo, se não tentarmos torná-lo mais otimizado do que o necessário. A recursão também pode ser otimizada nos idiomas que suportam a otimização da chamada de cauda.

O que importa mais do ponto de vista do programador é legibilidade e manutenção, em vez de otimização em primeiro lugar. Mais uma vez, "a otimização prematura é raiz de todo mal".

Isso é um palpite. Geralmente, a recursão provavelmente não supera o loop frequentemente ou nunca em problemas de tamanho decente, se ambos estiverem usando algoritmos realmente bons (sem contar a dificuldade de implementação); pode ser diferente se usada com uma linguagem com recursão de chamada de cauda (e um algoritmo recursivo de cauda) e com loops também como parte do idioma) - que provavelmente teriam muito semelhantes e possivelmente até prefeririam recursão algumas vezes.

Segundo a teoria, são as mesmas coisas. Recursão e loop com a mesma complexidade O () funcionarão com a mesma velocidade teórica, mas é claro que a velocidade real depende da linguagem, compilador e processador. Exemplo com potência de número pode ser codificado de maneira iterativa com O (ln (n)):

  int power(int t, int k) {
  int res = 1;
  while (k) {
    if (k & 1) res *= t;
    t *= t;
    k >>= 1;
  }
  return res;
  }