Como resolver a sequência de Fibonacci com Golang?
Heeeey gopheeers! Nesse post vou demonstrar algumas possíveis soluções da Sequência de Fibonnaci com o uso da linguagem mais queridinha de todas: Go. Só que mais do que simplesmente solucionar esse problema matemático, vamos falar também sobre alguns assuntos quentíssimos e super necessários para a evolução de qualquer pessoa desenvolvedora na profissão que são:
- Recursão
- Complexidade de Algoritmos
- Programação dinâmica (ou recursão com uma tabela (ou simplesmente cache))
- Go (que é por isso que estamos aqui também, né não?)
Antes de mergulhar nessa leitura junto comigo, talvez você passe os olhos nos títulos/imagens e logo pense “ó céus, que assunto difícil, deixa pra lá”. Informo a todes que esse assunto é mais simples do que parece e requer conhecimentos básicos em Go e Matemática para ser compreendido. Bora lá?
Um pouco de história: que raios é sequência de Fibonacci?
Conhecida como um dos padrões mais famosos da matemática, a sequência de Fibonacci ajudou a revolucionar a nossa relação com a matemática como a conhecemos hoje. Em 1202 o matemático italiano Leonardo de Pisa, descreveu a sequência de Fibonacci em sua pesquisa usando o crescimento de uma população de coelhos com base em um primeiro casal. Contudo, é possível presenciar a sequência de Fibonacci em padrões da natureza, no mercado financeiro, na arquitetura, na arte e até na programação. E essa é nossa deixa para focar no objetivo desse post, que é calcular o valor de qualquer número Fibonacci (mas sinta-se à vontade de se perder nesse assunto fascinante que é Fibonacci e a proporção áurea 🥰).
“A matemática é o alfabeto no qual Deus escreveu o universo” — Galileu Galilei
Vamos usar a fórmula abaixo, descrita pelo próprio Leonardo de Pisa:
F(n) = F(n-1) + F(n-2)
Leonardo também descreve nos seus estudos as seguintes constantes que inicia a sequência:
F(0)=0 e F(1)=1
Bora codar!
A tal solução recursiva — O(n) de espaço e O(n²) de tempo
A primeira solução que deve vir à mente, principalmente quando você já tem alguma familiaridade com recursividade, é transcrever a fórmula que nos foi dada diretamente para o código. Para ficarmos na mesma página, a definição de recursividade é:
“Em ciência da computação, a recursividade é a definição de uma sub-rotina (função ou método) que pode invocar a si mesma” — Wikipedia
Dito isso, aplicando a fórmula do mesmo jeitinho em que ela é descrita deixaria seu código mais ou menos parecido com o que vemos a seguir:
Nessa primeira interação vou testar se, ao passar como parâmetro o valor das constantes definidas pelo Fibonacci, irá retornar o valor delas como resultado. Ou seja, se o valor passado por parâmetro for 0 ou 1, o mesmo valor será retornado pela função. Caso o valor passado por parâmetro não seja de uma constante, vamos fazer duas chamadas recursivas a função Fibonacci, que representa a fórmula: F(n) = F(n-1) + F(n-2)
Então se eu rodar esse código pra qualquer valor de n≤30 (n menor que 30), ele vai funcionar que é uma beleza. Dá uma olhada:
Mas para n≥30 (n maior que 30), o tempo para executar a função recursiva e a quantidade de memória que será consumida irão aumentar, uma vez que para calcular o valor final, vamos precisar guardar todos os valores até as extremidades da árvore. Dá uma olhada nas evidências:
Isso acontece porque a cada vez que entramos na função Fibonacci(n) e o número é maior que 1, a função é chamada ao menos 2 vezes recursivamente. No caso que n=5, vamos ter 15 chamadas para a função Fibonacci(5) chegar a um resultado final. Ilustrei a pilha de chamadas na imagem a seguir:
Seguindo a ordem da pilha de chamadas, de cima pra baixo, da direita para esquerda, teremos a seguinte ordem de execução:
Fibonacci(5)→Fibonacci(4)→Fibonacci(3)→Fibonacci(2)→Fibonacci(1)→Fibonacci(0)→Fibonacci(1)…
e assim sucessivamente, até terminar as 15 chamadas.
Nessa mesma lógica, se n=40 , então a quantidade de vezes que a função Fibonacci(n) vai ser chamada será de 331.160.281 😱.
Uma pitada de complexidade de algoritmos
A complexidade desse algoritmo é definida da seguinte forma:
- O(n) para o espaço: porque a cada interação com a função Fibonacci(n), vamos ter que guardar todas as chamadas da nossa pilha até chegar a base, que é F(1) = 1 ou F(0)=0, para só em seguida esvaziar a pilha. Esse não é o pior dos casos, porque só guardamos o que vamos de fato utilizar.
- O(n²) para tempo: Como disse anteriormente, a cada vez que chamamos a função Fibonacci(n) haverão duas chamadas recursivas para essa mesma função, a medida que o número que passamos para a função Fibonacci(n) aumenta, a árvore e a quantidade de operações crescem em uma proporção de n².
Para nossa necessidade, vamos parar por aqui sobre complexidade de algoritmos. Comenta aí embaixo se quer aprofundar no assunto, que posso fazer um outro post dedicado a isso 😉
Mas a pergunta que não quer calar é: Dá pra melhorar? Dá!
Programação dinâmica: Top Down — O(n) de espaço e O(n) de tempo
Você deve ter notado que apesar da solução recursiva ser bem limpa em relação a quantidade de linhas de código, se nos atentarmos à árvore, é possível notar que a mesma função é chamada diversas vezes. Ao calcular Fibonacci(5), a função Fibonacci(2) é chamada 3 vezes, olha só:
Você pode imaginar que a medida que a quantidade de vezes aumenta, o número de chamadas para cada nó da árvore também aumenta. Veja só o que acontece se n=40:
Na imagem acima podemos ver em destaque que a Fibonacci(38) foi chamada 2 vezes, Fibonacci(37) foi chamada 3 vezes. Repare que à medida que nos aprofundamos na árvore, o número de n diminui e a quantidade de chamadas aumenta. Aqui está o link do repositório com os testes que foram executados acima :)
Bem, para otimizar nosso algoritmo, vamos usar uma técnica chamada de Programação Dinâmica.
Programação dinâmica é um método para a construção de algoritmos para a resolução de problemas computacionais, em especial os de otimização combinatória. Ela é aplicável a problemas nos quais a solução ótima pode ser computada a partir da solução ótima previamente calculada e memorizada — de forma a evitar recálculo — de outros subproblemas que, sobrepostos, compõem o problema original. — Wikipedia
Observe o código abaixo:
Nesse código, na linha 5, inicializamos uma variável do tipo map que tem um índice de inteiros e vai guardar inteiros também. Ao inicializar esse map, guardamos os valores base que recebemos da fórmula, 0 e 1.
Em seguida, chamamos a função auxiliar computeCache, que vai passar a ser nossa função de recursão. O objetivo dessa função é primeiramente verificar se o valor passado por parâmetro existe, através da instrução if value, found := cache[number]; found, que está na linha 14.
Importante: Se você ainda não conhece essa instrução MA-RA-VI-LHO-SA de verificação de chaves em variáveis do tipo map, super recomendo esse artigo da Digital Ocean sobre o assunto ;)
A variável found representa se o número foi encontrado ou não. Se o valor de cache[number] já existir, não vamos precisar passar novamente pela pilha inteira da função Fibonacci(n), e a variável value será retornada pela nossa função computeCache.
Mas caso o valor ainda não exista, e somente nessa situação, a chamada da função recursiva será executada 😃. A única diferença aqui, é que vamos guardar o valor do retorno das execuções da função na variável cache para uso posterior (se necessário).
E como uma imagem (ou um gif 😆) dizem mais que mil palavras:
Vamos olhar com carinho pro gif acima, afinal, deu um trabalhão pra fazer 😅😅. O nosso algoritmo continua fazendo chamadas recursivas, então continuamos tendo uma pilha de chamadas que vai começar em N(sendo que no nosso desenho n=5) e vão continuar até que n=0. A única diferença, e a mais importante, é que não vamos ter pilhas duplicadas, pois vamos usar a programação dinâmica para guardar os valores em memória (cache).
Mais uma pitada de complexidade de algoritmos
A complexidade desse algoritmo é definida da seguinte forma:
- O(n) para o espaço: Continua sendo O(n) , pois vamos precisar de uma variável de cache, que vai aumentar a medida que n aumentar.
- O(n) para tempo: O grande impacto dessa mudança será no tempo que o algoritmo vai gastar pra ser processado, pois como o número de chamadas diminuiu, a quantidade de tempo para processar esse algoritmo também vai diminuir 🙃.
Programação dinâmica: Bottom Up — O(n) de espaço e O(n) de tempo
Vamos ao último algoritmo. Observe o código abaixo:
Nesse último algoritmo, a ordem em que vamos fazer as coisas muda um pouco. Como no código anterior, vamos continuar usando um cache para os valores e vamos inicializá-lo com os valores base que recebemos da fórmula, 0 e 1. Contudo, ao invés de iniciar o preenchimento do cache a partir do último índice (que é definido pela variável number), esse código inicializa pelo início da matriz 😉.
Logo após inicializar o cache, vamos iterar até o valor que recebemos por parâmetro (number). É importante notar que não começamos do primeiro valor do cache, mas sim do terceiro índice através da definição i := 2, pois os índices 0 e 1 estão sendo inicializados antes de começar o for . Por fim, vamos executar sucessivamente a soma do último valor do cache com o penúltimo valor do cache, até chegar ao resultado de cache[number], que é o valor que será retornado pela função.
Em relação a complexidade de algoritmos, nada muda se comparar com o código anterior, pois vamos continuar tendo o mesmo número de interações e consumindo o mesmo espaço em memória para realizar o processamento de Fibonacci(5), por conta da variável cache que está guardando o valor das operações pra gente.
Contudo, consegue perceber algum ganho aqui? O terceiro código é muito mais legível e compreensível aos olhos humanos. E não me entenda errado, recursividade é incrivelmente útil, mas para resolver esse problema, não precisamos de uma função recursiva — e a removendo, deixamos nosso código mais acessível e objetivo 😉.
Bônus — O(1) 😱 de espaço e O(n) de tempo
Há ainda uma última solução para esse algoritmo 😁. Bora analisar esse código:
A única diferença entre esse código e o anterior é que esse código não utiliza nenhum cache para guardar o resultado das operações. Isso porque como o objetivo é retornar apenas o resultado de $Fibonacci(number)$ não precisamos guardar a sequência inteira, então precisamos lidar apenas com as variáveis auxiliares $penultResult$ e $lastResult$ para guardar os resultados da última e da penúltima operação .
Essa simples mudança faz com que a complexidade do algoritmo em relação ao espaço seja $O(1)$ 💃!!! O motivo é que sem a variável de cache, não vai importar se $n=2$ ou $n=9876543219$, o algoritmo vai ocupar a mesma quantidade de espaço em memória, independente do número de operações que ele vai executar.
Moral da história
Existem diversas maneiras de resolver o mesmo problema, como vimos aqui com a sequencia de Fibonacci, no entanto a solução completa vai além de retornar o resultado certo ao fim da função. Variáveis como tempo, espaço e principalmente legibilidade do código importam demais para criar um algoritmo (sobre esse último ponto, indico a leitura do #2 princípio da engenharia aqui da RD Station).
Pensa assim: se a premissa do problema fosse de que n<=30, o primeiro algoritmo que criamos já resolveria o problema, certo? Mas como você pode garantir a acessibilidade dele para as pessoas programadoras que poderão fazer manutenção no futuro? (considere que cada uma delas possui um nível de conhecimento diferente do seu). Não conseguimos garantir que nenhum bug vai ser criado, mas podemos contar uma história mais fluída das nossas soluções através das linhas de códigos que escrevemos 😃.
Primeiramente obrigada por chegar até aqui! Espero que esse post tenha sido útil para seus estudos 🤗. O código que você leu está no meu github e coberto de testes, recomendo demais que você vá lá dar uma estrela mergulhar nesse conteúdo incrível gratuito. Aproveita e já curte esse post pra liberar minha endorfina e me estimular a fazer mais posts como esse (tô brincando (mas é verdade!😁))).
E se você estiver procurando novos desafios para sua carreira e um ambiente bacana para se desenvolver, chega mais que nós temos várias oportunidades abertas, cada uma com um desafio diferente :)
Por hoje é isso pessoal! Bora interagir nos comentários! Pode mandar sugestões, críticas e perguntas, que é na troca que o conhecimento acontece!
