Aula 04 02 - Recursividade

Prévia do material em texto

Recursividade
Apresentação
Nesta Unidade de Aprendizagem, trabalharemos com recursividade através da construção de 
subalgoritmos recursivos. 
Bons estudos.
Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:
Identificar as características de funções recursivas.•
Reconhecer problemas que podem ser resolvidos através de soluções recursivas.•
Construir algoritmos que utilizem recursividade.•
Desafio
A recursividade é um processo utilizado para definir a própria solução, sendo chamado 
recursivamente na especificação de sua execução.
Seu desafio é construir um algoritmo em pseudocódigo que leia um vetor de 10 elementos, sendo 
cada elemento do tipo real, e que escreva todos os elementos do vetor. Para realizar essas tarefas, 
utilize dois procedimentos não recursivos (ler e escrever). O algoritmo também deve ter uma 
função recursiva que calcule o somatório dos elementos do vetor; assim, o somatório pode ser 
definido da seguinte maneira:
Somatorio(X) 
se X = 1, o somatorio é o primeiro elemento do vetor (vetor[1]) 
se X > 1, o somatório é o elemento atual (vetor[X]) + Somatorio(X-1)
Infográfico
Em programação, a recursividade é um mecanismo útil e poderoso que permite a uma função 
chamar a si mesma. Veja no infográfico conceitos e exemplos sobre recursividade
Aponte a câmera para o 
código e acesse o link do 
conteúdo ou clique no 
código para acessar.
https://statics-marketplace.plataforma.grupoa.education/sagah/1558c0a0-f473-4d33-bc7a-6d65797e770b/38baa2ea-361f-46fa-ae96-1f40b241d5a7.jpg
 
Conteúdo do livro
A recursividade é uma forma de construir funções que apresentam chamadas a elas mesmas 
recursivamente. Conheça um pouco mais sobre esse assunto estudando as páginas selecionadas do 
seguinte livro: EDELWEISS, N.; LIVI, M.A.C. Algoritmos e programação com exemplos em Pascal e 
C - Vol. 23. Série Livros Didáticos Informática UFRGS. Porto Alegre: Bookman, 2014. Boa leitura!
Conteúdo interativo disponível na plataforma de ensino!
Dica do professor
Assistindo ao vídeo preparado para esta Unidade, compreenderemos como funcionam os 
subprogramas recursivos!
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
https://fast.player.liquidplatform.com/pApiv2/embed/cee29914fad5b594d8f5918df1e801fd/cda5469a45a4c9c356ffc6135057e199
Exercícios
1) 
Considere o seguinte algoritmo em pseudocódigo e selecione a alternativa falsa. 
 
algoritmo "oquefaz" 
var 
 valor : inteiro 
procedimento faz(N : inteiro) 
inicio 
 se (N=0) entao 
 escreval(N) 
 senao 
 faz(N-1) 
 escreval(N) 
 fimse 
fimprocedimento 
 
inicio 
 repita 
 escreva("Digite: ") 
 leia(valor) 
 ate valor >= 0 
 faz(valor) 
fimalgoritmo
A) O procedimento "faz" é recursivo.
B) O procedimento "faz" possui uma condição de parada da recursividade.
C) O algoritmo escreve os números inteiros entre 0 (zero) e o valor lido.
D) O procedimento "faz" escreve o valor de N quando esse é igual a zero ou escreve o valor de 
N-1 quando N for maior que zero.
E) Se o valor digitado for menor que zero, o programa solicitará que seja digitado um novo valor.
2) 
Considere a implementação e o funcionamento de subprogramas (rotinas) recursivos. 
Analise as afirmativas a seguir e assinale a falsa.
A) Subprogramas recursivos possuem chamadas a si mesmos.
B) A execução do subprograma fica em espera (em suspenso) até que retorne da chamada 
recursiva.
C) Cada chamada recursiva exige o armazenamento de nova posição de retorna e criação de 
novas variáveis locais.
D) Rotinas recursivas correm o risco de gerar stack overflow.
E) Subprogramas recursivos não precisam ter condição de parada.
3) 
Analise as alternativas a seguir e selecione a que implementa corretamente um subprograma 
recursivo que calcula o somatório dos números inteiros no intervalo [1,N].
A) funcao Y(X :inteiro): inteiro 
inicio 
 se X = 0 entao 
 retorne (1) 
senao 
 retorne(X + Y(X-1)) 
fimse 
fimfuncao
B) funcao Y(X :inteiro): inteiro 
inicio 
 se X = 1 entao 
 retorne (1) 
 senao 
 retorne(X - Y(X-1)) 
 fimse 
fimfuncao
C) funcao Y(X :inteiro): inteiro 
inicio 
 se X = 1 entao 
 retorne (1) 
 senao 
 retorne(X + Y(X-1)) 
 fimse 
fimfuncao
funcao Y(X :inteiro): inteiro 
var 
D) 
 K, L : inteiro 
inicio 
 K <- 0 
 para L de 1 ate X passo 1 faca 
 K <- K + L 
 fimpara 
 retorne(K) 
fimfuncao
E) funcao Y(X :inteiro): inteiro 
var 
 K, L : inteiro 
inicio 
 K <- 0 
 para L de 1 ate X passo 1 faca 
 K <- K - L 
 fimpara 
 retorne(K) 
fimfuncao
4) Analise o seguinte subprograma em pseudocódigo: 
 
funcao M(X :inteiro): inteiro 
inicio 
 se (X = 0) ou (X = 1) entao 
 retorne (1) 
 senao 
 retorne(M(X-1)+M(X-2)) 
 fimse 
fimfuncao 
 
As alternativas a seguir apresentam chamadas da função M e indicam o retorno conforme o 
valor passado como parâmetro. Selecione a alternativa correta.
A) M(5) retornará o valor 8.
B) M(6) retornará o valor 20.
C) M(1) retornará o valor 0.
D) M(3) retornará o valor 2.
E) M(7) retornará o valor 13.
5) 
Analise o seguinte algoritmo em pseudocódigo: 
 
algoritmo "oquefaz" 
var 
valor : inteiro 
funcao calcula(N : inteiro):real 
inicio 
 se (N = 0) entao 
 retorne(1) 
 senao 
 retorne((N / (N-1)) + calcula(N-1)) 
 fimse 
fimfuncao 
 
inicio 
 escreva("Digite Valor: ") 
 leia(valor) 
 escreval("Serie= ",serie(valor)) 
fimalgoritmo 
 
Considere que foi digitado 10 para a variável valor. Selecione a alternativa que representa 
corretamente a série implementada pela função calcula(valor).
A) Série = (1/1) + (1/2) + (2/3) + (3/4) + (4/5) + (5/6) + (6/7) + (7/8) + (8/9) + (9/10).
B) Série = 1 + (1/1) + (2/1) + (3/2) + (4/3) + (5/4) + (6/5) + (7/6) + (8/7) + (9/8).
C) Série = (1/1) + (2/1) + (3/2) + (4/3) + (5/4) + (6/5) + (7/6) + (8/7) + (9/8) + (10/9).
D) Série = (1/1) - (1/2) + (2/3) - (3/4) + (4/5) - (5/6) + (6/7) - (7/8) + (8/9) - (9/10).
E) Série = (1/1) - (2/1) + (3/2) - (4/3) + (5/4) - (6/5) + (7/6) - (8/7) + (9/8) - (10/9).
Na prática
José trabalha como estagiário em uma fábrica de software, em meio de suas atribuições ele se 
deparou com uma dúvida referente a recursividade em um dos projetos que lhe foi dado, a dúvida 
dele foi:
"Uso recursão ou iteração (ouvi dizer que se pode fazer das duas formas) para resolver um dado 
problema algorítmico?"
Sendo assim, procurou seu líder de equipe, que lhe explicou:
"José, acho que quase todos que desenvolvem programas usam métodos iterativos para a criação 
de programas, vejo que você está ligado e foi ótimo a sua curiosidade. Vou dar uma nova 
ferramenta para modificar um pouco seu código e explicar as diferenças."
Primeiro de tudo, o que é um método iterativo e o que é um método recursivo?
Vejamos duas funções que fazem exatamente a mesma coisa, o produto fatorial de um número, 
entretanto uma usa um processo iterativo e a outra um processo recursivo.
//método iterativo 
int fatorial(int x){ 
 int i,result; 
 result=1; 
 for (i=0; i < x; i++){ //uso do comando for 
 result= result*(x-i); 
 } 
 return result; 
}
 
//método recursivo 
int fat(int x) 
{ 
if (x < 2) return 1; //recursivo uso de uma condição para o fim 
 else return fat(x-1) * x; 
} 
 
int main(int argc, char *argv[]) { 
//chamadas dos métodos 
printf("Fatorial com iteração.: %d",fatorial(4)); 
printf("nFatorial com recursão.: %d",fat(4)); 
return 0; 
}
Note que no método iterativo é criado um loop (for), já o recursivo a função é chamada dentro de si 
mesma com uma condição de parada.
O uso da linguagem C é para exemplificar, isso ajuda os programadores que querem aprender, mas 
o importante é fazer outros experimentos para ver se realmente entendeu.
Saiba +
Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do professor:
Recursividade 
Neste vídeo, o autor dá uma aula sobre recursividade 
utilizando slides e dando exemplos.
Aponte a câmera para o código e acesse o linkdo conteúdo ou clique no código para acessar.
Me Salva! Programação em C - PLC20 - Recursão 
No vídeo a seguir, a autora mostra como exemplo o fatorial de 
um número.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
Curso de Programação em C/C++ - Aula 14 - Recursividade 
Neste vídeo, o autor mostra, como exemplo, a impressão de 
números sequênciais de início e limite de um número.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
https://www.youtube.com/embed/eaUlBChA7nY?rel=0
https://www.youtube.com/embed/kS_VJYWeqIQ?rel=0
https://www.youtube.com/embed/dkBh0TrGXtg?rel=0