Recursividade

PSEUDOCODIGO bubble sort switch case

Continuando a série de artigos sobre Algoritmos, agora que já aprendemos sobre funções, é hora de aprender um pouco sobre Recursividade. Neste artigo apresentarei uma introdução ao assunto, de forma mais objetiva e até mesmo mais simplista, porém o necessário para você poder programar usando este recurso.

Conceito e Processo Recursivo

Em termos gerais, a recursão pode ser considerada como um processo de repetição de uma rotina. Portanto, de maneira bem simplista, pode ser definida como uma rotina (procedimento ou função) que chama a si mesma, de forma direta ou indireta.

Bem, se a rotina chama a si mesma inúmeras vezes, é preciso então tomar muito cuidado com o LOOP. Acredito que todos já tenham ouvido falar desse termo, mas esclarecendo para quem não está acostumado. Um LOOP ocorre quando uma parte do código fica repetindo eternamente, ocasionando o travamento do sistema todo.

Para que um LOOP não ocorra é necessário definir uma condição de terminação de forma correta pois, às vezes, até mesmo a condição de terminação pode ser a causa do LOOP. Portanto, é preciso analisar e avaliar bem o problema que está sendo resolvido de forma recursiva e como ele deverá terminar, sem entrar em LOOP.

É denominada Recursão Direta uma rotina que é formada por um conjunto de comandos e uma chamada a ela mesma. É denominada Recursão Indireta uma rotina que contém uma chamada a outra rotina que, por sua vez, tem uma chamada a outra rotina e assim sucessivamente, portanto, rotinas diferentes.

Uma função recursiva é chamada para resolver um problema, o qual ela sabe como resolver somente a “parte” mais simples, o “caso” mais trivial. Portanto, a solução para um problema recursivo normalmente pode ser dividida em duas partes: uma em que a solução é trivial, e outra em que a solução é mais geral.

Dessa forma, a recursão aplica uma técnica chamada divisão e conquista, que funciona mais ou menos assim: se o problema a ser resolvido é muito grande, o divida em dois; se ainda permanece grande, divida em dois novamente; e assim sucessivamente, até chegar em algo o mais simples possível.

No caso da recursão, ela sabe como resolver uma parte do problema, mas outra parte ela não tem muita certeza, então, a recursão vai dividindo o problema em duas partes sucessivamente: a primeira em que ela sabe como resolver e a segunda que ela não sabe como resolver, sendo esta semelhante ao problema original, que se está tentando resolver, mas deve ser uma versão mais simples ou menor. Dessa forma temos:

Caso Trivial: Fácil de se resolver e retorna um resultado, geralmente é o caso mais básico, ou simples, do problema, inclusive não há necessidade de se aplicar recursão.

Caso Geral: Neste caso, o problema é, em sua essência, igual ao problema original, porém deve ser uma versão mais genérica. Como esse novo problema é parecido com o original, a rotina chama uma nova cópia de si mesma para trabalhar no problema menor.

Enquanto for necessário dividir o problema em problemas menores, a função recursiva continuará chamando a si mesma, para continuar dividindo, até chegar no caso mais básico e, quando isso ocorre, a função para de dividir e começa a gerar os resultados. Todos os dados de todas as variáveis envolvidas na função recursiva devem ser guardados a cada chamada, isso significa que uma pilha de chamadas da função deve ser criada.

Quando a função começa a retornar os resultados (retornos das chamadas) então temos o desempilhamento das chamadas da função da pilha de controle de chamadas e retornos da função recursiva, que retornarão a quem chamou o resultado solicitado. Esse resultado é agrupado com o próximo e assim sucessivamente, até formar o resultado final. Conforme são desempilhados, os valores também são liberados da memória, exatamente como ocorre em uma pilha dinâmica. O algoritmo passo a passo abaixo ilustra o processo recursivo descrito até aqui:

  • Terminou?
    • Se sim:
      • Retorne os resultados.
    • Se não:
      • Simplifique o problema;
      • Resolva o(s) problema(s) mais simples;
      • Encaixe os resultados na solução do problema original;
      • Retorne a solução.

Exemplo de recursividade – Fatorial

O fatorial de um número natural n, representado por n!, é o produto de todos os inteiros positivos menores ou iguais a n, conforme definido na equação matemática abaixo:

n! = n * ( n – 1 ) * ( n – 2 ) * ( n – 3 ) * … * 1

Caso Trivial (menor problema): 0! = 1 e 1! = 1

Caso Geral (problema complexo): n! = n * ( n -1 )!

Exemplos:

2! = 2 * 1 = 2

3! = 3 * 2! = 3 * (2 * 1) = 6

4! = 4 * 3! = 4 * (3 * 2 * 1) = 24

O Código fonte para este problema ficaria da seguinte forma:

Saída no console:

Saída no console de uma função com recursividade.
Figura 1: Fatorial – Recursividade – Saída no console.

A linha 5 define a função como sendo do tipo inteiro, com o nome fatorial e também existe um parâmetro do tipo inteiro. Nas linhas de 7 a 11 é tratado o caso trivial e nas linhas de 12 a 16 o caso geral. Note que em ambas as partes, a função é chamada dentro dela mesma, isso ocorre nas linhas 9 e 14.

Porém, observe a diferença, na linha 9 por ser o caso trivial, o valor 1 é passado como parâmetro, enquanto na linha 14 é passado um cálculo, exatamente o cálculo que identificamos na equação do fatorial, portanto, é o caso geral. Nas linhas de 19 a 25 está o programa principal. A linha 23 faz a primeira chamada à função recursiva do fatorial, a partir daí, a função se auto chamará, conforme a necessidade, até terminar. Vejamos agora como fica a pilha de controle de chamadas e retornos desta função recursiva.

O vídeo acima mostra o comportamento da pilha de controle de chamadas e retornos da função fatorial, que só para de se chamar quando chega no caso mais trivial.

Recursão X Iteração

Existe uma discussão acerca de quando devemos usar a recursão em nossa solução. Alguns problemas são naturalmente recursivos, e outros podem ser definidos em termos recursivos. Uma função pode ser escrita como uma função recursiva sem o uso de iteração e, portanto, reciprocamente, uma função recursiva pode ser descrita através de iterações sucessivas. Porém é preciso, antes de mais nada, entender a diferença entre recursão e iteração, para depois escolher qual usar.

Tanto iteração quanto recursão usam repetição. A iteração usa repetição em forma de comandos de repetição (for, while, do-while), já a recursão usa a repetição na forma de chamadas repetitivas a uma rotina. Ambas precisam de um teste de terminação. A iteração termina quando a condição de teste falha e a recursão termina quando se atinge o caso trivial. Ambas podem entrar em loop infinito, no caso da iteração se o teste nunca se tornar falso e no caso da recursão se o problema não for reduzido de forma que convirja para o caso trivial.

Algumas linguagens de programação também são do tipo recursivas, são as linguagens de programação funcional (LISP) e a programação Lógica (PROLOG), muito utilizadas inclusive em inteligência artificial, robótica e automação. Estruturas de Dados Dinâmicas como Árvores, Filas, Pilhas e Listas também fazem uso da recursão.

A partir do momento que estiver clara a diferença entre o emprego desses dois recursos computacionais, você terá mais clareza para decidir qual deles usar em seu projeto. É importante também dizer que uma análise da complexidade de um algoritmo recursivo deve ser feita. Muitas vezes o tempo computacional gasto com uma função recursiva em particular não vale a pena, sendo menos custoso implementar a mesma função de forma iterativa.

O fatorial é uma dessas funções que pode ser implementada tanto de forma recursiva quanto de forma iterativa, e diversos outros problemas cairão nesta situação. Caberá ao projetista do algoritmo implementar e avaliar o que realmente valerá a pena.

Conclusão – Recursividade

Sugiro que façam o fatorial de forma iterativa, para comparar os dois algoritmos. Coloquem um número fatorial muito grande para ser calculado e verifiquem o tempo de execução ao final, de cada um. Depois façam o mesmo para o número 0, número 1 e número 2 e reflitam a respeito dos resultados obtidos: a diferença foi muito grande? Para quem quiser se aprofundar no assunto, sugiro ler a respeito de análise da complexidade de algoritmos, em livros da ciência da computação.

Recursão é mais um recurso computacional disponível para você, em praticamente todas as linguagens de computação, utilize-a sabiamente! Espero que este artigo tenha sido útil a você. Se tiver dúvidas, deixe aí nos comentários, ok!? Muito Obrigada.

Outros artigos da série

<< Funções e Procedimentos – ModularizaçãoAlgoritmos: Resolução dos Exercícios Parte 1 >>
Website | Veja + conteúdo

Atuo como Professora de Informática e Computação desde 2001, atendendo de forma especial a Terceira Idade e Concurseiros. Desde 2009 venho atuando como Docente no Ensino Superior em diversos cursos de Graduação e Pós Graduação Lato Sensu, tanto presenciais, quanto semipresenciais e à distância. Ministrei várias disciplinas onde ensino os estudantes a desenvolverem plataformas e sistemas computacionais. Orientei vários trabalhos acadêmicos, desenvolvi inúmeros materiais, trabalhei com pesquisa, ensino, extensão e inovação, ministrei palestras em vários eventos. Mais recentemente venho ofertando serviços na área de tecnologia como desenvolvimento de sistemas, treinamentos, consultoria, mentoria, etc. Comecei meu Doutorado na área de Machine Learning (Multi-label Classification) na UFSCar em 02/2019 e devo terminar em 01/2023. Também estudo canto, jogo vôlei, sou geek, nerd, otaku e gamer!

Licença Creative Commons Esta obra está licenciada com uma Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional.

Receba os melhores conteúdos sobre sistemas eletrônicos embarcados, dicas, tutoriais e promoções.

Comentários:
Notificações
Notificar
guest
7 Comentários
recentes
antigos mais votados
Inline Feedbacks
View all comments
Lucas Rocha Hoskem
Lucas Rocha Hoskem
14/07/2021 20:17

Olá, adorei a explicação, me ajudou muito a entender tudo, mas o resultado sempre sai 6.

Leilson
Leilson
22/08/2019 14:03

Boa tarde. Rodei o código, mas o resultado na tela não sai como o da imagem. O resultado de cada iteração sai = a 6.

Parabéns pela explicação.

Marlon
Marlon
04/04/2019 02:23

boa explicação

Ricardo
Ricardo
25/06/2018 14:42

Ótima explicação, me ajudou muito.

Talvez você goste:

Séries



Outros da Série

Menu