Você está fazendo isso errado! Tópico #2

 Fala galera! Como estão todos? Sejam bem-vindos ao primeiro post de 2021.

Continuando o tema "Você está fazendo isso errado", vamos ao tópico #2, onde falaremos do uso da recursividade.

Não lembro exatamente a primeira vez que vi o recurso recursividade sendo explicado (acho que foi numa aula de Programação I - tenho a impressão que não vi esse recurso nas aulas de algoritmos), mas lembro que fiquei impressionado, tanto pelo recurso em si, quanto como a palavra recursividade se encaixava bem ao propósito do recurso.

Pois bem, já perdi as contas de quantas vezes escrevi algoritmos baseados em recursividade, então vai novamente a ressalva, pessoal, de que o objetivo deste post não é cravar a regra "não use recursividade", mas sim, avalie se a recursividade realmente é a melhor solução para o seu algoritmo.

A verdade é que, para fins de leitura e simplificação de código, a recursividade muito mais agrega do que prejudica. Normalmente códigos recursivos são simples e elegantes.

A recursividade começa a se tornar um problema a partir do momento que não sabemos ou não é possível determinar quantas vezes a função vai chamar a si mesma (direta ou indiretamente), e não levar isso em consideração pode gerar um gargalo absurdo nos nossos algoritmos.

Sei que o exemplo que vou usar é batido: Descobrir o valor de uma determinada posição na sequência de Fibonacci. Todavia, neste caso em específico, não temos motivo para reinventar a roda, pois o exemplo demonstra claramente três coisas:

• O quanto um código pode ficar mais legível com recursividade;
• O quanto a performance pode cair ao usarmos recursividade;
• Recursividade não necessariamente é a única solução para alguns problemas.

Vamos começar analisando a implementação recursiva para Fibonacci:

1 2 3 4 5 6 7

class function TFibonacci.GetValorDaPosicao(const pPosicao: UInt32): UInt32; begin if pPosicao < 2 then Result := pPosicao else Result := GetValorDaPosicao(pPosicao - 1) + GetValorDaPosicao(pPosicao - 2); end;

É um código claro, que representa exatamente como a sequência é calculada ou até mesmo explicada para alguém que está sendo apresentado à sequência de Fibonacci.

Vamos agora dar uma olhada em como o algoritmo pode ser implementado de forma iterativa, eliminando a recursividade:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class function TFibonacci.GetValorDaPosicaoSemRecursividade(pPosicao: UInt32): UInt32; begin if pPosicao < 2 then Result := pPosicao else begin var lUltimaPosicao: UInt32 := 1; Result := 1; while pPosicao > 2 do begin Inc(Result, lUltimaPosicao); lUltimaPosicao := Result - lUltimaPosicao; Dec(pPosicao); end; end; end;

Alguém ficou em dúvida de quanto um código é mais simples que o outro? 😝   A diferença é gritante! Bom, para trocar a primeira opção pela segunda, é bom ter um bom motivo, não é?

Nas apresentações do "Você está fazendo isso errado" em eventos, eu expliquei o problema, a sua origem, e também como resolver o mesmo, mas, em nenhuma das apresentações eu citei números para demonstrar a queda de performance. Pois bem, aqui vamos ver números (lembrando que esses números são específicos para cada caso, e aqui estamos falando da recursividade e complexidade gerada para resolver a sequência de Fibonacci).

Antes dos números, vamos contextualizar que, para realizar este tipo de teste de performance, é importante reduzir ao máximo a quantidade de variáveis. Para isso, os algoritmos acima foram compilados em um exe de 64 bits configurado como release, e este executável foi testado em um servidor que estava ocioso durante os testes, conferindo assim um ambiente mais uniforme possível para os testes. Também é importante dizer que as medidas de performance foram executadas somente durante o processamento da lógica de negócio em si, não considerando atualizações visuais que usei como saída dos resultados. Por fim, os números demonstrados abaixo são as médias obtidas em 3 execuções de cada um dos cenários testados.

Sem mais delongas, vamos aos números:

Posição	Resultado	Recursivo		Não Recursivo
		Tempo (ms)	Ticks	Tempo (ms)	Ticks
0	0	< 1	44	< 1	41
3	2	< 1	47	< 1	41
8	21	< 1	51	< 1	42
15	610	< 1	96	< 1	50
20	6.765	< 1	556	< 1	44
25	75.025	< 1	5.486	< 1	41
30	832.040	5	55.810	< 1	42
35	9.227.465	40	403.651	< 1	49
40	102.334.155	433	4.331.396	< 1	46
43	433.494.437	1.813	18.131.228	< 1	52
44	701.408.733	2.938	29.383.621	< 1	49
45	1.134.903.170	4.714	47.141.376	< 1	49

Vamos às conclusões...

Durante a busca por posições iniciais (até a posição 8), a performance de ambos os algoritmos é muito semelhante, ao ponto das variações nos resultados estarem mais ligadas à variáveis que não temos controle (como o escalonamento de processos do Windows) do que qualquer outro fator.

Já a partir da busca pela posição 15 em diante, a performance do algoritmo recursivo começa a degradar significativamente. Na busca pela posição 15, especificamente, ainda estamos na faixa de tempo abaixo do 1ms, mas a quantidade de ticks já começa a apresentar o problema. Claro que daí para frente a deterioração é exponencial, na mesma base da evolução da sequência de Fibonacci (aproximadamente 1,618 - O(1,618 na potência n) - o que fica comprovado ao analisarmos as últimas 3 linhas da tabela).

Em contrapartida, a complexidade do algoritmo iterativo é linear (obviamente), sendo que, para as buscas apresentadas nesta tabela, as variações não estão relacionadas à variável n, mas às mesmas variáveis citadas dois parágrafos acima.

E então? O que acharam? É bom ter atenção aos detalhes dos algoritmos, não?

Abraço e até a próxima!!!