Recursividade e Iteração
Factorial, Fibonacci e Maior Divisor Comum
DI/FCT/UNL
1º Semestre 2004/2005
1
Programas e Funções
• Como visto em exemplos anteriores, um programa pode ser
considerado como o encadeamento de diversas funções, isto
é, no corpo de uma função são chamadas outras funções.
• Um programa pode pois ser estruturado de forma a ser
composto por várias funções, tal como é feio na
“matemática”. Por exemplo,
tg(x) = sin(x) / cos(x).
• Em algumas linguagens de programação, nomeadamente
naquelas em que as funções só podem retornar um valor, 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.
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.
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
4
Função Factorial
• A função factorial pode ser definida (em pseudo-código) como
função fact(n)
se n = 0 então
% elemento base
fact  1
senão
% definição recursiva
fact  n * fact(n-1)
fimse;
fimfunção;
• Em Octave, a definição é semelhante
function f = fact(n);
if n == 0
f = 1
else
f = n * fact(n-1)
endif;
endfunction;
% elemento base
% definição recursiva
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.
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).
7
Função Fibonacci (Recursiva)
• Em Octave, a definição do números de Fibonacci pode ser feita
muito facilmente como
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)!
8
Função Máximo Divisor Comum (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 !
9
Função Máximo Divisor Comum (Recursiva)
• Em Octave, pode determinar-se o maior divisor comum de dois
números com a função seguinte
function d =
if m == n
d = m;
else
if m-n
d =
else
d =
endif;
endif;
endfunction;
mdc(m,n);
>= n
mdc(m-n,n);
mdc(n,m-n);
• De notar que na chamada, o 1º argumento (m) é sempre maior
ou igual que o 2º (n), de forma a garantir que m-n seja positivo!
10
Recursão e Iteração
• Em geral, uma função ou procedimento definidos
recursivamente podem ser também definidos 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.
• 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”.
11
Recursão e Iteração
function f = fib(n); % versão recursiva
if n <= 2
f = 1;
else
f = fib(n-1) + fib(n-2);
endif;
endfunction;
function f = fib(n) % versão iterativa
if n <= 2
f = 1;
else
f1 = 1; f2 = 1;
for i = 3:n
f = f1+f2;
f1 = f2;
f2 = f;
endfor;
endif;
endfunction;
12
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 (muitas !) vezes.
7
5
6
5
4
3
2
1
3
3
2
4
4
2
1
2
3
2
1
2
3
2
2
1
1
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.
13
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 “enormes”
n
fib(n)
n
fib(n)
26
27
28
29
30
31
32
121 393 196 418 317 811 514 229 832 040 1 346 269 2 178 309
45
46
47
48
49
50
1 134 903 170 1 836 311 903 2 971 215 073 4 807 526 976 7 778 742 049 12 586 269 025
tornando proibitiva a sua computação recursiva (normal).
14
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 uma tabela, fib_m, com os valores já
computados.
– Se fib_m(n) ainda não contiver o valor de fib(n), então
determina-se fib(n) e escreve-se em fib_m(n).
– Caso contrário, apenas se retorna o valor de fib_m(n).
• Para que este esquema seja posível, é conveniente 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.
15
Variáveis Globais em Octave
• 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_m = zeros(1,100)
• 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_m
global fib_m = zeros(1,200)
• Para que na função a variável, fib_m considerada seja a
variável global e não uma variável local, a variável deve ser
identificada novamente como global.
16
Memorização
function f = fib(n);
% versão recursiva com memória
global fib_m;
if fib_m(n) > 0
f = fib_m(n);
else
if n <= 2
f = 1;
else
fib_m(n) = fib_mem(n-1)+fib_mem(n-2);
f = fib_m(n);
endif;
endif;
endfunction;
17