Upload
others
View
2
Download
0
Embed Size (px)
Citation preview
Recursividade
Aula 9
� Em matemática vários objetos são definidos
apresentando-se um processo que os
produz.
� Ex PI (circunferência/diâmetro)
� Outra definição de um objeto por um
processo é o fatorial de um número
� Fatorial(n) ou n! � = n*(n-1)*(n-2)...(2)*1 se n >0
� =1 se n==0� Se formulamos:� 0! = 0
� 1! = 1� 2! = 2 * 1
� 3! = 3 * 2 * 1� 4! = 4 * 3 * 2 * 1� Não é possível listar a fórmula para fatorial de cada
inteiro
� Para evitar qualquer abreviatura e um cjto infinito de definições poderemos apresentar um algoritmo que
aceite um número inteiro n e retorne n!
prod = 1;
for (x = n; x > 0; x--)
prod *= x;
return prod;
ALGORITMO ITERATIVO: Requer de repetição
explícita até uma condição ser satisfeita.
� Um algoritmo pode ser considerado “Um programa ideal” sem quaisquer limitações práticas de um computador real e portanto
pode ser usado para definir uma função
matemática, entretanto uma função de C não
serve como definição matemática da função
fatorial por causa de limitações como
precisão e tamanho finito de uma máquina
real.
� Examinemos detalhadamente a definição de n! que lista uma fórmula separada para cada valor de n
� Ex 4! = 4 * 3 * 2 * 1 isso é igual a 4 * 3!
� Para todo n>0 verificamos que
n! = n* (n-1)!
� Podemos definir:
0! = 1
1! = 1 * 0!
2! = 2 * 1!
3! = 3 * 2!
4! = 4 * 3!
5! = 5 * 4!
� Se empregamos uma notação matemática temos que
� n! = 1 se n == 0
� n! = n * (n - 1)! se n >0
� Definição de uma função em termos de se mesma, aparentemente circular.
� Método conciso de escrever um número infinito de equações necessárias para definir n!
� Definição RECURSIVA
� A recursividade pode ser utilizada quando um problema puder ser definido em termos de si próprio.
� Por exemplo, quando um objeto é colocado entre dois espelhos planos paralelos e frente a frente surge uma imagem recursiva, porque a imagem do objeto refletida num espelho passa a ser o objeto a ser refletido no outro espelho e, assim, sucessivamente.
� Uma função recursiva chama ela mesma, mas com outros parâmetros.
Algoritmos Recursivos� A idéia básica de um algoritmo recursivo consiste em
diminuir sucessivamente o problema em um problema menor ou mais simples, até que o tamanho ou a simplicidade do problema reduzido permita resolvê-lo de forma direta, sem recorrer a si mesmo.
� Quando isso ocorre, diz que o algoritmo atingiu uma condição de parada, a qual deve estar presente em pelo menos um local dentro algoritmo.
� Sem esta condição o algoritmo não pára de chamar a si mesmo, até estourar a capacidade da pilha de execução, o que geralmente causa efeitos colaterais e até mesmo o término indesejável do programa.
Componentes de um algoritmorecursivo
� Condição de parada, quando a parte do problema pode ser resolvida diretamente,
sem chamar de novo a função recursiva.
� Outros comandos que resolvem uma parte do problema (chamando novamente a função
recursiva);
Algoritmos Recursivos
f1(..)
...
...
...
chama f1(..)
...
...
fim
f1(..)
...
...
...
condição de
parada!
f1(..)
...
...
chama f1(..)
...
...
1. 5! = 5 * 4!
2. 4! = 4 * 3!
3. 3! = 3 * 2!
4. 2! = 2 * 1!
5. 1! = 1 * 0!
6. 0! = 1
Cada caso é reduzido a um caso mais simples até
chegarmos ao caso 0! Que é definido
imediatamente como 1
Se voltarmos
6’ 0! = 1
5’ 1! = 1 * 0! = 1 * 1 = 1
4’ 2! = 2 * 1! = 2 * 1 = 2
3’ 3! = 3 * 2! = 3 * 2 = 6
2’ 4! = 4 * 3! = 4 * 6 = 24
1’ 5! = 5 * 4! = 5 * 24 = 120
� Se levamos esse processo a um algoritmos
teremos
if (n == 0) fact = 1;else {
x = n -1;ache o valor de x!. Chame-o de y;fact = n * y;}
Definição recursiva do processo do cálculo do
fatorial
int main(void){ int NUMERO, RESULTADO;
scanf("%d", &NUMERO);RESULTADO = FAT(NUMERO);printf("%d\n", RESULTADO); }
int FAT(int N){ int AUX;
if(N == 0) // condição de paradareturn 1;
AUX = N * FAT(N - 1);return AUX; }
� LEMBRE-SE!! N é variável local da função FAT. � É melhor a definição recursiva de fatorial?
� Programa principal:main
� NUMERO = 2
RESULTADO = FAT(2)
� Função FAT:PRIMEIRA CHAMADA
� N = 2
AUX = 2 * FAT(1)
1
� Função FAT:
PRIMEIRA CHAMADA
� N = 2
AUX = 2 * FAT(1)
� Função FAT:
SEGUNDA CHAMADA
� N = 1
AUX = 1 * FAT(0)
1 2
� Função FAT:
SEGUNDA CHAMADA
� N = 1
AUX = 1 * FAT(0)
� Função FAT:
TERCEIRA CHAMADA
� N = 0
condição de parada
atingida!!!
if (N = = 0)
return 1;
2 3
� Função FAT:
SEGUNDA CHAMADA
� N = 1
AUX = 1 * FAT(0)
AUX = 1
� Função FAT:
TERCEIRA CHAMADA
� N = 0
condição de parada
atingida!!!
if (N = = 0)
return 1;
1
2 3
� Função FAT:
PRIMEIRA CHAMADA
� N = 2
AUX = 2 * FAT(1)
AUX = 2
� Função FAT:
SEGUNDA CHAMADA
� N = 1
AUX = 1 * FAT(0)
AUX = 1
11
21
� Programa principal:
main
� NUMERO = 2
RESULTADO = FAT(2)
RESULTADO = 2
� Função FAT:
PRIMEIRA CHAMADA
� N = 2
AUX = 2 * FAT(1)
AUX = 2
22
1
Problemas associados a recursividade
� Recursões que não terminam!!!
� Um requisito fundamental é que a chamadarecursiva esteja sujeita à uma condição booleana que em um determinado momento irá se tornar falsa e não mais ativará a recursão (condição de parada!).
� Um subprograma recursivo deve terobrigatoriamente uma condição que controla sua execução ou término, sob pena de produzir uma computação interminável.
Multiplicação de números naturais
� Outro exemplo de definição recursiva
� O produto A*B em que a e b são inteiros
positivos pode ser definido como A somado a
se mesmo b vezes. Essa definição é
ITERATIVA
� Definição recursiva
a * b = a se b == 1
a * b = a * (b - 1) + a se b > 1
� Exemplo:
6 * 3 = 6 * 2 + 6 = 6 * 1 + 6 + 6 = 6 + 6 + 6 = 18
Exercício: Converter num algoritmo recursivo.
Observe padrão de definições recursivas (caso
simples e avaliação de casos mais simples)
Por que não podemos usar definições como ??
n! = (n + 1)! / (n + 1)
a * b = a * (b + 1) - a
A seqüência de Fibonacci
� Seqüência de inteiros do tipo
� 0, 1, 2, 2, 3, 5, 8, 13, 21, 34
� Cada elemento da seqüência é a soma dos dois elementos anteriores. Se permitimos que fib(0) = 0 e fib(1) = 1
� fib(n) = n se n == 0 ou n == 1
� fib(n) = fib(n-2) + fib(n-1) se n >= 2
� Que diferencia a definição da seqüência de Fibonacci da do fatorial e da multiplicação dos números naturais??
A seqüência de Fibonacci
� Note que:
� fib(6) = fib(5) + fib(4)
� = fib(4) + fib(3) + fib(3) + fib(2)
� = fib(3) + fib(2) + fib(3) + fib(3) + fib(2)
E assim por diante. Que tem de errado??????
Seria mais eficiente lembrar quanto é fib(3) na primeira
vez que ele for chamado
Solução iterativa:if (n
Solução recursiva
FIB(5)
FIB(5)
FIB(3)FIB(4)
FIB(5)
FIB(3)FIB(4)
FIB(3) FIB(2)
FIB(5)
FIB(3)FIB(4)
FIB(3) FIB(2) FIB(2) FIB(1)
FIB(5)
FIB(3)FIB(4)
FIB(3) FIB(2) FIB(2) FIB(1)
FIB(1)FIB(2)
FIB(5)
FIB(3)FIB(4)
FIB(3) FIB(2) FIB(2) FIB(1)
FIB(1)1
FIB(5)
FIB(3)FIB(4)
FIB(3) FIB(2) FIB(2) FIB(1)
11
FIB(5)
FIB(3)FIB(4)
2 FIB(2) FIB(2) FIB(1)
11
FIB(5)
FIB(3)FIB(4)
2 FIB(2) FIB(1)
11
1
FIB(5)
FIB(3)FIB(4)
2 FIB(1)
11
1 1
FIB(5)
FIB(3)FIB(4)
2
11
1 1 1
FIB(5)
FIB(3)3
2
11
1 1 1
23
2
11
1 1 1
FIB(5)
5
23
2
11
1 1 1
Resposta: O 5º termo da série é 5.
Torres de Hanoi
� Problema criado pelo matemático francês EdouardLucas, em 1883;
� 3 torres;
� x discos de vários tamanhos na primeira torre;
� Objetivo: transportar os discos, 1 a 1, para a terceiratorre;
� Regras:� nunca colocar um disco maior sobre um disco menor;
� pode-se mover um único disco por vez;
� nunca colocar um disco noutro lugar que não numa das três hastes.
Torres de Hanoi
Torres de Hanoi� Lucas também criou uma “lenda” que dizia que em
Benares, durante o reinado do imperador Fo Hi, existia um templo que marcaria o centro do universo. Dentro deste templo, alguns monges moviam discos de ouro entre 3 torres de diamante. Deus colocou 64 discos de ouro em uma das torres na hora da criação do universo. Diz-se que, quando os monges completarem a tarefa de transportar todos os discos para a terceira torre, o universo terminará.
� (como vai levar pelo menos 264 - 1 movimentos para completar a tarefa, estamos a salvo por enquanto. Assumindo que os monges realizem 1 movimento por segundo, e não cometam erros, eles irão levar um total de 585,000,000,000 anos.)
Como resolver?
� Sejam 4 discos na torre 1.
� Problema principal: Mover 4 discos da torre 1
para a torre 3.
Recursão!
� Mover 4 discos da torre 1 para a torre 3:
� mover 3 discos da torre 1 para a torre 2;
� mover 1 disco da torre 1 para a torre 3;
� mover 3 discos da torre 2 para a torre 3.
Recursão!
� Mover 4 discos da torre 1 para a torre 3:
• mover 3 discos da torre 1 para a torre 2;
• mover 1 disco da torre 1 para a torre 3;
• mover 3 discos da torre 2 para a torre 3.
Recursão!
� Mover 4 discos da torre 1 para a torre 3:
• mover 3 discos da torre 1 para a torre 2;
• mover 1 disco da torre 1 para a torre 3;
• mover 3 discos da torre 2 para a torre 3.
Recursão!
� Mover 4 discos da torre 1 para a torre 3:
• mover 3 discos da torre 1 para a torre 2;
• mover 1 disco da torre 1 para a torre 3;
• mover 3 discos da torre 2 para a torre 3.
Divisão do problema
� Logo o problema principal:
� Mover 4 discos da torre 1 para a torre 3
� Se transforma em um problema menor:
� mover 3 discos da torre 1 para a torre 2;
� mover 1 disco da torre 1 para a torre 3;
� mover 3 discos da torre 2 para a torre 3.
� Mas, como mover 3 discos?
Divisão do problema
� Mover 3 discos da torre 1 para a torre 2:
� mover 2 discos da torre 1 para a torre 3;
� mover 1 disco da torre 1 para a torre 2;
� mover 2 discos da torre 3 para a torre 2.
Divisão do problema
� Mover 3 discos da torre 1 para a torre 2:
• mover 2 discos da torre 1 para a torre 3;
• mover 1 disco da torre 1 para a torre 2;
• mover 2 discos da torre 3 para a torre 2.
Divisão do problema
� Mover 3 discos da torre 1 para a torre 2:
• mover 2 discos da torre 1 para a torre 3;
• mover 1 disco da torre 1 para a torre 2;
• mover 2 discos da torre 3 para a torre 2.
Divisão do problema
� Mover 3 discos da torre 1 para a torre 2:
• mover 2 discos da torre 1 para a torre 3;
• mover 1 disco da torre 1 para a torre 2;
• mover 2 discos da torre 3 para a torre 2.
Algoritmo
� Mover x discos, da torre a para a torre b:
� mover (x-1) discos, da torre a para a torre c
� mover 1 disco da torre a para a torre b
� mover (x-1) discos, da torre c para a torre b
� Função de parada:
� Se o número de discos = 1, move direto.
Observações
� Sejam 3 torres, com os números 1, 2 e 3.
� Dadas 2 torres, como descobrir qual a
terceira?
� Isto é, dadas as torres 1 e 3, como descobrir
que a outra torre é a 2?
� Dadas as torres 2 e 3, como descobrir que a
outra torre é a 1?
Observação
� Note: 1 + 2 + 3 = 6
� Logo: A outra torre é
6 - (soma das torres indicadas)
� Exemplos:
� torres 1 e 2
� Outra torre: 6 - (1 + 2) = 6 - 3 = 3
� torres 2 e 3
� Outra torre: 6 - (2 + 3) = 6 - 5 = 1
Soluçãovoid HANOI(int ND, int DE, int PARA)
{int OUTRA_TORRE = 6 - (DE + PARA);
if(ND == 1){printf("Mover disco da torre %d para a
torre %d.\n", DE, PARA);return;
}
HANOI(ND-1, DE, OUTRA_TORRE);HANOI(1, DE, PARA);HANOI(ND-1, OUTRA_TORRE, PARA);return;
}
SoluçãoDigite o numero de discos: 4
Mover disco da torre 1 para a torre 2.Mover disco da torre 1 para a torre 3.Mover disco da torre 2 para a torre 3.Mover disco da torre 1 para a torre 2.Mover disco da torre 3 para a torre 1.Mover disco da torre 3 para a torre 2.Mover disco da torre 1 para a torre 2.Mover disco da torre 1 para a torre 3.Mover disco da torre 2 para a torre 3.Mover disco da torre 2 para a torre 1.Mover disco da torre 3 para a torre 1.Mover disco da torre 2 para a torre 3.Mover disco da torre 1 para a torre 2.Mover disco da torre 1 para a torre 3.Mover disco da torre 2 para a torre 3.Pressione qualquer tecla para continuar . . .
� Mover disco da torre 1 para a torre 2.
� Mover disco da torre 1 para a torre 3.
� Mover disco da torre 2 para a torre 3.
� Mover disco da torre 1 para a torre 2.
� Mover disco da torre 3 para a torre 1.
� Mover disco da torre 3 para a torre 2.
� Mover disco da torre 1 para a torre 2.
� Mover disco da torre 1 para a torre 3.
� Mover disco da torre 2 para a torre 3.
� Mover disco da torre 2 para a torre 1.
� Mover disco da torre 3 para a torre 1.
� Mover disco da torre 2 para a torre 3.
� Mover disco da torre 1 para a torre 2.
� Mover disco da torre 1 para a torre 3.
� Existem linguagens de programação que não suportam recursividade como FORTAM, COBOL e muitos linguagens de máquina
� Porem soluções recursivas podem ser simuladas se entendermos o conceito e funcionamento da recursividade
� Não é raro que um programador consiga enunciar uma solução recursiva para um problema, as vezes a solução recursiva é a mais natural e simples porem as soluções recursivas são com freqüência mais dispendiosas que a solução não recursiva.
� Em geral uma solução não recursiva de um programa executarácom mais eficiência em termos de espaço e tempo, isso acontece porque a solução não recursiva evita o trabalho extra de entrar e sair de um bloco e o empilhamento de desnecessário de variáveis
� Contudo verificaremos que a solução recursiva é as vezes o método mais natural e lógico de desenvolver como é o caso das torres de Hanoi e menos propenso a erros
� Conflito EFICIENCIA DA MAQUINA X EFICIENCIA DO PROGRAMADOR
� Nestes casos versões simuladas dos casos recursivos é uma excelente solução
� Que acontece quando uma função é chamada??
1. Passar argumentos: Para um parâmetro em C uma copia é criada localmente dentro da função e quaisquer mudança e feita nessa copia local. O original não é alterado
2. Alocar e inicializar variáveis locais: Depois que os argumentos forem passados as variáveis locais da função serão alocadas. As diretamente declaradas na função e as temporais
3. Transferir o controle para a função: Deve ser passado o endereço de retorno como parâmetro
� Quando retorna que acontece?
1. O endereço de retorno é recuperado e
armazenado num logar seguro
2. A área de dados da função é liberada
3. Usa-se um desvio para o endereço de
retorno salvo anteriormente, deve também
salvar se os valores de retorno para que o
chamador possa recuperar esse valor.
Chamada de b Chamada de c
Endereço de
retorno
Chamada de d
Endereço de
retorno
Endereço de
retorno
controle
Programa principal Procedimento bProcedimento c Procedimento d
Chamada de b Chamada de c
Endereço de
retorno
Chamada de d
Endereço de
retorno
controle
Programa principal Procedimento bProcedimento c
� Observe que a seqüência de endereços de retorno forma uma pilha isto é o mais recente endereço de retorno a ser incluído na cadeia é o primeiro a ser removido. Em qualquer ponto só poderemos acessar o endereço de retorno a partir da função
atualmente em execução que representa o topo da pilha. Quando uma pilha é esvaziada (isto é quando
a função retornar) será revelado um novo topo dentro da rotina de chamadas.
� Chamar uma função tem o efeito de incluir um
elemento numa pilha e retornar da função de eliminá-lo
� Cada vez que uma função recursiva chama a
si mesma uma área de dados totalmente
nova para essa chamada precisa ser
alocada. Essa área contem todos os
parâmetros variáveis locais temporárias e
endereços de retorno. Todo retorno acareia a
liberação da atual área de dados. Sugere-se
o uso de uma pilha
� Poderemos usar uma estrutura do tipo
#define MAXSTACK 50;
struct stack{
int top;
struct dataarea item[MAXSTACK]
}
� Passos da conversão
� Desenvolver caso recursivo
� Desenvolver simulação com todas as pilhas e temporários
� Eliminar todas as pilhas e variáveis supérfluas
� Quando uma pilha não pode ser eliminada da versão não recursiva e quando a versão recursiva não contem nenhum dos parâmetros adicionais o variáveis locais, a versão recursiva pode ser tão o mais veloz que a não recursiva sob um compilador eficiente. Exemplo Torres de Hanoi
� O fatorial que não precisa pilha na implementação não recursiva e a geração de números de fibonacci onde temos uma chamada desnecessária e também não precisa de pilha a solução recursiva deve ser evitada na pratica
� Até onde uma solução recursiva pode ser transformada em direta dependerá do problema e a engenhosidade do programador
Simulação de Recursividadestruct stack {
int top;
struct dataarea item[MAXSTACK];
};
void popsub(struct stack *s, struct dataarea *a){
*a = s->item[s->top];
s->top--;
}
void push(struct stack *s, struct dataarea *a){
s->top++;
s->item[s->top] = *a;
}
Simulação de Recursividade
int fact(int n){
int x, y;
if (n==0)
return(1);
x = n-1;
y = fact(x);
return (n * y);
}
Ponto 2 para retornar (label1: return(result);)
Ponto 1 para retornar (labe2 y = result;)
Simulação de Recursividade
struct dataarea{
int param; //parametro simulado (n)
int x; //variaveis atuais da chamada
long int y;
short int retaddr; //endereço de retorno (1 ou 2)
};
switch(i){
case 1: goto label1; //retorno ao prg principal
case 2: goto label2; //simulando à atribuição do valor //retornado à variavel y na execução//anterior de fact
}
Simulação de Recursividade
//retorno a partir de fact
result = valor a ser retornado;
i = currarea.retaddr;
popsub(&s, &currarea);
switch(i){
case 1: goto label1;
case 2: goto label2;
}
Simulação de Recursividade
//chamada introduz a atual área na pilha
//atualiza os valores dos parâmetros e
//transfere o controle para o inicio da rotina
push(&s, &currarea);
currarea.param = currarea.x;
currarea.retaddr = 2;
goto start;
long int simfact(int n){
struct dataarea currarea;
struct stack s;
short i;
long int result;
s.top = -1;
currarea.param = 0;
currarea.x = 0;
currarea.y = 0;
currarea.retaddr = 0;
push (&s, &currarea);
currarea.param = n;
currarea.retaddr = 1;
start:
if (currarea.param ==0){
result = 1;
i = currarea.retaddr;
popsub(&s, &currarea);
switch(i){
case 1: goto label1;
case 2: goto label2;
}
}
currarea.x = currarea.param -1;
push(&s, &currarea);
currarea.param = currarea.x;
currarea.retaddr = 2;
goto start;
label2:
currarea.y = result;
result = currarea.param*currarea.y;
i = currarea.retaddr;
popsub(&s, &currarea);
switch(i){
case 1: goto label1;
case 2: goto label2;
}
label1:
return result;
}
Simulação de Recursividade
� São necessárias todas as variáveis temporais? (n, x, y)
� n necessita ser empilhada (y=n*fact(x);)
� Embora x seja definida na chamada nunca seráusada depois de retornar (se x e y não fossem declaradas na função e sim globais, a rotina funcionaria igualmente bem.
� x e y não precisam ser empilhadas
� E o endereço de retorno?? Só existe um endereço de retorno importante (fact), mas se não empilhamos a area de dados artificial UNDERFLOW
� Podemos fazer popandtest...
#include
#include
#define MAXSTACK 50
struct stack {
int top;
int param[MAXSTACK];
};
int empty(struct stack *s){
return (s->top == -1);
}
void popandtest(struct stack *s, int *a,
short int *und){
if (!empty(s)){
und = 0;
*a = s->param[s->top];
s->top--;
return;
}
*und = 1;
}
void push(struct stack *s, int *a){
s->top++;
s->param[s->top] = *a;
}
label2:
y = result;
result = currparam*y;
popandtest(&s, &currparam, &und);
switch(und){
case 1: goto label1;
case 0: goto label2;
}
label1:
return(result);
}
int simfact1(int n){
struct stack s;
short int und;
long int result, y;
int currparam, x;
s.top = -1;
currparam = n;
start:
if (currparam == 0){
result = 1;
popandtest(&s, &currparam, &und);
switch(und){
case 0: goto label2;
case 1: goto label1;
}
}
x = currparam -1;
push(&s, &currparam);
currparam = x;
goto start;
Simulação de Recursividade
� As instruções goto start e goto label2;
?????? Repetições de código
� Para currparam == 0 e currparam != 0
popandtest(&s, &currparam, &und);
switch(und){
case 0: goto label2;
case 1: goto label1;
}
int simfact2(int n){
struct stack s;
short int und;
long int y;
int x;
s.top = -1;
x = n;
start:
if (x == 0) y = 1;
else{
push(&s, x--);
goto start;
}
label1:
popandtest(&s, &x, &und);
if(und == 1) return(y);
label2:
y*=x;
goto label1;
}
Repetição normal
Repetição normal
int simfact3(int n){
struct stack s;
short int und;
long int y;
int x;
s.top = -1;
x = n;
start:
while (x!=0) push(&s, x--);
y = 1;
popandtest(&s, &x, &und);
label1:
while (und == 0){
y*=x;
popandtest(&s, &x, &und);
}
return (y);
}
int simfact4(int n){
long int y;
int x;for(y=x=1; x