Aula 6 – Sumário
 Revisão
da aula anterior
 Endereçamento
indirecto
 Recursividade
 Conceito
 Exemplos
1
Processador MAC-1
Revisão – endereçamento indirecto
2
Revisão – endereçamento indirecto
Exemplo: copiar vector
Implementar um procedimento que copie n elementos de
um vector A para um vector B
O procedimento deverá receber como argumentos:



O número de elementos a copiar (n)
O endereço do primeiro elemento do vector A (referência)
O endereço do primeiro elemento do vector B (referência)
3
Revisão – endereçamento indirecto
jump main
A:
B:
n:
6 4 3 5 7
0 0 0 0 0
5
main:
lodd
push
loco
push
loco
push
call
insp
halt
n
copia: loco 0
push
# int i=0
ciclo: lodl 0
subl 4
jzer fim
# i-n == 0?
lodl 3
addl 0
pshi
# A[i] no topo da pilha
lodl 3
addl 1
popi
# B[i] = A[i]
Organização da pilha em ‘copia’
loco 1
addl 0
stol 0
# i=i+1
SP
jump ciclo
A
B
copia
3
i
End. Ret.
B (ref.)
fim:
insp 1
retn
A (ref.)
n
4
Processador MAC-1
Recursividade
5
Recursividade

Existem situações em que uma rotina se invoca a si
própria

Diz-se que a rotina é recursiva ou recorrente

Soluções recursivas podem ser úteis, simplificando a
resolução de alguns problemas, …

… mas é preciso ter cuidado, pois uma solução recursiva
causa um maior crescimento da pilha

cada chamada à rotina faz com que sejam colocados dados na
pilha (argumentos, endereço de retorno, variáveis locais);

se a rotina se chamar demasiadas vezes a ela própria, a pilha
pode ficar sem espaço para crescer (“stack overflow”)
6
Programação MAC-1
Exemplo: uma sucessão
Implementar uma função que calcule o termo de ordem n da
seguinte sucessão, definida de forma recursiva:
, se n  1
1
U(n)  
2 Un  1  1 , se n  1
// Pseudo-código
int U(int n)
{
if (n==1)
return 1;
return 2*U(n-1) + 1;
}
7
Programação MAC-1
C1:
main:
jump main
# int U(int n)
1
U:
loco 4
push
call U
insp 1
halt
# U(4)
Organização da pilha em ‘U’
SP
End. Ret.
n
ret1:
lodl 1
subd C1
jzer ret1
# AC = n-1
# if n-1==0 return 1
push
call U
insp 1
#
# U(n-1)
#
push
addl 0
insp 1
addd C1
retn
#
#
#
#
loco 1
retn
# AC = 1
temp = U(n-1)
AC = 2*temp
descarta temp
AC = 2*U(n-1)+1
8
Programação MAC-1
Exemplo: números de Fibonacci
Fazer uma função que calcule o número de Fibonacci de ordem n.
Este é dado por:
, se n  0 ou n  1
1
Fibo(n)  
Fibon  1  Fibon  2 , se n  1
// Pseudo-código
int fibo(int n)
{
if (n==1 || n==0)
return 1;
return fibo(n-1) + fibo(n-2);
}
9
Programação MAC-1
fibo:
C1:
C2:
1
2
lodl
subd
jzer
lodl
jzer
main:
loco 4
push
call fibo
insp 1
halt
lodl
subd
push
call
insp
jump main
# fibo(4)
lodl
subd
push
call
insp
End. Ret.
n
SP
1
C2
fibo
1
push
Organização da pilha em ‘fibo’
SP
1
C1
ret1
1
ret1
tmp
End. Ret.
# AC = n-1
# if n-1==0 return 1
#
#
#
# fibo(n-2)
# tmp = fibo(n-2)
2
C1
fibo
1
#
#
#
# F(n-1)
addl 0
insp 1
retn
# AC=fibo(n-1)+tmp
# descarta tmp
loco 1
retn
# AC = 1
n
ret1:
10