A recursividade sobrecarga — é muito grave?[duplicado]

Question

Possíveis Duplicados:
É a recursão sempre mais rápido do que o loop?

Fui treinado a sério o programa em C, há cerca de 15 anos.Meu patrão queria código altamente otimizado para computação de tarefas difíceis.Lembro-me de ser avisado mais de uma vez para reescrever recursions como loops, mesmo com a cara de legibilidade, a fim de evitar a "recursividade sobrecarga." Como eu entendi, então, a recursividade sobrecarga foi o esforço extra necessário para envio de dados em uma pilha e, mais tarde, colocá-lo fora.

Agora eu o código em C, Python, Perl, e, às vezes, Java, e às vezes me pergunto sobre recursões.Ainda existe algo a ser ganho por reescrevê-los?O que se está a cauda recursions?Temos os modernos compiladores fez todas essas simulado de questões?São tais preocupações irrelevantes para linguagens interpretadas?

Answer 1

A recursão pode levar a uma sobrecarga significativa se o kernel da função recursiva for menos caro computacionalmente do que o código de entrada/saída da função e o custo da própria chamada. A melhor maneira de descobrir é simplesmente perfilar duas versões do código - uma recursiva e uma não.

Dito isto, se a sua idéia de evitar a recursão é fazer uma estrutura semelhante a uma pilha, cuidado - pode não ser necessariamente mais rápido do que a abordagem recursiva mais direta. Novamente, o perfil é seu amigo.

Por fim, lembre -se de que o tempo do programador é mais caro que o tempo da CPU. Antes de micro-otimizar seu código, é realmente uma boa idéia medir para ver se realmente será um problema.

Answer 2

É sério.A maioria das línguas que eu código de ter um custo real para chamadas de função (os compiladores para eles geralmente podem fazer com recursão, bem assim às vezes não é um problema).

Que custo, e o fato de que a pilha não é um recurso ilimitado, geralmente faz-me tendem a usar recursão somente para casos onde eu sei que há um limite de profundidade, pode ir para.

Por exemplo, eu sei de uma equilibrada árvore binária de pesquisa só vai cinqüenta níveis de profundidade para um quadrilhão de entradas.Eu não iria, no entanto, utilizar:

def sum1through (n):
    if n == 0 return 0
    return n + sum1through (n-1)

uma vez que fazer para que n vinte milhões de não ser saudável para uma pilha.

Answer 3

O problema ainda existe.Recursão tem um monte de espaço de pilha, como cada vez que o método se chama a si própria, um ponteiro para ele e suas variáveis locais são gerados novamente.O número de chamadas de função feita durante a recursão faz um tempo O(n) o uso de memória;comparado a O(1) de uma não-função recursiva, como loops.

Answer 4

Eu não acho que nenhum dos idiomas que você mencionou exigir que a plataforma/compilador implementa Eliminação de chamadas de cauda. Você pode encontrar idiomas que Faz requer essa otimização - a maioria dos idiomas funcionais tem esse requisito.

No entanto, outra coisa que você precisa considerar é que os computadores se tornaram ordens de magnitudes mais rapidamente do que eram 15 anos atrás, por isso é muito mais raro agora, antes que você precise se preocupar com micro-otimizações. Um programa que, 15 anos atrás, pode ter exigido uma otimização cuidadosa das mãos no assembler para obter desempenho decente, pode funcionar incrivelmente rápido em um computador moderno, mesmo se escrito em um idioma de nível superior, como o Java. Isso não quer dizer que o desempenho nunca seja mais um problema - mas você deve se concentrar em escolher o algoritmo correto e ao escrever legível código. Faça apenas micro-otimizações depois de medir o desempenho e você pode ver que o código em questão é o gargalo.

Uma coisa você Faz Precisa se preocupar com o que está transbordando da pilha. Se houver algum risco de que isso aconteça, pode valer a pena reescrever uma função recursiva de maneira iterativa.

Answer 5

As pessoas dizem muitas coisas tolas sobre desempenho.

1. Se você precisar Recursão, gostaria de fazer uma caminhada de árvores em profundidade, então você precisa, então use-a.

2. Antes de se preocupar com o desempenho de nada, descubra se você tem um problema e onde está.
   Problemas de desempenho são como vigaristas e trapaceiros - eles são especializados em estar onde você menos espera; portanto, se você estiver preocupado com algo específico como recursão, é quase garantido que se preocupe com a coisa errada.

Na minha opinião, a melhor maneira de encontrar problemas de desempenho é por amostragem de pilha na hora do relógio de parede, e Examinando as amostras para ver o que o programa está fazendo, não apenas obtendo medições e imaginando o que elas significam.

Dito isto, se você encontrar 10% ou mais de tempo entrando em uma chamada recursiva, e nada mais acontece dentro da rotina recursiva, e você poderá loop, depois o loop provavelmente ajudará.