Introdução:
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.
Conceito geral sobre recursão:
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.
Diferenças entre recursão e laço de repetição:
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:
Utilizando a técnica de recursão para a mesma solução:
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:
Agora olhe que interessante quando comparamos a performance das estruturas utilizando o TimeIt do python:
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:
Quando utilizar laço e quando utilizar recursão:
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
Top comments (0)