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:

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