DEV Community

Mateus Costa
Mateus Costa

Posted on • Updated on

Um resumo sobre: recursão.

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:

Image description

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:

Image description

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

Image description

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

Agora olhe que interessante quando comparamos a performance das estruturas utilizando o TimeIt do python:

Image description

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

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)