Baixe o app para aproveitar ainda mais
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
Compartilhar