Funções, Execução Condicional,
Recursividade e Iteração
Pedro Barahona
DI/FCT/UNL
Introdução aos Computadores e à Programação
2º Semestre 2005/2006
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
1
Programas e Funções
• Como foi visto no exemplo anterior, 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 é feito na
“matemática”. Por exemplo,
tg(x) = sin(x) / cos(x).
• 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.
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteraçã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.
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
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
n
se n  0
de base e a cláusula recursiva:

fact ( n )  
n * fact ( n  1 )

30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
se
n0
4
Execução Condicional
• Quando queremos, como no caso do factorial, que um
programa execute uma de duas alternativas, dependendo do
valor de uma condição, deve ser usada a instrução “se”:
se Condição então
% alternativa a executar quando a condição for verdadeira
senão
% alternativa a executar quando a condição for falsa
fim se;
• Em Condição deve estar uma expressão cujo resultado ou é
verdadeiro ou é falso (para que, em tempo de execução, se
possa decidir qual a alternativa a executar)
• As expressões cujo resultado pode ser verdadeiro ou falso
chamam-se Expressões Booleanas.
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
5
Expressões Booleanas
• Expressões booleanas podem ser construidas recursivamente a
partir de outras mais simples com os operadores booleanos de
– Conjunção, “e” ou “and”, expressa como & em OCTAVE
– Disjunção, “ou” ou “or”, expressa como | em OCTAVE
– Negação, “não” ou “not”, expressa como ! em OCTAVE
• As variáveis booleanas podem tomar os valores verdade ou falso.
Em OCTAVE, que só considera variáveis “numéricas”, 0
corresponde a falso e qualquer outro valor a verdade!
• De notar que uma variável booleana pode ser atribuído o valor
booleano de uma comparação numérica. Por exemplo:
encontrada = (x > xmin & y > ymax)
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
6
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;
30 Março 2006
% elemento base
% definição recursiva
Funções, Execução Condicional, Recursividade e Iteração
7
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.
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
8
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).
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
9
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)!
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
10
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 !
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
11
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!
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
12
Recursividade para Resolução de Problemas
• A recursividade pode ser usada na resolução de problemas,
difíceis de resolver por outras técnicas de programação.
• Tal é o caso das “Torres de Hanoi”: dadas três torres (estacas)
pretende-se passar uma “pirâmide” de peças ordenadas de
uma torre para outra, movendo-se uma peça de cada vez, para
o topo de uma torre encimada por uma peça menor.
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
13
Torres de Hanoi - Recursividade
•
•
Apesar de aparentemente complicado, este problema tem
uma solução recursiva simples.
Para passar n peças de uma torre (A) para outra (C)
1. Passar n-1 peças da torre inicial (A) para a torre livre (B)
2. Mover a última peça, para a torre final (C)
3. Passar as n-1 peças da torre B para a torre final (C).
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
14
Torres de Hanoi: Movimentos Necessários
• Baseados nesta resolução recursiva podemos
– Determinar o número de movimentos necessários
– Determinar os movimentos necessários
• O número de movimentos necessários é bastante simples de
determinar, na versão recursiva
hanoi_count(n) = hanoi_count(n-1)+1+ hanoi_count(n-1)
• Neste caso, pode-se evitar a dupla recursividade (ver adiante)
de uma forma muito simples
hanoi_count(n) = 2*hanoi_count(n-1) + 1
• Finalmente, há que especificar a condição de paragem (n=1)
hanoi_count(1) = 1
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
15
Torres de Hanoi: Movimentos Necessários
• Um programa Octave para resolver o programa é imediato
function c = hanoi_count(n)
if n == 1
c = 1;
else
c = 2*n_hanoi_count(n-1)+1;
end;
endfunction;
• De notar o aumento exponencial do número de movimentos
necessários
n
1 2 3 4 5 6 7 8 9 10 11 12 13
14
15
count 1 3 7 15 31 63 127 255 511 1 023 2 047 4 095 8 191 16 383 32 767
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
16
Torres de Hanoi
• O problema propriamente dito pode ser resolvido com base
num vector T, com 3 números, correspondentes ao número de
peças em cada uma das torres.
T = [3,1,1]
• Notar que não é necessário indicar o tamanho de cada peça,
porque o algoritmo nunca coloca uma peça sobre uma menor!
• O movimento de uma só peça da torre A para a torre B, usado
no corpo da recursão e na sua terminação, pode ser feito com
uma função auxiliar, move_hanoi(T,A,B), especificada da
forma óbvia (tira uma peça de A e aumenta em B).
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
17
Torres de Hanoi
function T = hanoi(T,N,A,B) % move N peças de A para B
if N == 1
T = hanoi_move(T,A,B); % move a peça de A para B
else
C = 6-A-B;
% C é a outra torre!
T = hanoi(T,N-1,A,C); % move N-1 peças de A para C
T = hanoi_move(T,A,B); % move 1 peça de A para B
T = hanoi(T,N-1,C,B); % move N-1 peças de C para B
endif;
endfunction;
function T = hanoi_move(T,A,B)
T(A) = T(A) - 1;
T(B) = T(B) + 1;
disp(T);
endfunction;
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
18
Torres de Hanoi
• O funcionamento do programa pode ser visto com a
chamada
>> hanoi([4,0,0],4,1,3);
4
0
0
3
1
0
2
1
1
hanoi(_,2,1,3)
2
0
2
1
1
2
move(_,1,2)
2
1
1
hanoi(_,2,3,2)
2
2
0
1
3
0
0
3
1
0
2
2
1
1
2
hanoi(_,2,2,1)
2
1
1
move(_,2,3)
2
0
2
1
1
2
hanoi(_,2,1,3)
0
1
3
0
0
4
30 Março 2006
hanoi(_,3,1,2)
move(_,1,3)
hanoi(_,3,2,3)
Funções, Execução Condicional, Recursividade e Iteração
19
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”.
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
20
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;
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
21
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
30 Março 2006
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.
Funções, Execução Condicional, Recursividade e Iteração
22
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).
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
23
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.
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
24
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.
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
25
Memorização
function f = fib_mem(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;
30 Março 2006
Funções, Execução Condicional, Recursividade e Iteração
26