Recursividade e Funções Recursivas
Aleatoriedade
e Processos de Monte Carlo
Pedro Barahona
DI/FCT/UNL
Introdução aos Computadores e à Programação
2º Semestre 2006/2007
23 Março 2007
Recursividade Funções Recursivas. Aleatoriedade e Processos de Monte Carlo
1
Funções Encadeadas
•
Como foi visto em vários exemplos anteriores, na especificação de uma função
podem ser chamadas outras funções, que por sua vez podem chamar outras
funções.
•
Assim uma função (programa pode ser visto como um encadeamento de funções.
Por exemplo, a função ang_vec/2 chama a função mod_vec/2 na especificação
abaixo indicada
function a = ang_vec(V1,V2); % retorna ângulo em graus
M = prod_int(V1,V2))
cos = M /(mod_vec(V1) * mod_vec(V2))
a = acos(cos)*180/pi
endfunction
•
Em algumas linguagens de programação, em vez de funções são usados
procedimentos, mas a filosofia de encadeamento é semelhante.
•
De notar que o programa principal, pode ele próprio ser visto como uma função.
23 Março 2007
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
2
Funções Recursivas
•
Um caso particular ocorre quando as funções se chamam a si próprias, isto é,
quando as funções são recursivas.
•
Talvez o exemplo mais simples seja o da função factorial, que pode ser definida
(incompletamente) como
fact(n) = n * fact(n-1)
•
Nestas condições, tal como nos ciclos, levanta-se o problema da terminação. Se uma
função se chama a si própria, existe o risco de a computação se tornar infinita (entrar
em ciclo fechado ou “loop”).
•
É pois condição necessária para evitar estes ciclos infinitos que sejam definidas e
testadas em primeiro lugar as condições de fim da recursividade.
se n  0
1

fact(n)  
n * fact(n  1) se n  0
23 Março 2007
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
3
Funções Recursivas
•
Em geral, a recursividade é feita com base num conjunto recursivo (indutivo), definido
através de cláusulas
– de base; um ou vários elementos de base (que fecham a recursão)
– de recursão: uma definição recursiva que permite a obtenção de elementos a
partir de outros elementos.
•
Num grande número de casos, o conjunto recursivo utilizado é o conjunto dos
numeros inteiros, em que
– 1 (ou 0) é um número inteiro (cláusula de base)
– Se i é inteiro, i+1 também é inteiro (cláusula de recursão)
•
Tendo em conta esta estrutura recursiva, podemos definir (correctamente) a função
factorial tendo em conta a cláusula de base e a cláusula recursiva:
se n  0
1

fact(n)  
n * fact(n  1) se n  0
23 Março 2007
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
4
Funções Recursivas
•
No caso da função factorial basta então testar inicialmente se o parâmetro de entrada
é nulo. Em pseudo-código, a função é definida como
função fact(n)
se n = 0 então
fact  1
% elemento base
senão
fact  n * fact(n-1) % definição recursiva
fimse;
fimfunção;
•
Em Octave é definida de uma forma semelhante
function f = fact(n)
if n == 0
f = 1
else
f = n*fact(n)
endif;
endfunction;
23 Março 2007
se n  0
1

fact(n)  
n * fact(n  1) se n  0
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
5
Limites à Recursividade
•
De notar que para prevenir os ciclos infinitos, o Octave tem uma variável prédefinida,
max_recursion_depth, que limita o número de chamadas recursivas de uma função.
•
Por omissão (“default”), o valor da variável é 256, pelo que não se pode calcular
fact(260) sem alterar o valor da variável.
•
Existem várias outras funções recursivas em que pode existir mais do que um
elemento base ou em que o conjunto recursivo é mais difícil de definir. Em qualquer
caso é essencial definir a condição de terminação.
•
Para exemplificar estas funções, estudamos de seguida
– a determinação dos números de Fibonacci e
– o cálculo do maior divisor comum entre dois números.
23 Março 2007
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
6
Função Fibonacci (Recursiva)
•
Fibonacci (matemático da Renascença italiana) estabeleceu uma série curiosa de
números para modelar o número de casais de coelhos em sucessivas gerações. Em
cada geração, o número pode ser obtido através dos das 2 gerações anteriores
através de
fib(n) = fib(n-1) + fib(n-2)
•
Assumindo que nas primeiras duas gerações só existe um casal de coelhos, os
sucessivos números de Fibonacci são
1,1,2,3,5,8,13,21,34,55,89, ...
•
Estes números ocorrem em vários processos biológicos (e não só), por exemplo, no
número de pétalas de algumas flores.
•
A sua determinação recursiva impõe o cálculo directo do valor para 2 elementos de
base (a 1ª e a 2ª geração).
23 Março 2007
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
7
Função Fibonacci (Recursiva)
•
Em Octave, a obtenção dos números de Fibonacci pode ser feita muito facilmente
através da função recursiva abaixo (em Octave)
function f = fib(n);
if n == 1
% 1º elemento base
f = 1;
elseif n == 2
% 2º elemento base
f = 1;
else
% definição recursiva
f = fib(n-1) + fib(n-2);
endif;
endfunction;
•
Como é fácil de constatar, se o número n inicial for maior ou igual a 1, a recursão
termina. No entanto, se se chamar fib(0) a computação não termina (em Octave
termina quando o número de chamadas recursivas exceder o valor da variável
max_recursion_depth)!
23 Março 2007
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
8
Máximo Divisor Comum (Função Recursiva)
•
Como se sabe, o máximo divisor comum (mdc) entre dois números m e n é também
um divisor da sua diferença, m-n. Por exemplo, o mdc de 60 e 36 é 12, que divide 24
= 60-36.
•
Por outro lado, o mdc dos dois números m e n é ainda o mdc do menor número (n)
com a diferença (m-n). Se houvesse um divisor comum maior, ele seria igualmente
divisor de n, contrariamente à hipótese.
•
Assim, pode determinar-se o mdc de dois números através da determinação do mdc
de números cada vez menores. A computação termina quando os números forem
iguais, caso em que o mdc é esse número.
•
Por exemplo:
60 - 36 = 24 ;
36 – 24 = 12;
24 – 12 = 12;
12 = 12 !
23 Março 2007
% 12 é o mdc de 60 e 36
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
9
Máximo Divisor Comum (Função Recursiva)
•
Em Octave, pode determinar-se o maior divisor comum de dois números com a
função seguinte
function d = mdc(m,n);
if m == n
d = m;
elseif m > n
d = mdc(m-n,n);
else
d = mdc(n-m,m);
endif;
endfunction;
•
De notar que antes da chamada recursiva deve ser verificado qual o maior dos
argumentos de entrada (para não se chamar a função com argumentos negativos!)
23 Março 2007
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
10
Recursão e Iteração
•
Uma função definida recursivamente pode ser igualmente definida de uma forma
iterativa (através de ciclos). Em geral, a definição recursiva é mais “declarativa” na
medida em que explicita o que se pretende obter e não a forma como se obtém (ou
seja, um determinado programa que é usado).
•
Por outro lado, uma definição iterativa, embora não permita uma compreensão tão
imediata, é geralmente mais eficiente, já que as instruções de programação de baixo
nível para a iteração são mais eficientes que as de chamadas de funções.
function f = fact_ite(n);
f = 1;
for i = n:-1:1
f = f * i;
endif;
endfunction;
•
function f = fact_rec(n);
if n == 1
f = 1
else f = n * fact_rec(n-1);
endif;
endfunction;
No entanto, estas diferenças são geralmente pouco importantes, excepto em casos
de recursão múltipla, em que a ineficiência pode ser “catastrófica”.
23 Março 2007
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
11
Recursão e Iteração
•
Esta é a situação da função de Fibonacci, em que o seu valor depende de 2
chamadas recursivas. Como as chamadas são independentes, a mesma função
acaba por ser recalculada várias (mu...uitas !) vezes.
•
Na realidade, o número de funções chamadas é o próprio número de fibonacci (7/1,
6/1, 5/2, 4/3, 3/5, 2/8) que aumenta exponencialmente com o valor de n.
7
5
6
5
4
3
2
1
23 Março 2007
3
3
2
4
4
2
1
2
3
2
1
2
3
2
2
1
1
function f = fib(n);
if n <= 2 f = 1
else f = fib(n-1)+fib(n-2);
endif;
endfunction;
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
12
Recursão e Iteração
•
Para se ter uma ideia do aumento, podemos notar que apesar de inicialmente
pequenos
n
fib(n)
1
1
2
1
3
2
4
3
5
5
6
8
7
13
8
21
9
34
10
55
11
89
os números tornam-se rapidamente “grandes” !!!
n
fib(n)
26
121 393
27
196 418
28
317 811
29
514 229
30
832 040
31
1 346 269
32
2 178 309
ou mesmo “enormes” !!!
n
fib(n)
46
1 836 311 903
47
2 971 215 073
48
4 807 526 976
49
7 778 742 049
50
12 586 269 025
tornando proibitiva a sua computação recursiva (normal).
23 Março 2007
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
13
Memorização
•
Por vezes é possível aliar a declaratividade da versão recursiva, com a eficiência da
versão iterativa, através da memorização dos valores já computados. Por exemplo
se se pretenderem os primeiros 100 números de fibonacci, pode criar-se um vector,
fib_vec, com os valores já determinados.
– Se fib_vec(n) ainda não contiver o valor de fib(n), então determina-se fib(n) e
regista-se esse valor em fib_vec(n).
– Caso contrário, retorna-se simplesmente o valor de fib_vec(n).
•
Para que este esquema seja posível, é necessário que a tabela fib_m seja visível por
todas as instâncias da função fib(n). Para evitar passá-la como parâmetro deve
declarar-se como uma variável global.
•
Em Octave, para que uma variável seja global, ela deve ser declarada no programa
principal com a declaração global. No caso actual, se se pretende um vector linha
com 100 elementos inicializados a zero, devemos declarar a variável global
global fib_vec = zeros(1,100)
23 Março 2007
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
14
Memorização
•
Uma vez declarada uma variável global, ela só pode ser eliminada através da
declaração clear. Se pretendermos um vector com 200 elementos deveremos fazer
clear fib_vec
global fib_vec = zeros(1,200)
•
Para que na função a variável, fib_vec considerada seja a variável global e não uma
variável local, a variável deve ser identificada novamente como global.
function f = fib_mem(n); % versão recursiva com memória
global fib_vec;
if fib_vec(n) == 0
% se o valor ainda não foi calculado
if n <= 2
% determina esse valor ...
fib_vec(n) = 1;
else
fib_vec(n) = fib_mem(n-1)+fib_mem(n-2);
endif
endif;
f = fib_vec(n); % e atribui o valor memorizado à função
endfunction;
23 Março 2007
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
15
Aleatoriedade
•
Em muitas aplicações informáticas, nomeadamente em simulações que utilizam
processos aleatórios ou estocásticos, muito utilizadas em engenharia.
•
Um processo aleatório é aquele cujo resultado não é conhecido com rigor, mas que
obedece a uma distribuição de probabilidades.
•
Por exemplo, no lançamento de uma moeda ao ar, não se conhece o resultado a
priori, mas, se a moeda não estiver viviada, assume-se que cerca de 50% das vezes
sai cara, enquanto que nas outras cerca de 50% de vezes sai coroa. Já o número de
vezes que no lançamento de um dado sai um “2” é de 1/6 (ou 16.66%).
•
Tais processos podem ser simulados com recurso a números (pseudo-) aleatórios,
conhecidos como processos ou simulações de Monte Carlo.
•
Estes números são obtido por um gerador de números aleatórios, que no caso do
Octave é invocado pela função pre-definida rand(), ou simplesmente rand.
•
Esta função retorna um número aleatório entre no intervalo [0, 1[ de cada vez que é
invocada.
23 Março 2007
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
16
Exemplos: Moeda ao ar e Lançamento de um Dado
•
Por exemplo o processo de n lançamentos de uma moeda ao ar, em que 1 significa
caras e 2 significa coroas, pode ser simulado pela função
function L = moeda(n);
for i = 1:n
if rand > 0.5 L(i) = 1
else
L(i) = 2
endif
end for
endfunction
•
Já o lançamento de uma dados pode ser simulado pela função
function L = dado(n);
for i = 1:n
r = rand;
if
r < 1/6
elseif r < 2/6
...
elseif r < 5/6
else
endif
end for
endfunction
23 Março 2007
L(i) = 1;
L(i) = 2;
L(i) = 5
L(i) = 6
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
17
Exemplos: Moeda ao ar e Lançamento de um Dado
•
Na realidade, para grandes números a frequência aproxima-se da probabilidade, isto
é, se lançarmos 10 vezes uma moeda ao ar, o número de caras deve ser próximo de
5, pois a probabilidade de sair caras é ½ e ½ *10 = 5.
•
Em geral a frequência de ocorrrência de um valor aleatório aproxima-se da sua
probabilidade para grandes valores de n. Mais formalmente, denotando por
– p(X=a) ou simplesmente pa, a probabilidade de um evento X tomar o valor A;
– n o número de eventos e
– ea o valor esperado do número de ocorrências de X=a
– fa o número efectivo de ocorrências de X=a
temos
ea = n*pa ; e
fa ≈ ea,
devendo o erro relativo (n) = ( fa – ea)/ n diminuir com o aumento do número de
eventos.
23 Março 2007
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
18
Passeio Aleatório
Exemplo: Uma pessoa pretende percorrer um passeio entre as duas vias de uma estrada,
em que começando no centro do passeio, pode guinar até k vezes para a direita ou a
esquerda antes de sair do passeio e ser atropelada. Estando “bêbada”, em cada passo
que dá tem uma probabilidade de 50% de guinar para a direita .e outra igual de guinar
para a esquerda. Sabendo-se que deverá dar n passos, qual a probabilidade de chegar
ao fim da estrada sem sair do passeio?
•
Para resolver este problema, basta utilizar a função passeio, que para um número total
de percursos de n passos num passeio que admite k desvios, conta o número na de
“atropelamentos”.
function p = passeio(n,k,total);
na = 0;
for i = 1:total
na = na + atropelado(n,k);
endfor
p = na/total
endfunction
•
Naturalmente a função passeio utiliza uma função atropelado que deve retornar 1 se
houver atropelamento e 0 no caso contrário.
23 Março 2007
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
19
Passeio Aleatório
•
Para a função atropelado, vamos considerar uma variável desvio, que começa em 0 e
vai acumulando os desvios para a direita e para a esquerda.
•
Se conseguir chegar ao fim do ciclo for sem atingir um desvio, em módulo, maior que
k, a função retorna 0.
•
De notar que logo que o desvio seja maior que k, a função pode retornar
imediatamente o valor 1, saindo do ciclo for com a instrução de excepção return.
function p = atropelado(n,k);
p = 0; desvio = 0;
for i = 1:n
if rand > 0.5 d = 1; else d = -1; endif;
desvio = desvio + d;
if abs(desvio) > k
p = 1;
return;
endif
endfor
endfunction
23 Março 2007
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
20
Área de uma Curva
• Os numeros aleatórios também podem ser utilizados na determinação aproximada de
áreas. O raciocínio é o seguinte:
1. Contornemos a área a determinar A, por uma área conhecida, B
2. Consideremos um conjunto aleatório de pontos na área conhecida, e contabilizar
a percentagem p de pontos que “cai” dentro da área a determinar.
3. A área A pode ser aproximada por A ≈ pB .
• Exemplo:
f ( x)  1  x 2
1
B
1. Calculemos a área do ¼ de circulo de raio 1 ao lado.
2. A área B é naturalmente de 1
A
3. A área do ¼ de circulo deve ser próxima de /4
1
• Falta determinar a forma de gerar pontos aleatórios no quadrado, o que se pode fazer
facilmente gerando x e y aleatórios no intervalo [0,1[ e verificando se ficam abaixo da
função y = sqrt(1-x2)
23 Março 2007
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
21
Área de uma Curva
• Este algoritmo está implementado na função pi_prob abaixo indicada.
– O ciclo for gera n pontos <x,y>,
– Destes n pontos , c estão abaixo da curva do ¼ círculo.
– A área do ¼ de círculo é a fracção c/n da área do quadrado (1*1)
– O valor de pi é 4 vezes a área
function p = pi_prob();
c = 0;
for i = 1:n;
x = rand(); y = rand();
if y < sqrt(1-x^2)
c = c+1;
endif
endfor
area = (1*1)* c/n;
p = 4*area;
endfunction
23 Março 2007
f ( x)  1  x 2
1
B
A
Recursividade Funções Recursivas. Aleatoriedade e Processos de
Monte Carlo
1
22