Entendendo Algoritmos - Segunda Semana
Tags: beginners, programming, hacktoberfest, algorithms
Published: 2023-10-17 13:29:58


## Recapitulando...

Na semana passada, tivemos o primeiro contato com algoritmos de ordenação e busca binária(você pode conferir [aqui](https://dev.to/loremimpsu/entendendo-algoritmos-primeira-semana-5fmn)). 

## Recursividade


![recursividade](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0bevq3bjy5tlv5ejjckp.png)



A recursividade é uma ferramenta de programação que utiliza a reutilização do bloco de código para criar um processo de repetição de uma rotina de código. O conceito pode ser complexo, mas é apenas a criação de um laço a partir de um trecho de código e não de uma estrutura. 
Caso você queira se aprofundar no assunto de recursão:

- [recursividade](https://carlacastanho.github.io/Material-de-APC/aulas/aula14.html);

Um exemplo clássico de recursividade é a torre de hanoi. Sim, aquele brinquedinho de bebê. A torre de hanoi é o melhor exercício de recursividade que você pode treinar. Se você quer uma ajuda com a torre de hanoi:
- [como resolver a torre de hanoi - freecodecamp](https://www.freecodecamp.org/portuguese/news/como-resolver-o-problema-da-torre-de-hanoi-um-guia-ilustrado-do-algoritmo/)

![torre de hanoi](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/e4n6u8af9vtcj9zdjmls.png)

## Pilha de recursão 

Ao trabalhar com recursividade, temos a necessidade de trabalhar com a pilha de recursão. Nós já estudamos pilhas como estrutura de dados no [capítulo anterior](https://dev.to/loremimpsu/entendendo-algoritmos-primeira-semana-5fmn). Hoje vemos uma estrutura semelhante, só que trabalhando com o empilhamento das chamadas de uma função recursiva. Para se aprimorar mais, temos:
- [pilha recursiva](https://www.mundojs.com.br/2019/06/23/recursao-e-a-pilha-stack/)

Um exemplo de utilização ao máximo da pilha de recursividade, temos o caso do fibonacci. Ela se vale da pilha para calcular uma resposta. Vamos dar uma olhada mais afundo no algoritmo de fibonacci:
- [algoritmo de fibonacci](http://devfuria.com.br/logica-de-programacao/recursividade-fibonacci/)

![fibonacci](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kdikijvelsu5woj57f8k.png)

## Algoritmo de divisão e conquista e Quicksort

O algoritmo de divisão e conquista é um algoritmo que trata a divisão de um problema em vários probleminhas de mais fácil resolução. Baseado no algoritmo de euclides, que também é um dos algoritmos matemáticos interessantes para o estudo. 
- [algoritmo de euclides](https://pt.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm#:~:text=O%20Algoritmo%20Euclidiano%20para%20encontrar,e%20podemos%20parar%20a%20verifica%C3%A7%C3%A3o.)

![algoritmo de euclides](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2pdi4cza8vl20ntogfu7.png)

O algoritmo de divisão e conquista é a base de vários outros algoritmos, incluido o Quicksort, que foi o algoritmo estudado pelo livro. Se você quer saber mais sobre o quicksort, acesse:

-[quicksort](https://joaoarthurbm.github.io/eda/posts/quick-sort/)

Além do Quicksort, há um segundo algoritmo muito importante, o Mergesort. O mergesort é um dos algoritmos mais pedidos em provas técnicas, pois ele te promete um algoritmo de custo baixo **O(nlogn)**, com um bonus de não exceder tanto a memória demandada. O quick é relativamente mais rápido, porém gasta muito com o recurso de memória, onde o merge entra para ajudar. Para saber mais sobre o mergesort, acesse:

-[mergesort](https://joaoarthurbm.github.io/eda/posts/merge-sort/)

Em uma classe diferente de algoritmos de ordenação, temos um algoritmo famoso pelo seu baixo custo, o counting sort. Seu custo é estimado em **O(n + k)** onde **k** seria uma constante calculada através do tamanho da lista. Ou seja, se a lista tem 10 elementos o custo do algoritmo seria O(n + 10). Um ótimo algoritmo, com um crescimento linear, não é? sim, mas como tudo que é bom tem seu preço, o algoritmo countingsort vai cobrar na memória utilizada. Para saber mais sobre este algoritmo, dá uma olhada neste material:

-[countingsort](https://joaoarthurbm.github.io/eda/posts/ordenacao-linear/)

O coutingsort tem variações, que melhoram este problema de memória. O bucketsort e o radixsort. Eles irão trabalhar com estruturas de dados auxiliares que já vimos no [capítulo anterior](https://dev.to/loremimpsu/entendendo-algoritmos-primeira-semana-5fmn), linkedlist e arraylist, para fazer essa otimização. Para saber mais sobre, acessem: 
-[bucketsort  e radixsort](https://algoritmosempython.com.br/cursos/algoritmos-python/pesquisa-ordenacao/bucket-radix/)


## Tabelas hash

Se você já programa a algum tempo, já deve ter topado com a estrutura de dados Map, ou dictionary, ou simplesmente tabela hash. Mas porque ela é tão importante? A tabela hash nos garante o acesso a um valor salvo e catalogado anteriormente ao preço de O(1). Ou seja, o acesso é instantâneo. Isso se dá pelo método em que traduzimos o valor da chave (key) em um endereço de memória e salvamos o seu conteúdo no valor resultante. Este método de calculo chama hashcode. Se você que saber mais alguns detalhes sobre a tabela e como fazer um hashcode, olha o link:

- [tabela hash](https://joaoarthurbm.github.io/eda/posts/hashtable/) 

## Conclusão

A maioria dos assuntos aqui são um incremento ao assunto principal abordado no livro atual do clube do livro. Caso você não esteja acompanhando o livro, mas se interesse sobre os assunto, até o momento temos estes artigos lançados:

- [Entendendo algoritmos - introdução](https://dev.to/loremimpsu/entendendo-algoritmos-introducao-53f0)

- [Entendendo algoritmos - primeira semana](https://dev.to/loremimpsu/entendendo-algoritmos-primeira-semana-5fmn)

Caso queira acompanhar nosso clube na leitura do livro, se sinta convidado a entrar para o discord:

- [Link do convite](https://discord.gg/DWDGjacWyM)

Caso queira adquirir o livro, peça pelo nosso link. O valor adquirido pelo link de patrocinado vai ser revertido a livros para pessoas de baixa visão ou que tenham alguma deficiência para a utilização de meios ... não ortodoxos de leitura. 

- [Link do livro - Entendendo algoritmos](https://amzn.to/3tD028z)