Estruturas de Dados - Programação Recursiva

Prévia do material em texto

CIC/UnB - Estruturas de 
dados
Programação recursiva
Definição de recursão
● Em matemática vários objetos são definidos 
a partir de um processo que os produz. Por 
exemplo, o número π é a razão entre a 
circunferência e o diâmetro de um circulo.
● O fatorial de um número inteiro n é assim 
definido:
n! = 1 se n == 0
n! = n * (n-1) * (n-2) * ... * 1 se n > 0
Definição de Fatorial
● Assim,
 0! == 1
 1! == 1
 2! == 2 ( 2 * 1 )
 3! == 6 ( 3 * 2 * 1 )
 4! == 24 ( 4 * 3 * 2 * 1 )
 
e assim por diante
Definição de Fatorial
● Implementação interativa de fatorial:
#include <stdio.h>
int fat(int n) {
 int x, prod = 1;
 if (n!=0) for (x=n; x>0; x--) prod *=x;
 return (prod);
}
int main() {
 int i=0;
 while (i>=0){
 printf("Entre valor entre 0 e 12 inclusive ou valor <0 para terminar:");
 scanf("%d", &i);
 if (i>=0) printf("Fatorial de %d = %d\n", i, fat(i));
 }
 return 0;
} 
Programa p/ Fatorial
● ./fat1
● Entre valor entre 0 e 12 inclusive ou valor <0 para terminar:0
● Fatorial de 0 = 1
● Entre valor entre 0 e 12 inclusive ou valor <0 para terminar:1
● Fatorial de 1 = 1
● Entre valor entre 0 e 12 inclusive ou valor <0 para terminar:2
● Fatorial de 2 = 2
● Entre valor entre 0 e 12 inclusive ou valor <0 para terminar:9
● Fatorial de 9 = 362880
● Entre valor entre 0 e 12 inclusive ou valor <0 para terminar:10
● Fatorial de 10 = 3628800
● Entre valor entre 0 e 12 inclusive ou valor <0 para terminar:11
● Fatorial de 11 = 39916800
● Entre valor entre 0 e 12 inclusive ou valor <0 para terminar:12
● Fatorial de 12 = 479001600
● Entre valor entre 0 e 12 inclusive ou valor <0 para terminar:13
● Fatorial de 13 = 1932053504
● Entre valor entre 0 e 12 inclusive ou valor <0 para terminar:-1
Limites em C
● Os tipos de variáveis em C têm seus limites, que 
podem variar em cada implementação:
– char: 0 .. 256
– signed char: -127..127
– int: -32767..32767
– unsigned int: 0 .. 65535
– long int: -2.147.483.647 a 2.147.483.647
– float: 6 dígitos de precisão
– double: 10 dígitos de precisão
– expoente: -37 .. +37
Revisão da definição de 
fatorial
● Vamos fazer uma revisão de definição de fatorial:
0 ! = 1
1 ! = 1 * 0 !
2 ! = 2 * 1!
3 ! = 3 * 2!
4 ! = 4 * 3!
...
n ! = n * (n -1)!
● Portanto, o fatorial de um número inteiro n maior ou igual a 0 
é:
 
 1, se n == 0
 n * (n-1)!, para todos os demais valores
Programa recursivo p/ 
fatorial
● Isso pode ser facilmente implementado em uma linguagem 
recursiva, como o C. São denominadas recursivas as 
linguagens que, dotadas de procedures ou funções, permitem 
que estas chamem a si mesmas:
float fat(int n) {
 if (n == 0) return (1); 
 else return (n * fat(n-1)); 
}
int main() {
 int i=0;
 while (i>=0){
 printf("Entre valor inteiro >=0 ou valor <0 para terminar:");
 scanf("%d", &i);
 if (i>=0) printf("Fatorial de %d = %f\n", i, fat(i));
 }
 return 0;
}
Programa modificado
● Para auxiliar a compreensão da pilha de execução vou introduzir 
uma versão ligeiramente modificada do programa fatorial:
float fat(int n) {
 int x; /* define uma variável local x */
 x=n-1;
 if (n == 0) return (1); 
 else return (n * fat(x)); /* ao invés de passar n-1, passa-se x */
}
int main() {
 int i=0;
 while (i>=0){
 printf("Entre valor inteiro >=0 ou valor <0 para terminar:");
 scanf("%d", &i);
 if (i>=0) printf("Fatorial de %d = %f\n", i, fat(i));
 }
 return 0;
}
Programa recursivo
● Mas, como pode o compilador resolver essa questão?
● A resposta é que, na implementação de um procedimento recursivo, o 
código gerado pelo compilador da linguagem manipula uma pilha.
● No momento em que é feita uma chamada de procedimento, o 
compilador instala em uma pilha de execução, o(s) parâmetros que o 
procedimento deve receber. No nosso exemplo de fatorial, a chamada 
deve providenciar um valor inteiro, referido como ''n'' internamente na 
procedure ''fat''. Por exemplo, ao chamarmos ''fat (4)'' a primeira 
coisa que é feita é o empilhamento deste valor no stack de execução:
 4
Contexto da procedure
● A seguir, o compilador gera código para armazenar informações 
importantes para o retorno, quando a procedure chamada terminar, e 
para viabilizar a referência a variáveis do contexto global e local – 
essas informações denominam-se de registro de contexto, e não as 
detalharei agora. Da mesma forma, reserva espaço no stack para as 
eventuais variávels locais (no exemplo, a variável ''x'')
 x: Ponteiro de topo
 Reg.
 de
 contex
 to
 n: 4
Contexto da procedure
● A variável ''x'' logo ganha o valor de n-1, que é ''3'', e a seguir será 
feita nova chamada de procedure, passando como valor o valor de ''x''
 x: 3 Ponteiro de topo
 Reg.
 de
 contex
 to
 n: 4
Contexto da procedure
● Como o valor de n é > 0, a procedure calculará o seu elemento de 
retorno pelo valor de n * fat (x). Dessa forma, ela colocará o valor 4 
(de n) no stack e fará a chamada de fat (x) que agora tem o valor 3, 
para multiplicá-los:
 3 valor de x (parâmetro prox chamada)
 4 valor de n
 x: 3 
 Reg.
 de
 contex
 to
 n: 4
Contexto da procedure
● Na nova instância da procedure, tudo acontecerá, de novo, no topo da 
pilha: será colocado o valor do parâmetro, representado por n' , montado 
novo registro de contexto e novo espaço para x':
 x': 2 Ponteiro de topo 
 Novo
 Ctxt
 n': 3
 4 Copia de valor de n (para multiplicar)
 x: 3 
 Reg.
 de
 contex
 to
 n: 4
Contexto da procedure
● Veja esquema simplificado da pilha quando chegamos ao fatorial de 0:
 
 x'''': -1 topo da pilha
 ctx
 n'''': 0 
 1
 x''': 0
 ctx
 n''': 1 
 2
 x'': 1
 ctx
 n'': 2
 3
 x': 2
 ctx
 n': 3
 4
 x: 3
 ctx
 n: 4
 
Contexto da procedure
● Para n==0 a função retorna o valor 1 no topo da pilha:1 topo da pilha 
 1
 x''': 0
 ctx
 n''': 1 
 2
 x'': 1
 ctx
 n'': 2
 3
 x': 2
 ctx
 n': 3
 4
 x: 3
 ctx
 n: 4
 
Contexto da procedure
● O valor retornado é multiplicado pelo valor que estava no topo 
( 1 * 1) e a próxima instância retorna este resultado, tirando 
todo o seu contexto da pilha: 
 
 1 Novo topo
 2
 x'': 1
 ctx
 n'': 2
 3
 x': 2
 ctx
 n': 3
 4
 x: 3
 ctx
 n: 4
 
Contexto da procedure
● O valor retornado é multiplicado pelo valor que estava no topo 
( 1 * 2) e a próxima instância retorna este resultado, tirando 
todo o seu contexto da pilha: 
 
 
 
 
 
 2 Novo topo
 3
 x': 2
 ctx
 n': 3
 4
 x: 3
 ctx
 n: 4
 
Contexto da procedure
● O valor retornado é multiplicado pelo valor que estava no topo 
( 6 * 4) e a próxima instância retorna este resultado, tirando 
todo o seu contexto da pilha:
 
 
 
 
 
 
 
 6 Novo topo
 4
 x: 3
 ctx
 n: 4
 
Contexto da procedure
● O valor retornado é multiplicado pelo valor que estava no topo 
( 6 * 4) e a próxima instância retorna este resultado, tirando 
todo o seu contexto da pilha e deixando o resultado (24) para 
o procedimento que a chamou, que no caso é o programa 
principal, que imprimirá o valor. 
 
 
 
 
 
 
 
 
 
 
 
 24 Novo topo 
 
Máquina virtual
● int fat(int n) {
 int x; /* define uma variável local x */
 x=n-1;
 if (n == 0) return (1); 
 else return (n * fat(x)); /* ao invés de passar n-1, passa-se x */
}
 
● A compilação de uma função como a vista acima pode ser auxiliada por 
 um código intermediário voltado para pilha como o seguinte:
fat:enterfunc(1,2)
 localaddr 1 const 1
 localvalue -1 return 1
 const 1 jump 11
 sub localvalue -1
 store 1 localvalue 1
 localvalue -1 funccall (fat)
 const 0 mult
 equal return 1
 jumpfalse 8
Máquina virtual
● Uma máquina virtual como essa interpreta a tradução do 
programa fonte para uma notação pós fixa do programa, 
idealizada para ser executada em uma pilha virtual. Todas as 
instruções exemplificadas manipulam a pilha de execução. Por 
exemplo, o primeiro comando,
 
 x=n-1
foi traduzido para
 localaddr 1 
 localvalue -1 
 const 1 
 sub 
 store 1 
 
Máquina virtual
● O que significa:
localaddr 1 - empilhe o endereço da 1a variável local 
 
localvalue -1 – empilhe o valor do parâmetro na posição contexto -1
 const 1 - empilhe o valor 1
 
 sub - subtraia o valor do topo do valor do topo -1, deixe o result no topo -1
 store 1 - armazene o valor do topo no endereço que está no topo -1 
Máquina virtual
● A condição do if 
 
 if (n==0)
foi traduzida para 
 
● 
 localvalue -1 - empilha o valor de n, o ultimo e único parâmetro 
 const 0 - empilha a constante 0 
 equal - verifica se o topo = topo-1, deixa 1 ou 0 no topo-1 
 jumpfalse 8 - verifica se o topo é 1 ou 0 – se for 0, salta 8 palavras
 (isso é, vai para a parte else do if)
Máquina virtual
● A parte then do if 
 
 return(1);
foi traduzida para 
 
 const 1 - empilha a constante 1
 return 1 - retorna da função, sabendo que ficou uma palavra no topo
 do stack (para efeito de fazer o desempilhamento adequado)
 jump 11 - para pular a parte else do if (neste caso sabemos que este
 comando nunca será executado porque é precedido de um
 return)
 
Máquina virtual
● A parte else do if 
 
 return (n * fat(x))
ficou assim:
 
● A compilação de uma função como a vista acima pode ser auxiliada por um 
código intermediário voltado para pilha como o seguinte:
 
 localvalue -1 - empilha o valor do parâmetro n
 localvalue 1 - empilha o valor da variável x
 funccall (fat) - chama a função – olabel fat conterá a diferença de
 endereços (atual e da função) – lembre-se que a
 função em questão ao retornar deixa um operando
 no stack
 mult - multiplica o topo-1 pelo topo, resultado no topo-1
 return 1 - retorna a quem chamou, deixando um operando no
 stack
 
Outros exemplos de 
recursão
● Definição recursiva de multiplicação de 
números naturais:
a * b = a se b == 1
a * b = a + a * (b – 1) se b > 1
Faça rapidamente uma implementação da 
multiplicação natural em C
 
Outros exemplos de 
recursão
● Definição recursiva de multiplicação de 
números naturais:
 double mult (int a, int b) {
 if (b == 1) return (a); 
 else return (a + mult (a,(b-1))); 
}
 scanf("%d %d", &i,&j);
 if ((i>1)&&(j>1))
 printf("Produto=%10.0f\n", mult(i,j));
Outros exemplos de 
recursão
● Definição da seqüência de Fibonacci:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
● A partir do terceiro número o seu valor é 
sempre a soma dos dois anteriores.
● A seqüência estabelece um número real, 
chamado número de ouro, denotado pela letra 
grega  (phi) com valor arredondado de 1,618, 
presente na natureza, nas artes, na arquitetura. 
A divisão de um número da seqüência pelo seu 
antecessor vai se aproximando sucessivamente 
de 
 
Outros exemplos de 
recursão
● Leonardo de Pisa – Fibonacci
(1170-1250)
● Introduziu os números arábicos
na Europa através do Livro do Ábaco
em 1228, impulsionando o seu uso
em contabilidade, matemática financeira,
percentagens, etc.
 
Outros exemplos de 
recursão
● Matematicamente, pode-se definir, de forma 
recursiva, a seqüência famosa:
fib (n) = n, se n==0 ou n==1
fib (n) = fib (n-2) + fib (n-1), para n > 1
● Pense um pouco na implementação da 
função em linguagem C 
Fibonacci recursiva em C
● int fib (int n) {
 if ((n == 0)||(n == 1)) return (n); 
 else return (fib(n-2) + fib(n-1)); 
}
int main() {
 int i, j; float k, ant=0;
 printf("Entre com o número de elementos da seqüência: ");
 scanf("%d", &i);
 for (j=0;j<=i;j++) {
 k=fib(j);
 if (ant!=0) printf("%5.0f (phi=%10.8f)\n ",k, k/ant); 
 ant=k;
 }
 printf("\n");
 return 0;
}
Fibonacci recursiva em C
Entre com o número de elementos da seqüência: 15
 1 (phi=1.00000000)
 2 (phi=2.00000000)
 3 (phi=1.50000000)
 5 (phi=1.66666667)
 8 (phi=1.60000000)
 13 (phi=1.62500000)
 21 (phi=1.61538462)
 34 (phi=1.61904762)
 55 (phi=1.61764706)
 89 (phi=1.61818182)
 144 (phi=1.61797753)
 233 (phi=1.61805556)
 377 (phi=1.61802575)
 610 (phi=1.61803714)
A busca binária
● A busca (ou verificação de existência) de um 
elemento em um conjunto pode ser demorada 
ou complicada
● Se o conjunto estiver ordenado a demora pode 
ser reduzida através da busca binária
● O processo consiste em verificar-se o ponto 
intermediário e, caso não seja este o elemento 
procurado, buscá-lo na metade apropriada 
(superior ou inferior), recursivamente
A busca binária
● a[0] == 2 Procurar 6
a[1] == 4 MIN=0 MAX=9
a[2] == 6
a[3] == 8
a[4] == 10 <= (MIN+MAX)/2==4
a[5] == 12
a[6] == 14
a[7] == 16
a[8] == 18
a[9] == 20
A busca binária
● a[0] == 2 Procurar 6
a[1] == 4 <= MIN=0 MAX=3
a[2] == 6
a[3] == 8
a[4] == 10 (MIN+MAX)/2 ==1
a[5] == 12
a[6] == 14
a[7] == 16
a[8] == 18
a[9] == 20
A busca binária
● a[0] == 2 Procurar 6
a[1] == 4 MIN=2 MAX=3
a[2] == 6 <=
a[3] == 8
a[4] == 10 (MIN+MAX)/2==2
a[5] == 12
a[6] == 14
a[7] == 16
a[8] == 18 Encontra em A[2] 
a[9] == 20 
Eficiência da busca 
binária
● Na busca seqüência o comprimento de busca 
médio é n/2 
● Na busca binária o comprimento de busca 
máximo é (log
2
 n) + 1
● n busca média seq busca max bin 
 10 5 4
100 50 7
1000 500 10
10000 5000 14
100000 50000 17