A recursividade é, sem dúvida, um dos temas mais fascinantes da programação. Ao contrário das funções iterativas, que dependem de estruturas de repetição como for ou do while, as funções recursivas nos permitem realizar ciclos sem a necessidade de recorrer a essas estruturas, utilizando apenas estruturas condicionais.

Sim, é possível criar um loop que "substitua" as funções iterativas usando apenas estruturas condicionais. Embora possa parecer complexo à primeira vista, diria que é apenas uma questão de prática - como tudo na programação. Basicamente, as funções recursivas seguem um padrão semelhante às funções iterativas, incluindo uma condição de parada, incremento ou decremento, e o elemento diferenciador: a chamada sucessiva.

Com isso em mente, gostaria de destacar quatro pontos fundamentais sobre funções recursivas:

• Toda função recursiva deve possuir uma condição de paragem;
• O valor inicial da iteração deve ser incializado fora da função;
• A função recursiva deve realizar um processo de incremento ou decremento para se aproximar da condição de paragem;
• A função deve fazer chamadas sucessivas de si mesma.

Embora existam outros aspectos a serem considerados, neste artigo focaremos exclusivamente nesses quatro princípios.

Vamos agora visualizar um exemplo de comparação entre esses dois tipos de função.

Observe aqui essas duas funções para achar o fatorial de um número:

Iteratividade

 
  int fat(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
    	result *= i;
    }
    return result;
  }
 

Agora observe a mesma função de forma recursiva.

Recursividade

 
  int fat(int n) {
    if (n == 0 || n == 1) return 1;
    return n * fat(n - 1);
  }
 

A diferença é notória. O número de linha na função recursiva foi uma provocação da minha parte, mas repare que respeitamos as 4 notas propostas no princípio.

• A condição de paragem ocorre quando n é igual a 0 ou 1, onde a função retorna imediatamente 1;
• O valor inicial da iteração é qualquer número inteiro n passado como parametro para a função fat;
• Repare que a cada nova chamada temos n - 1, ou seja, é retirado um valor a cada nova chamada da função;
• A chamada sucessiva ocorre dentro da própria função fat, onde ela se chama recursivamente com n - 1 até que a condição de paragem seja atendida..

Você pode estar se preguntando: Mas por quê usar funções recursivas se as iterativas funcionam?

Podemos começar explicando que a recursividade não é uma opção obrigatória, ou seja, você é livre para usar recursividade ou não. No exemplo anterior não existia uma grande necessidade de usarmos recursividade, já que a iteratividade seria a suloção mais "familiar".

Não necessariamente existem problemas que só podem ser resolvidos com recursividade, mas há problemas em que a recursividade é uma abordagem natural e eficiente para sua resolução. No entanto, existe uma teoria que afirma que: qualquer problema que pode ser resolvido de forma recursiva também pode ser resolvido de forma iterativa, e vice-versa. Isso é conhecido como o princípio da equivalência entre recursão e iteração.

Alguns casos em que a recursão é mais recomendada:

• Travessia de estruturas de dados recursivas: Estruturas de dados como árvores e listas ligadas podem ser eficientemente percorridas usando recursão. Por exemplo, a travessia de uma árvore binária ou uma lista ligada pode ser feita de forma recursiva.
• Problemas dividir e conquistar: Algoritmos baseados na técnica de dividir e conquistar, como mergesort, quicksort e busca binária, muitas vezes são mais facilmente implementados de forma recursiva.
• Problemas de pombinação e permutação: Problemas que envolvem combinações e permutações de elementos, como gerar todas as combinações de um conjunto de elementos, são naturalmente tratados de forma recursiva.
• Problemas de Grafos: Algoritmos para a busca em profundidade (DFS) e a busca em largura (BFS) em grafos são comumente implementados de forma recursiva

Esses são apenas alguns dos vários casos em que a recursividade é amplamente recomendável.

Entender a recursividade é uma habilidade valiosa que todo programador deve dominar!

Conclusão

Embora muitos problemas possam ser resolvidos tanto de forma recursiva quanto iterativa, a recursão é especialmente útil em situações onde a estrutura do problema se alinha naturalmente com a abordagem recursiva, como em travessias de estruturas de dados recursivas ou problemas de divisão e conquista.

No entanto, é essencial compreender os princípios fundamentais da recursão e avaliar cuidadosamente o problema e verificar se a situação poderia ser melhorada com recursividade.

Obrigado!