Buscar

Aula11_TT214_Linguagem e Técnica de Programação I

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 27 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 27 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 27 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

TT214 – Linguagem e Técnica de 
Programação I 
1º Semestre – 2013 
Prof. Suelen Mapa de Paula 
 
1 
Aula 9 
Contatos 
 Suelen Mapa de Paula 
 suelenmapa@gmail.com 
 suelen@dca.fee.unicamp.br 
2 
Ementa da aula 
 Recursividade: 
 Introdução e Definições; 
 Rotinas Recursivas; 
 Exercícios; 
 Referências. 
 
 
 
 
**Este material foi baseado nas aulas do professor Guilherme 
Coelho, sob a autorização do mesmo. 
 
 
3 
Preencher formulário de Avaliação 
 http://goo.gl/NJhVQQ 
4 
Introdução 
 Um objeto de estudo é dito recursivo se ele pode ser 
definido em termos de si próprio; 
 Objetos recursivos são muito comuns na matemática; 
 Exemplo – soma dos números inteiros em um intervalo [m, n], com m 
≤ n: 
 
 
 Definição 1: 
 
 
 
 Definição 2: 
 
 
 
 
5 
k
k=m
n
å
k
k=m
n
å =
m se m= n
n+ k
k=m
n-1
å se n >m
ì
í
ï
î
ï
k
k=m
n
å =
m se m= n
m+ k
k=m+1
n
å se n >m
ì
í
ï
î
ï
Introdução 
 Da mesma maneira que é possível definir operações 
matemáticas de forma recursiva, também é possível 
definir algoritmos computacionais recursivos; 
 Ou seja, que são definidos em termos deles mesmos; 
 Vantagens: 
 Dependendo do problema, a implementação da versão 
recursiva de um algoritmo requer um número menor de 
variáveis e de instruções de controle (quando comparada 
com a versão iterativa do algoritmo); 
 Programas recursivos tendem a ser mais simples de escrever e 
analisar. 
 Abordagem recursiva deve ser usada com cuidado! 
 
 
6 
Recursão 
 Em computação, recursão é o processo de resolução de um problema que 
consiste em: 
 Reduzir o problema em um ou mais subproblemas com as seguintes 
características: 
 Os subproblemas são idênticos ao problema original; 
 São mais simples de resolver; 
 Uma vez feita a subdivisão, a mesma técnica é aplicada para dividir cada 
subproblema; 
 O procedimento se repete até que se encontre subproblemas tão simples que podem 
ser resolvidos sem mais divisões; 
 A solução completa do problema original é obtida através da montagem 
das soluções dos subproblemas (componentes). 
 Neste tópico trabalharemos com funções e procedimentos (rotinas) 
recursivos. 
 7 
Rotinas Recursivas 
 Uma rotina (função ou procedimento) é dita recursiva 
quando ela chama a si mesma; 
 Existem dois tipos de rotinas recursivas: 
 Rotinas recursivas diretas: aquelas que, em suas descrições, 
fazem chamadas a si próprias; 
 Ex.: no corpo de uma função funcao1() é feita uma chamada a 
funcao1(). 
 Rotinas recursivas indiretas: são aquelas que não fazem 
chamadas a si próprias em suas descrições, mas chamam outras 
rotinas que podem vir a chamá-las. 
 Ex.: no corpo de uma função funcao1() é feita uma chamada a uma 
função funcao2() que, por sua vez, chama funcao1() em seu próprio 
corpo. 
 
8 
Rotinas Recursivas 
 Exemplo 1a: cálculo da soma dos números inteiros em 
um intervalo [m, n], com m ≤ n, pela definição 1 (vide 
slide 4); 
 
9 
int soma(int m, int n){ 
 if (m == n) 
 return m; 
 else 
 return (soma(m, n-1) + n); 
 
} 
soma(1, 4) = soma(1, 3) + 4 
soma(1, 3) = soma(1, 2) + 3 
soma(1, 2) = soma(1, 1) + 2 
soma(1, 1) = 1 
1 
3 
6 
10 
Rotinas Recursivas 
 Exemplo 1b: cálculo da soma dos números inteiros em 
um intervalo [m, n], com m ≤ n, pela definição 2 (vide 
slide 4); 
 
10 
int soma(int m, int n){ 
 if (m == n) 
 return m; 
 else 
 return (m + soma(m+1, n)); 
 
} 
soma(1, 4) = 1 + soma(2, 4) 
soma(2, 4) = 2 + soma(3, 4) 
soma(3, 4) = 3 + soma(4, 4) 
soma(4, 4) = 4 
4 
7 
9 
10 
Rotinas Recursivas 
 Exemplo 1c: cálculo da soma dos números inteiros em 
um intervalo [m, n], com m ≤ n, sem recursão (versão 
iterativa); 
 
11 
int somaIt(int m, int n){ 
 int i, soma = 0; 
 
 for (i=m; i <= n; i++) 
 soma += i; 
 
 return soma; 
} 
Requer algumas variáveis 
adicionais. 
Não faz nenhuma chamada a rotinas 
Rotinas Recursivas 
 Podemos tirar algumas conclusões a respeito dos exemplos 
dados nos slides anteriores: 
 Dependendo do problema, existem diferentes formas de resolvê-lo 
recursivamente; 
 Algumas podem ser mais eficientes que as outras; 
 
 Além das formas recursivas pode-se resolver o mesmo problema 
iterativamente, ou seja, sem o uso de recursão: 
 Em algumas situações, formas iterativas de solução podem ser mais eficientes 
que formas recursivas, apesar de apresentarem implementação mais 
complexa. 
 
 TODA implementação recursiva possui uma verificação de condição 
que interrompe as chamadas recursivas (uma condição de parada): 
 Esta verificação é FUNDAMENTAL em toda implementação recursiva 
 
 12 
Rotinas Recursivas 
 Exemplo 2a: cálculo do número de dígitos de um 
número inteiro (versão iterativa); 
 
13 
int numero_digitos(int n){ 
 int num = 1; 
 
 while( abs(n) > 9 ) { 
 num ++; 
 n = n/10; 
 } 
 
 return num; 
} 
Rotinas Recursivas 
 Exemplo 2b: cálculo do número de dígitos de um 
número inteiro (versão recursiva); 
 
14 
int numDigitos(int n){ 
 
 if( abs(n) <= 9 ) { 
 return 1; 
 } 
 else { 
 return (1 + numero_digitos(n/10)); 
 } 
} 
numDigitos(937) = 1 + numDigitos(93) 
numDigitos(93) = 1 + numDigitos(9) 
numDigitos(9) = 1 
1 
2 
3 
Condição de saída da 
recursão 
Rotinas Recursivas 
 Exemplo 3a: cálculo do fatorial (versão iterativa); 
 Definição: 
 n! = n*(n-1)*(n-2)*(n-3)...*2*1 
 1! = 0! = 1; 
 
15 
int fatorial(int n){ 
 int i, fat = 1; 
 
 while (n > 1) { 
 fat *= n; 
 n--; 
 } 
 
 return fat; 
} 
Rotinas Recursivas 
 Exemplo 3b: cálculo do fatorial (versão recursiva); 
 Definição (recursiva): 
 
16 
n!=
1
n´ (n-1)!
se n= 0
se n> 0
ì
í
ï
îï
int fatorial(int n){ 
 
 if (n == 0) 
 return 1; 
 else 
 return (n * fatorial(n-1)); 
} 
Condição de saída da 
recursão 
Rotinas Recursivas 
 Exemplo 4a: cálculo da potência (versão iterativa); 
 
17 
int potencia(float x, int n){ 
 float pot = 1; 
 int i; 
 
 if (n < 0){ 
 for (i=1; i <= -n; i++) 
 pot *= 1/x; 
 } 
 else { 
 if (n == 0) 
 pot = 1; 
 else 
 for (i=1; i <= n; i++) 
 pot *= x; 
 } 
 return pot; 
} 
Rotinas Recursivas 
 Exemplo 4b: cálculo da potência (versão recursiva); 
 Definição (recursiva): 
 
18 
xn =
1 x|n|
1
x´ xn-1
se n< 0,
se n= 0,
se n> 0
ì
í
ïï
î
ï
ï
int potencia(float x, int n){ 
 if (n == 0) 
 return 1; 
 else { 
 if (n < 0) 
 return (1 / potencia(x, abs(n))); 
 else 
 return (x * potencia(x, n-1)) 
 } 
} 
Rotinas Recursivas Indiretas 
 Exemplo 5: rotina recursiva indireta 
 
19 
#include <stdio.h> 
 
void func1(int n); 
void func2(int n); 
 
void func1(int n) { 
 if (n > 0) { 
 if ((n%2) == 0) { 
 printf("f1: %d\n", 
n); 
 func2(n-1); 
 } 
 else 
 func2(n); 
 } 
} 
void func2(int n) { 
 if ((n % 2) != 0){ 
 printf("f2: %d\n", 
n); 
 func1(n-1); 
 } 
} 
 
int main() { 
 int n; 
 
 printf(”Numero: "); 
 scanf("%d", &n); 
 func1(n); 
 return 0; 
} 
Numero: 4 
f1: 4 
f2: 3 
f1: 2f2: 1 
Rotinas Recursivas 
 Existem algumas situações em que não é recomendável a 
utilização de recursão: 
 Quando a chamada recursiva é no início ou no fim da rotina 
 Implementações iterativas tendem a ser mais eficientes; 
 Lembrem-se que cada chamada de função aloca espaço de memória para 
variáveis internas e parâmetros (além da memória de controle da execução); 
 Exemplos: 
 Cálculo de Fatorial, potência e soma de números vistos nos exemplos 
anteriores. 
 Quando chamadas independentes da rotina em um processo 
recursivo repetem o processamento de partes da solução 
 
20 
Rotinas Recursivas 
 Exemplo 6a: cálculo recursivo de um número de 
Fibonacci; 
 Definição (recursiva): 
 
21 
Fibonacci(n)=
0
1
Fibonacci(n-1)+Fibonacci(n-2)
se n= 0,
se n=1,
se n>1
ì
í
ï
î
ï
int fibonacci(int n){ 
 if ((n == 0) || (n == 1)) 
 return n; 
 else 
 return (fibonacci(n-1) + fibonacci(n-2)); 
} 
Rotinas Recursivas 
 Exemplo 6b: cálculo iterativo de um número de 
Fibonacci; 
 
22 
int fibonacci(int n){ 
 int f0 = 0, fn = 1, i, temp; 
 if (n == 0) 
 return f0; 
 else { 
 if (n == 1) 
 return fn; 
 else { 
 for (i=2; i <= n; i++) { 
 temp = fn; 
 fn = fn + f0; 
 f0 = temp; 
 } 
 return fn; 
 } 
 } 
} 
Rotinas Recursivas 
 Observando os códigos-fonte dos exemplos 6a e 6b, 
percebemos que a versão recursiva é muito mais clara 
que a versão iterativa; 
 No entanto, ao executarmos as duas versões para o 
cálculo de Fibonacci(45) obtemos os seguintes resultados: 
 Versão iterativa: 
 Fibonacci(45) = 1.134.903.170; 
 Tempo de execução: 0.006s; 
 Versão recursiva: 
 Fibonacci(45) = 1.134.903.170; 
 Tempo de execução: 19.463s; 
 23 
3250x mais lento!!! 
Rotinas Recursivas 
 Por que a versão recursiva de Fibonacci é tão mais lenta? 
 Tomemos o cálculo de fibonacci(5): 
 
24 
2 
fibonacci(5) 
fibonacci(4) fibonacci(3) 
3 
fibonacci(2) fibonacci(2) fibonacci(1) 
1 1 1 2 
fibonacci(3) 
fibonacci(2) fibonacci(1) 
1 1 
fibonacci(1) fibonacci(0) 
0 1 
fibonacci(1) fibonacci(0) 
1 0 
fibonacci(1) 
fibonacci(0) 
1 
0 
Ineficiente: muitos “pedaços” do problema são 
calculados múltiplas vezes. 
  Crescimento exponencial do tempo em função de n. 
Exercícios 
ATENÇÃO: Os exercícios de número 1 e 3 deverão ser entregues (em um arquivo .ZIP), 
via Teleduc, até o dia 14/11/2013. Um deles será sorteado e corrigido. A correção deste 
exercício, combinada com a correção dos exercícios solicitados nos demais tópicos, terá nota 
equivalente a uma atividade do Susy. Estes exercícios devem ser feitos individualmente. 
1. Escreva uma função recursiva que calcule a soma dos elementos de um 
vetor. Esta função deve receber dois parâmetros: o vetor de dados e o 
tamanho deste vetor. Escreva também o programa principal que deve ler 
o tamanho e os dados do vetor (máximo 20 elementos), chamar a 
função e mostrar o resultado. 
2. Escreva uma função recursiva que encontre o maior elemento de um 
vetor. Esta função deve receber dois parâmetros: o vetor de dados e o 
tamanho deste vetor. Escreva também o programa principal que deve ler 
o tamanho e os dados do vetor (máximo 20 elementos), chamar a 
função e mostrar o resultado. 
 
 
25 
Exercícios 
3. Escreva um procedimento recursivo que imprima na tela o 
resultado da conversão de qualquer número inteiro não-negativo 
para a base binária. Escreva também o programa principal, 
responsável por ler o valor do número inteiro e chamar o 
procedimento recursivo. 
4. Escreva um programa que resolva recursivamente e mostre na 
tela a solução para o problema da Torre de Hanoi com n discos e 
três pinos. Na configuração inicial todos os discos estão no pino 
1 e deseja-se mover tais discos para o pino 3, usando o pino 2 
como auxiliar. Lembre-se que só é possível mover um disco por 
vez e nenhum disco pode ser colocado sobre outro disco de 
tamanho menor que ele. 
Mais informações: http://www.geider.net/esp/varios/hanoi.htm 
26 
Referências 
 MIZRAHI, V. V., Treinamento em Linguagem C – Curso 
Completo – Módulo 1. 2a Edição, Pearson Makron Books, 
2005. 
 ASCENCIO, A. F. G. & DE CAMPOS, E. A. V., Fundamentos 
da Programação de Computadores – Algoritmos, Pascal e 
C/C++. Pearson Prentice Hall, 2003. 
 
27

Outros materiais