Um resumo sobre: recursão.
Tags: python, algorithms
Published: 2023-02-28 19:55:55

**<u>Introdução:</u>**
Neste resumo irei dar uma breve explicação sobre recursão e mostrar a diferença entre ela e o laço de repetição. Sendo assim, aqui irei abordar os seguintes tópicos:
- Conceito geral sobre recursão;
- Diferenças entre recursão e laço de repetição; 
- Quando utilizar laço e quando utilizar recursão.

**<u>Conceito geral sobre recursão:</u>**


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/diyjcx2tc9vvq4jvrre2.png)

Muito utilizada em estruturas mais complexas, **a recursão ocorre quando uma função chama ela mesma até a sua resolução**. Dessa maneira, é utilizada quando é necessário fazer uma repetição de tarefas, mas que um laço de repetição não é adequado. Essa imagem do Bob Esponja, representa muito bem a ideia de recursão e em que tipo de estrutura devemos utilizá-la. 

**<u>Diferenças entre recursão e laço de repetição:</u>**

Antes de partirmos para exemplos práticos, vamos pensar em problemas do dia a dia da programação. Vamos supor que você precisa contar a quantidade de comentários de uma postagem, entretanto cada comentário permite a inserção de outro comentário e esse comentário do comentário, pode ter um outro comentário nele e assim por diante. Problemas assim que a recursão pode ser uma mão na roda. Além desses, problemas básicos como fatorial ou exponenciação também podem ser resolvidos com recursão. 

Veremos alguns exemplos práticos:

Utilizando laço de repetição:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ocspzis6w3c8z0b2sjog.png)


Utilizando a técnica de recursão para a mesma solução:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/t81ypz8p1nuey2cqb8pn.png)


Repare que na recursão precisamos ter uma variável que irá controlar a quantidade de chamadas, uma vez que se não houver, a recursão será infinita. 
Lembrando que quando nós fazemos essas chamadas da função no retorno, essas funções vão entrando na pilha de processamento. Quando terminar essas chamadas, as funções irão desempilhando(FILO - first in last out) uma a uma.


Repare agora outro exemplo da diferença entre um laço de repetição e uma função recursiva:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/t3zaa5d9or50hbxamwo2.png)

Agora olhe que interessante quando comparamos a performance das estruturas utilizando o [TimeIt](https://dev.to/costamateus7/um-resumo-sobre-big-o-2hpk#:~:text=No%20python%2C%20h%C3%A1%20uma%20biblioteca%20chamada%20timeit%2C%20uma%20das%20funcionalidades%20dela%20%C3%A9%20calcular%20o%20tempo%20de%20execu%C3%A7%C3%A3o%20de%20um%20algoritmo) do python:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/z7qp45nfmlipu8iqkhkq.png)

A recursão neste caso é menos performática do que o laço, sendo quase o dobro do tempo do laço. Isso, pode se dar ao fato da recursão empilhar as chamadas e desempilhá-las após o término das chamadas e também do laço agir de forma linear sem o empilhamento da estrutura.

Portanto, uma função recursiva ela: 

- Chama ela mesma;
- Precisa ser controlada para não gerar um looping.
- A cada chamada ela se aproxima do fim;


Dentro da recursão podemos ter a recursão direta (quando uma função chama ela mesma), recursão indireta (quando ela chama outra função e essa outra função chama ela novamente), função recursiva em cauda (quando a chamada da recursividade é a última a ser executada) e por último temos a função non-tail recursive (função sem cauda).

Deixarei mais dois algoritmos utilizando recursão em Python. O primeiro calcula o fatorial e o segundo calcula o exponencial:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6hgokke7hy0dk9yf72gi.png)


**<u>Quando utilizar laço e quando utilizar recursão:</u>**

Por fim, utilizamos recursão quando:

- O problema pode ser dividido em subproblemas menores e idênticos ao problema original.
- A solução do problema original depende da solução dos subproblemas menores.
- A estrutura de dados subjacente ao problema é naturalmente recursiva, como árvores ou grafos.
- A recursão torna a solução mais fácil de entender e manter
.

Utilizamos laço quando: 

- O problema não pode ser facilmente dividido em subproblemas menores.
- A solução do problema não depende da solução de subproblemas menores.
- A estrutura de dados subjacente ao problema é linear, como uma lista ou matriz.
- O desempenho é uma consideração importante, já que a recursão pode ser mais lenta do que o loop devido ao overhead (custo adicional) da pilha de chamadas.



Caso tenha alguma sugestão sobre o tema, mande mensagem. Será muito bom evoluir com sua ajuda! Obrigado por chegar até aqui e espero ter ajudado!

Este resumo é baseado no curso: [Estruturas de dados e algoritmos em python](https://www.udemy.com/course/estrutura-de-dados-e-algoritmos-python-guia-completo/)