Recursividade

Operações relacionais e lógicas Operações Aritméticas variáveis Tipos de dados Estruturas Aninhadas algoritmos

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

 

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: 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

 

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ção
NEWSLETTER

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

Obrigado! Sua inscrição foi um sucesso.

Ops, algo deu errado. Por favor tente novamente.

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

Elaine Cecília Gatto
Bacharel em Engenharia de Computação. Mestre em Ciência da Computação. Doutoranda em Ciência da Computação. Co-fundarora e Líder das #GarotasCPBr. Pesquisadora Convidada no Grupo de Pesquisa: "Artes em Tecnologias Emergentes" do Programa de Pós Graduação em Design na UNESP Campus Bauru. Cantora, Docente no Magistério Superior, Geek, Nerd, Otaku e Gamer. Apaixonada por Michael Jackson, Macross, Rocky Balboa, Séries, Filmes, Cervejas e Vinhos. Mais informações sobre mim você encontra em: http://lattes.cnpq.br/8559022477811603.

6
Deixe um comentário

avatar
 
3 Comment threads
3 Thread replies
2 Followers
 
Most reacted comment
Hottest comment thread
4 Comment authors
Elaine Cecília GattoLeilsonMarlonRicardo Recent comment authors
  Notificações  
recentes antigos mais votados
Notificar
Leilson
Visitante
Leilson

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
Visitante
Marlon

boa explicação

Ricardo
Visitante
Ricardo

Ótima explicação, me ajudou muito.