00.ED.Recursividade-2014-1

Prévia do material em texto

DCC013 
 
Estruturas de Dados 
Recursividade 
Recursividade em Procedimentos e Funções 
 Um procedimento ou função é recursivo (ou 
recorrente) quando chama a si próprio para 
atingir o resultado a que se propõe. 
 A recursividade é uma estratégia que pode ser 
utilizada sempre que o cálculo de uma função 
para o valor n, pode ser descrita a partir do 
cálculo desta mesma função para o valor 
anterior (n - 1). 
 Exemplo – Função fatorial: 
n! = n * (n - 1) * (n - 2) * (n - 3) *....* 1 
n! = n * (n - 1)! 
Recursividade 
2 
Recursividade em Procedimentos e Funções 
 A recursividade pode ser: 
Recursividade 
3 
Direta: Indireta: 
procedimento A . . . { 
--------------- 
A . . . 
--------------- 
} // fim-procedimento A; 
procedimento A . . . { 
 --------------- 
 B . . . 
 --------------- 
} // fim-procedimento A; 
procedimento B . . . { 
 --------------- 
 A . . . 
 --------------- 
} // fim-procedimento B; 
A recursividade pode ser usada em três 
situações: 
 Em procedimento ou função que resolve 
problema definido recursivamente. 
 Em procedimento ou função onde se deseja 
substituir iteração por recorrência. 
 Para definir estruturas de dados dinâmicas 
(listas, árvores etc.). 
Recursividade 
4 
Problema Definido Recursivamente 
Recursividade 
5 
 1, se N = 0 
 N * (N – 1)!, se N > 0 
Ex.: N! = 
int Fat(int n) 
{ 
 if(n == 0) 
 return 1; 
 else 
 return n * Fat(n-1); 
} 
Recursividade em Procedimentos e Funções 
 Obs.: Condição de parada: 
 Todo módulo (procedimento ou funções) recursivo possui 
uma condição de parada, cujo teste pode permitir a 
terminação da execução do módulo. 
 Exemplo: 
Recursividade 
6 
int Fat(int n) 
{ 
 if(n == 0) // condicao de parada 
 return 1; 
 else 
 return n * Fat(n-1); 
} 
Recursividade em Procedimentos e Funções 
 Obs.: Execução de um Módulo Recursivo: 
 Quando um módulo é chamado para execução, é criado 
um Registro de Ativação na Pilha de Execução do 
programa. 
 Esse registro de ativação armazena os parâmetros e 
variáveis locais do módulo bem como o “ponto de 
retorno” no programa ou subprograma que o chamou. 
 Ao final da execução desse módulo, o registro é 
desempilhado e a execução volta ao ponto de retorno do 
programa ou subprograma que o chamou. 
Recursividade 
7 
Substituição de Iteração por Recorrência 
 Exemplo: Classificar os N elementos inteiros do 
vetor A em ordem crescente. 
 Solução iterativa: 
Recursividade 
8 
void SORT(int A[], int N) 
{ 
 int I, J, K, T; 
 for(I = 0; I < (N – 1); I++){ 
 J = I; 
 for(K = (I + 1); K < N; K++) 
 if(A[K] < A[J]) 
 J = K; 
 T = A[I]; 
 A[I] = A[J]; 
 A[J] = T; 
 } 
} //fim do procedimento SORT 
Substituição de Iteração por Recorrência 
 Identificação de duas estruturas de iteração (for): 
Recursividade 
9 
void SORT(int A[], int N) 
{ 
 int I, J, K, T; 
 for(I = 0; I < (N – 1); I++){ 
 J = I; 
 for(K = (I + 1); K < N; K++) 
 if(A[K] < A[J]) 
 J = K; 
 T = A[I]; 
 A[I] = A[J]; 
 A[J] = T; 
 } 
} //fim do procedimento SORT 
1 
2 
Substituição de Iteração por Recorrência 
 Substituindo o for mais interno (1) por um while, 
tem-se: 
 
 
 
 
 
 
 
 Para transformar o while em um procedimento 
recursivo, deve-se substituir a declaração 
“while(condição)” por uma alternativa 
“if(condição)” e o “}” que finaliza o while pela 
chamada recursiva. Assim: 
Recursividade 
10 
 K = (I + 1); 
 while(K < N){ 
 if(A[K] < A[J]) 
 J = K; 
 K++; 
 } 1 
Substituição de Iteração por Recorrência 
Recursividade 
11 
void MIN(int K, int N, int A[], int *J){ 
 if(K < N) 
 if(A[K] < A[*J]) 
 *J = K; 
 MIN(K + 1, N, A, J);//ou: K = K + 1; 
 //MIN(K, N, A, J); 
} // fim do procedimento MIN 
Substituição de Iteração por Recorrência 
 Substituindo o for mais interno (1) pela chamada do 
procedimento MIN, tem-se: 
Recursividade 
12 
 for(I = 0; I < (N – 1); I++){ 
 J = I; 
 K = I + 1; 
 MIN(K, N, A, &J) 
 T = A[I]; 
 A[I] = A[J]; 
 A[J] = T; 
 } 
1 
2 
Substituição de Iteração por Recorrência 
 Substituindo o for mais interno (1) pela chamada do 
procedimento MIN, tem-se: 
Recursividade 
13 
 for(I = 0; I < (N – 1); I++){ 
 J = I; 
 K = I + 1; 
 MIN(K, N, A, &J) 
 T = A[I]; 
 A[I] = A[J]; 
 A[J] = T; 
 } 
1 
2 
Substituição de Iteração por Recorrência 
 Substituindo o for mais interno (1) pela chamada do 
procedimento MIN, tem-se: 
 
 
 
 
 
 
 
 Repetindo o processo para o for mais externo (2), pode-
se obter o procedimento SORT1 a seguir: 
Recursividade 
14 
 for(I = 0; I < (N – 1); I++){ 
 J = I; 
 MIN(I + 1, N, A, &J) 
 T = A[I]; 
 A[I] = A[J]; 
 A[J] = T; 
 } 
1 
2 
Substituição de Iteração por Recorrência 
Recursividade 
15 
void SORT1(int I, int N, int A[]){ 
 int J, T; 
 if(I < (N – 1)){ 
 J = I; 
 MIN (I + 1, N, A, &J); 
 T = A[I]; 
 A[I] = A[J]; 
 A[J] = T; 
 SORT1(I + 1, N, A);//ou: I  I + 1; 
 //SORT1(I, N, A); 
 } 
} //fim do procedimento SORT1 
Substituição de Iteração por Recorrência 
 O procedimento SORT passa a ser: 
 
 
 
 
 Deve-se observar que o único objetivo do procedimento 
SORT passou a ser a chamada do procedimento SORT1. 
Portanto, pode-se iniciar o processo pela chamada: 
 SORT1 (1, N, A); 
 Analisar: quais as vantagens e desvantagens de se usar 
solução iterativa ou recursiva em procedimentos (ou 
funções)? 
Recursividade 
16 
void SORT(int A[], int N){ 
 SORT1(1, N, A);//ou: int I = 1; 
 //SORT1(I, N, A); 
} //fim do procedimento SORT 
Recursividade em Procedimentos e Funções 
 Exemplo: Série de Fibonacci: 
 
 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89... 
 
 Desenvolver um algoritmo iterativo e um 
recursivo, ambos para calcular o n-ésimo termo 
da série. 
Recursividade 
17 
Recursividade em Procedimentos e Funções 
Recursividade 
18 
int FibIter(int n){ 
 int ant = 1, atual = 1; 
 
 for(int k = 3; k <= n; k++){//n>=3 
 int aux = atual; 
 atual = atual + ant; 
 ant = aux; 
 } 
 return atual;//para n==1 ou n==2, atual é 1 
} 
int fib(int n){//versão recursiva 
 if(n <= 2) 
 return 1; 
 else 
 return fib(n-1) + fib(n-2); 
} 
Recursividade em Procedimentos e Funções 
Recursividade 
19 
fib(6) 
fib(5) fib(4) 
fib(4) fib(3) fib(2) 
1 fib(2) 
1 
fib(1) 
1 
fib(3) 
fib(2) 
1 
fib(1) 
1 
fib(2) 
1 
fib(3) 
fib(2) 
1 
fib(1) 
1 
Recursividade em Procedimentos e Funções 
 Comparação dos algoritmos iterativo e recursivo 
de Fibonacci : 
Recursividade 
20 
N Num somas Atribuições 
Iterativo 
Atribuições 
Recursivo 
6 5 15 25 
10 9 27 177 
15 14 42 1973 
20 19 57 21891 
25 24 72 242785 
30 29 87 2692537 
Recursividade em Procedimentos e Funções 
 Exercícios: 
1. Desenvolver um programa para ler um valor inteiro N  1, 
calcular e imprimir os N primeiros termos da série de 
Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, . . .Obs.: Apresentar duas soluções: 
1. Iterativa 
2. Recursiva, onde o programa principal deve chamar 
um procedimento recursivo que controla a geração e 
impressão dos N termos e a geração de cada termo da 
série deve ser realizada por uma função recursiva. 
Recursividade 
21 
Recursividade em Procedimentos e Funções 
 Exercícios: 
2. Desenvolver uma função recursiva para calcular a 
potência de um número: 
 O problema pode ser definido recursivamente? 
 
 Qual a condição de parada? 
 
Recursividade 
22 
Recursividade em Procedimentos e Funções 
 Exercícios: 
3. Qual o objetivo da função abaixo? 
 
 
 
 
 
Resposta: Calcula o MDC (máximo divisor comum) 
de dois números a e b (Algoritmo de Euclides). 
Recursividade 
23 
int f(int a, int b){ // considerar a > b 
 if (b = 0) 
 return a; 
 else 
 return f(b, a % b); 
} 
Recursividade em Procedimentos e Funções 
 Exercícios: 
4. Dado um vetor V ordenado com n posições reais, 
criar um algoritmo para retornar a posição de um 
valor x no vetor V através da realização de uma 
busca binária recursiva. 
Recursividade 
24 
Recursividade em Procedimentos e Funções 
 Exercícios: 
4. Busca binária recursiva – Solução: 
Recursividade 
25 
int buscab(int V[], int inicio, int final, int x) 
{ 
 int meio = (inicio + final) / 2;//ponto médio 
 if(V[meio] == x) return meio; 
 if(inicio == final) return -1; 
 if (V[meio] < x)//busca na primeira metade 
 return buscab(V, inicio, meio-1, x); 
 else //busca na segunda metade 
 return buscab(V, meio+1, final, x); 
} 
Recursividade em Procedimentos e Funções 
 Exercícios: 
4. Busca binária recursiva – Solução: 
Função empacotadora/Inicializadora 
Recursividade 
26 
int buscaBinaria(int V[], int tam, int Chave) 
{//V é um vetor de tamanho tam. 
 //Será retornado k tal que V[k]==Chave 
 //ou -1 caso contrário 
 
 //faz a busca binária de Chave 
 //em V no intervalo 0 a tam 
 return buscab(V,0,tam,Chave); 
} 
Recursividade em Procedimentos e Funções 
 Exercícios: 
5. Desenvolver uma função recursiva que receba um número 
inteiro n e retorne o valor do somatório: 
 n + (n-1) + (n-2) + . . . + 2 + 1 
6. Desenvolver uma função não recursiva equivalente à 
seguinte função: 
Recursividade 
27 
int f(int i){ 
 if(i > 1) 
 return i + f(i-1); 
 else 
 return 1; 
}