capitulo-05 (9)

Prévia do material em texto

Algoritmos e Estruturas 
de Dados
Recursividade
Desenvolvimento do material
Miguel Carvalho
1ª Edição
Copyright © 2022, Afya.
Nenhuma parte deste material poderá ser reproduzida, 
transmitida e gravada, por qualquer meio eletrônico, 
mecânico, por fotocópia e outros, sem a prévia 
autorização, por escrito, da Afya.
Sumário
Nome Unidade
1. Título da Disciplina ...................................................................................... 4
2. Título da Disciplina ...................................................................................... 4
3. Título da Disciplina ....................................................................................... 5
4. Título da Disciplina ........................................................................................ 5
Para Início de Conversa...
Existem diversas maneiras para resolver problemas computacionais. 
Uma delas é optar por criar soluções utilizando estratégias interativas 
que executam um conjunto de passos empregando diversos comandos 
de repetição ou condicionais para alcançar um objetivo, ou usar 
estratégias recursivas que realizam chamadas internas a si próprias e 
que, na maioria das vezes, possuem implementações mais simples. 
Entretanto, podem apresentar maior complexidade de tempo e recursos. 
A implementação de soluções recursivas se aproveita da repetição de 
partes do código para resolução de problemas e utiliza chamadas aos 
métodos que contenham essa repetição do código, simplificando a 
visualização e o desenvolvimento da solução. 
Aprofundaremos nossos estudos sobre recursividade verificando as 
vantagens e desvantagens de sua utilização. Além disso, praticaremos 
os conhecimentos aprendidos por meio de diversos exemplos clássicos 
apresentados ao longo deste estudo.
Objetivos
 ▪ Implementar métodos recursivos; 
 ▪ Criar soluções iterativas e recursivas; 
 ▪ Conhecer problemas clássicos que empregam a recursão.
Algoritmos e Estruturas de Dados 3
1. Princípios da Recursão
Uma das estratégias para resolução de problemas computacionais é a 
utilização da estratégia de recursividade. 
Segundo Goodrich e Tamassia (2013), a recursão pode ocorrer em duas 
situações: 
 ▪ Quando o método chama ele próprio; 
 ▪ Quando o método X chama outro método Y, que chama X novamente. 
A grande vantagem da abordagem recursiva é a possibilidade de 
criarmos soluções que tiram vantagem do comportamento repetitivo de 
muitos problemas (GOODRICH; TAMASSIA, 2013).
Uma boa aplicação da recursividade permite que um caso geral seja 
resolvido por meio de um caso específico. Isto é, em termos práticos, 
podemos não saber resolver o fatorial de 10, mas podemos alcançar o 
resultado sabendo que fatorial de 1 (1!) é 1, e que fatorial de um número 
n (n!) é igual a n x (n-1)!. 
A utilização de um caso base permite resolver, de forma simples, os 
casos gerais. Essa ideia é a base da recursão alcançando a resolução de 
problemas gerais, por meio do entendimento de um caso base, possível 
de resolver. Devido a essa particularidade, muitos algoritmos de divisão 
e conquista optam por utilizar a recursividade como base para as suas 
soluções, simplificando problemas.
Uma solução recursiva chama a si mesma, passando como parâmetro 
uma chamada mais simplificada, permitindo que depois de algumas 
chamadas o método recursivo convirja para a solução.
As estratégias de resolução de problemas com recursividade utilizam 
um caso base – algo que sabemos resolver – e o caso recursivo (passo 
recursivo) – onde ocorrem as chamadas cada vez mais simples, até que 
seja alcançado o caso base.
Vejamos alguns princípios básicos sobre a recursão: 
 ▪ Uma recursão sempre deve resolver problemas gerais, fazendo 
chamadas mais simplificadas até que se alcancem problemas mais 
simples de resolver, casos mais específicos; 
 ▪ Uma recursão deve sempre simplificar as chamadas a cada iteração, 
do contrário, não ocorre convergência para o resultado. Veja, no 
exemplo, um problema que não converge: 
O programa a seguir certamente não converge para um resultado.
Algoritmos e Estruturas de Dados 4
A partir do código apresentado, obteremos como resposta o seguinte 
resultado:
valor de n 4885
vException in thread “main” java.lang.StackOverflowError
at java.io.FileOutputStream.write(Unknown Source)
at java.io.BufferedOutputStream.flushBuffer(Unknown Source)
at java.io.BufferedOutputStream.flush(Unknown Source)
at java.io.PrintStream.write(Unknown Source)
at sun.nio.cs.StreamEncoder.writeBytes(Unknown Source)
at sun.nio.cs.StreamEncoder.implFlushBuffer(Unknown Source)
A recursividade possui um caso base e os casos recursivos que devem 
alcançar o caso base.
Exemplo: 
1! = Fatorial (1) =1.
2. Algoritmo Iterativo x Algoritmo Recursivo
Os algoritmos iterativos possuem determinados passos, para alcançar 
uma solução, utilizando, geralmente, uma variedade de laços e comandos 
condicionais. Os algoritmos recursivos possuem um caso base, que 
auxilia na resolução de um caso geral, por meio de chamadas recursivas 
mais simplificadas. 
Comumente, algoritmos recursivos são mais simples de serem 
entendidos, pois costumam possuir menos linhas de código que os 
algoritmos iterativos.
Neste estudo, poderíamos utilizar como caso base o Fatorial de 0 (0!), que, por 
definição, é igual a 1. Entretanto, para um melhor entendimento e eficiência da 
proposta pedagógica, optamos Saiba Mais Leia mais Importante Algoritmos e 
Estruturas de Dados 9 por utilizar como caso base 1!. Além disso, os programas 
implementados somente permitem os cálculos dos Fatoriais dos números maiores 
ou iguais a 1 (n>=1).
Vamos supor um problema que precisa calcular o Fatorial de um número 
para ser resolvido. 
1!=1 e que n!=n x (n-1)!. 
Algoritmos e Estruturas de Dados 5
Dessa forma, podemos calcular o Fatorial utilizando uma implementação 
iterativa da seguinte maneira:
O código da Classe Principal é apresentado a seguir:
Teremos, então, o seguinte resultado:
Fatorial Iterativo
120
Nessa implementação, a variável “f ” guarda o valor do fatorial do número 
“n”, que é obtido pela multiplicação por todos os números anteriores a 
“n”, utilizando o cálculo do fatorial: 
n! = n x (n-1) x (n-2) x … x 1
Podemos pensar nesse problema implementado por meio de uma 
solução recursiva, em que o método fat, faz chamadas a ele próprio até 
que o cálculo do fatorial convirja para um caso específico nosso caso 
base 1!=1. 
Vejamos:
O código da Classe Principal é apresentado a seguir:
Algoritmos e Estruturas de Dados 6
Teremos, então, o seguinte resultado:
Fatorial Recursivo
120
Perceba que, na solução recursiva, o código é mais simples de ser 
entendido.
Os algoritmos que utilizam estratégias recursivas também podem 
ser implementados por estratégias interativas. A vantagem da 
implementação recursiva é que, na maior parte das vezes, o código 
fica mais simples, legível e com menos linhas de código. Entretanto, a 
Importante Algoritmos e Estruturas de Dados 11 maioria dos algoritmos 
recursivos possui complexidade de tempo e recursos maiores que os 
algoritmos iterativos.
3. Exemplos de Problemas Clássicos que 
Empregam a Recursão
Segundo Goodrich e Tamassia (2013), as implementações recursivas 
podem ser classificadas como: 
 ▪ Recursão linear: o algoritmo faz apenas uma chamada recursiva por vez. 
 ▪ Recursão binária: algoritmo faz duas chamadas recursivas por vez. 
 ▪ Recursão múltipla: o algoritmo faz mais de duas chamadas por vez. 
Como forma do processo de ensino aprendizagem, na literatura, 
encontramos alguns exemplos clássicos de recursão, como os métodos 
para cálculo do Fatorial de um número e da sequência de Fibonacci. 
Neste tópico, serão apresentados alguns desses exemplos, para 
aprimorarmos nossos conhecimentos sobre recursividade e aplicar os 
conceitos aprendidos no desenvolvimento de soluções computacionais.
Fatorial
Um dos mais clássicos exemplos de recursão é o da implementação do 
método para cálculo do Fatorial de um número.O cálculo do fatorial 
é importante no desenvolvimento de diversas soluções, principalmente, 
nos sistemas que envolvem cálculos de análise combinatória. 
O Fatorial já foi usado para exemplificar os conceitos de recursividade. 
Entretanto, nesta seção, nos aprofundaremos no estudo dessa 
implementação.
A implementação para o cálculo do Fatorial recursivo possui como caso 
base o valor de 1!, que sabemos ser 1. 
1!=1(Caso Base) 
Algoritmos e Estruturas de Dados 7
Além disso, sabemos que n! = n x (n-1)!. Dessa forma, podemos definir 
uma função da seguinte maneira:
fat(n) = n x fat(n-1) 
Na implementação do código, devemos colocar como critério de parada 
das chamadas recursivas o valor de n sendo 1. Isso deve ser feito dentro 
de um comando if. 
if (n == 1) return 1; 
Caso, o valor de n não seja igual a 1, continuamos as chamadas recursivas 
até que o valor de n seja igual 1. Para isso, vamos diminuindo valor de n 
para que, em um determinado momento, n convirja para o valor desejado. 
else return n * fat(n - 1); 
Na Classe Principal, utilizamos um comando de repetição para imprimir 
os 10 primeiro números de fibonacci.
Na Classe Principal, utilizamos um comando de repetição para imprimir 
o fatorial dos 10 primeiros números.
Classe Principal:
Dessa forma, obtemos como resultado:
Você pode imaginar quantas chamadas ao método public static int 
fat(int n) foram necessárias para calcular cada número da sequência de 
fibonacci impresso? 
Algoritmos e Estruturas de Dados 8
Veja, no Quadro 1, a seguir.
Fatorial Quantidade de chamadas
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
Total 55
Quadro 1: Quantidade de Chamadas ao Método public static int fat(int n). Fonte: Do autor.
A Figura 1 esquematiza as chamadas ao método public static int fat(int 
n) realizadas para calcular o Fatorial de 5.
Figura 1: Chamadas ao método public static int fat(int n) realizadas para calcular o Fatorial de 5. 
Fonte: Do autor
Fibonacci
A sequência de Fibonacci é outro exemplo clássico para o processo de 
ensino-aprendizagem de recursividade, pois está presente em vários 
lugares, como em projetos de arquitetura e em muitos fenômenos da 
natureza. 
A sequência de Fibonacci pode ser obtida pela seguinte função: 
Fib(n) = Fib(n-1) + Fib (n-2) 
Sendo definido Fib(1)=1 e Fib(2)=1
Algoritmos e Estruturas de Dados 9
Portanto, para calcular a sequência de Fibonacci, devemos utilizar como 
base o valores de Fibonacci 1 e 2, que são iguais a 1. Para todos os 
outros valores, devemos utilizar a função geral. 
Dessa maneira, utilizando uma estratégia recursiva implementamos o 
caso base com um if. 
if (n == 1 || n == 2) return 1;
Caso o valor de n não seja igual a 1 ou a 2, devemos continuar as 
chamadas recursivas até que o valor de n convirja para esses valores. 
else return fib(n - 1) + fib(n - 2); 
Veja, a seguir, a Classe Fibonacci em Java com o método fib para calcular 
o Fibonacci de um número implementando por meio de uma estratégia 
recursiva. 
Na Classe Principal, utilizamos um comando de repetição para imprimir 
os 10 primeiro números de fibonacci. 
Classe Principal:
O resultado está apresentado a seguir:
Você pode imaginar quantas chamadas ao método public static int 
fib(int n) foram necessárias para calcular cada número da sequência de 
fibonacci impresso? 
Veja, no Quadro 2, a seguir:
Algoritmos e Estruturas de Dados 10
Fibonacci Quantidade de chamadas
1 1
2 1
3 3
4 5
5 9
6 15
7 25
8 41
9 67
10 109
Total 276
Quadro 2: Quantidade de Chamadas ao Método public static int fib(int n). Fonte: Do autor.
A Figura 2 esquematiza as chamadas recursivas realizadas para calcular 
o Fibonacci de 5.
fib(5)
fib(4)
fib(3)
fib(3)
fib(2)
fib(2) fib(1)
fib(2) fib(1)
return fib(4)+ fib(3);
return fib(3)+ fib(2);
return fib(2)+ fib(1);
return fib(2)+ fib(1);
return 1;
return 1; return 1;
return 1; return 1;
5
3
1
11
1 12
2
Figura 2: Chamadas ao método public static int fat(int n) realizadas para calcular o Fibonacci de 
5. Fonte: Do autor.
É possível fazer a sequência de Fibonacci de maneira iterativa. Entretanto, 
o entendimento do código é muito mais complexo.
O conteúdo foi dividido em três partes. Na primeira, apresentamos 
os conceitos básicos da recursão; na segunda, diferenciamos as 
implementações iterativas das recursivas, e na terceira, apresentamos 
diversos exemplos de recursão. Durante nosso estudo, aprendemos 
a importância dos algoritmos recursivos na resolução de problemas 
e verificamos suas vantagens e desvantagens. O profissional de 
computação deve sempre avaliar os contextos em que será aplicada a 
solução, para implementar adequadamente os algoritmos, optando por 
utilizar a estratégia iterativa ou a estratégia recursiva.
Algoritmos e Estruturas de Dados 11
Referências
GOODRICH, M. T.; TAMASSIA, R. Estrutura de dados e algoritmos em Java. 
5 ed. Porto Alegre: Bookman, 2013.
Algoritmos e Estruturas de Dados 12
	Nome Unidade 5
	1. Título 5
	2. Título 5
	3. Título 5
	4. Título 5