Recursividade
Inhaúma Neves Ferraz
Departamento de Ciência da Computação
Universidade Federal Fluminense
[email protected]
Objetos e Procedimentos
Recursivos
Um objeto é dito recursivo se consiste
parcialmente em si mesmo ou é definido em
termos de si mesmo.
Procedimentos recursivos podem ser
processadas por procedimentos não
recursivos simulando a recursão.
2
Eventos que ocorrem no uso de
Procedimentos
Na chamada do procedimento
 Passagem dos argumentos
 Alocação e inicialização das variáveis locais
 Transferência do controle para a função (endereço de
retorno)
No retorno do procedimento
 Recuperação do endereço de retorno
 Liberação da área de dados
 Desvio para o endereço de retorno
3
Chamadas de procedimentos
(não recursivos)
4
Implementação de procedimentos
recursivos
Procedimentos recursivos só podem ser
implementados em alto nível de abstração.
As máquinas não executam procedimentos
recursivos.
Cabe ao “software” simular procedimentos
recursivos.
5
Simulação de Procedimentos
Recursivos
A simulação de recursão utilizará uma pilha
com os seguintes atributos gravados:




Parâmetros
Variáveis
Valor da função (se for o caso)
Endereço de retorno
6
Chamadas recursivas de funções
7
Exemplo de Procedimentos
Recursivos
Cálculo do fatorial de um inteiro
Série de Fibbonacci
Torres de Hanói
8
Cálculo do fatorial de um inteiro
public class Factorial {
public static void main(String[] args){
int input = Integer.parseInt(args[0]);
double result = factorial(input);
System.out.println(result);
}
public static double factorial(int x){
if (x<0) return 0.0;
else if (x==0) return 1.0;
else return x*factorial(x-1);
}
}
9
Série de Fibbonacci
public static int fib(int n)
{
int x,y;
if (n <= 1) return 1;
else {
x = fib(n-1);
y = fib(n-2);
return x + y;
}
}
10
Torres de Hanói
Denote os pinos por A, B, C
Seja n o número total de discos
Numere os discos de 1 (menor, no topo da
pilha) até n (maior, base da pilha)
Para mover n discos do pino A para o pino B:
Mova n-1 discos de A para C. Isto faz com que o
disco n fique isolado no pino A
2. Mova o disco n de A para B
3. Mova n-1 discos de C para B de maneira que eles
fiquem em cima do disco n
1.
11
Exemplo
Algoritmo do Fatorial
fact(n) = n * fact(n - 1)
se n=o
então
fact(0) = 1
senão
x = n-1
y = fact(x)
fact(n) = n * y
fim do se
13
Exemplo de uso de pilha
x = n-1
y = fact(x)
fact(n) = n * y
14
Simulação de Recursão
Programa simulador de recursão (1)
Para criar um programa que simule a
recursão deve-se partir do programa
recursivo e executar 3 alterações:
 Alteração inicial
 Substituição de cada chamada recursiva por um
conjunto de instruções
 Substituição de cada retorno da função por um
conjunto de instruções
16
Programa simulador de recursão (2)
O programa assim obtido será uma
simulação não recursiva do programa
recursivo.
Em geral o programa assim obtido não é
um programa bem estruturado e que,
freqüentemente, pode ser aperfeiçoado por
refinamentos subseqüentes.
17
Alteração inicial
Declarar uma pilha e inicializá-la como
vazia
2. Associar um rótulo ao primeiro comando
executável
3. Atribuir aos dados correntes os valores
adequados
1.
18
Chamadas recursivas
4.
5.
6.
7.
8.
9.
Criar o i-ésimo rótulo Li (ou label_i)
Quando os argumentos da chamada do procedimentos
forem expressões calcular o valor das expressões e
atribuir estes valores aos parâmetros formais
Empilhar os parâmetros, as variáveis locais e o endereço
de retorno i
Atualizar os valores dos parâmetros para o
prosseguimento do programa
Executar um desvio incondicional para o rótulo do início
do procedimento
Associar o rótulo criado no item (ou regra) 4 ao comando
subseqüente ao desvio incondicional
19
Substituição do return
10. Retornar se a pilha estiver vazia
11. Desempilhar os parâmetros, variáveis locais e
endereço de retorno
12. Se o procedimento for uma função avaliar as
expressões que se seguem ao return e empilhar o
resultado
13. Executar um desvio condicional para o rótulo
especificado no endereço de retorno corrente
20
Modelos de geração de
programas não recursivos
simulando programas
recursivos
Modelo de alteração inicial
Modelo de chamada recursiva
Modelo de retorno de chamada recursiva
21
Alteração Inicial
/* Passo 1: Pilha vazia
*/
s.top = MENOS_UM;
/* inicialização de área vazia
*/
currarea.x = 0;
/* por exemplo */
currarea.y = ‘’;
/* por exemplo */
currarea.retaddr = 0;
/* empilhar a área vazia
*/
push(&s,&currarea);
/* Passo 3: Atribuir aos parametros e endereço
de retorno os valores adequados */
currarea.param = n; /* por exemplo */
currarea.retaddr = 1; /* 1 para retornar a main.
2 para recursão */
start : /* Passo 2: associar rótulo inicial ao
primeiro comando executável */
22
Chamada Recursiva
/* simulação de chamada recursiva */
/* Passo 6: empilhamento
*/
push(&s,&currarea);
/* Passo 7: atualização dos valores dos
parâmetros
*/
currarea.x = ...;
/* por exemplo */
.
.
currarea.retaddr = i;
/* Passo 8: desvio incondicional para o rótulo
inicial
*/
goto start;
label_i : /* Passos 4 e 9: rótulo associado ao
comando subseqüente ao desvio
*/
23
Retorno de função
/* simulação de return */
/* Passo 11: desempilhar
*/
i = currarea.retaddr;
pop(&s,&currarea);
/* Passo 13: desvio condicional para o endereço
de retorno
*/
switch (i) {
case 1 : goto label1; /* tantos casos
quantos forem as chamadas recursivas + 1 */
.
.
case m : goto label2;
} /* end switch */
} /* end if (currarea.param == 0)
*/
24
Exemplos
Serão apresentados dois problemas
clássicos de recursão :
cálculo do fatorial de um inteiro
 problema conhecido como Torres de Hanói

25
Torres de Hanói
26
Passagem de 4 discos do pino A para o pino C
27
28
Chamadas de funções (não recursivas)
29
Chamadas recursivas de funções
30
Fatorial recursivo
long int fact(int n)
{
int x;
long int y;
if (n < 0) {
printf("parâmetro negativo: %d\n",n);
exit(1);
} /* end if */
if (n == 0)
return (1);
x = n-1;
y = fact(x);
return(n*y);
}
/* end fact
*/
31
Simulação da recursão (1)
long int simfact1(int n)
{
// Simulação de fatorial
struct dataarea currarea;
short int i;
long int result;
s.top = MENOS_UM;
/* inicialização de área vazia
*/
currarea.param
= 0;
currarea.x
= 0;
currarea.y
= 0;
currarea.retaddr = 0;
/* empilhar a área vazia
*/
if (push(&s,&currarea) == MENOS_DOIS) {
printf("Estouro de pilha\n");
exit(1);
}
/* end if
*/
/* Atribuir ao parametro e endereço de retorno os valores adequados */
currarea.param
= n;
currarea.retaddr = 1; /* 1 para retornar a main. 2 para recursão */
32
Simulação da recursão (2)
start : /*inicio da rotina de simulação de fatorial
if (currarea.param == 0) { /* fact(0) */
/* simulação de return */
result = 1;
/* fact(0) == 1; */
i = currarea.retaddr;
if (pop(&s,&currarea) == MENOS_UM) {
printf("Pilha vazia\n");
}
/* end if */
switch (i) {
case 1 : goto label1;
case 2 : goto label2;
} /* end switch */
} /* end if (currarea.param == 0)
*/
/* currarea.param != 0
*/
currarea.x = currarea.param - 1;
/* simulação de chamada recursiva */
if (push(&s,&currarea) == MENOS_DOIS) {
printf("Estouro de pilha\n");
exit(1);
}
/* end if
*/
currarea.param = currarea.x;
currarea.retaddr = 2;
goto start; /* chamada recursiva */
*/
33
Simulação da recursão (3)
label2 : /* ponto de retorno da chamada recursiva */
/* atribui-se o valor retornado a cuurarea.y */
currarea.y = result;
/* simulação de return(n*y)
*/
result = currarea.param * currarea.y;
i = currarea.retaddr;
/* voltar ao ambiente original */
if (pop(&s,&currarea) == MENOS_UM) {
printf("Pilha vazia\n");
}
/* end if */
switch (i) {
case 1 : goto label1;
case 2 : goto label2;
} /* end switch */
label1 : /* ponto de retorno ao programa principal
*/
return (result);
} /* end simfact1 */
34
O programa simulador obtido
O programa simulador obtido ( fat_nr01)
não tem uma boa estrutura.
Ele pode, e deve, ser aperfeiçoado por
refinamentos subseqüentes.
Inicialmente será criado o programa
fat_nr02.
35
Passagem de fat_nr01 para fat_nr02
O fatorial corrente y e o valor corrente x podem
ser globais não necessitando ser empilhados.
Como só há um endereço de retorno de chamada
recursiva, só há um endereço de retorno, pois o
retorno ao programa chamador é testado pela
condição de pilha vazia. Portanto não é preciso
empilhar endereços de retorno usando desvio
incondicional
36
Passagem de fat_nr02 para fat_nr03
switch(pop(&s,&currarea)){ aparece
duas vezes e agrupando estas ocorrências
pode-se simplificar o algoritmo
x e currparam nunca são usadas
simultaneamente e podem ser uma só
variável x
37
Passagem de fat_nr03 para fat_nr04
O laço criado pelo teste inicial e terminado
por goto start pode ser substituído por um
laço while
O laço iniciado por label2 e terminado por
switch(pop(... pode ser substituído por
outro laço while
38
Passagem de fat_nr04 para fat_nr05
O primeiro laço while empilha 1 a n, sendo 1
no topo
O segundo laço while multiplica o resultado
corrente pelo topo da pilha
Sabendo disso não é preciso nem empilhar
nada
39
Algoritmo recursivo das Torres de Hanói
void towers(int n, char from, char to, char aux)
{
/* Caso haja um só disco, mova-o e retorne
*/
if (n == 1) {
printf("Mover disco 1 do pino %c para o pino %c\n",
from, to);
return;
}
/* end if */
/* Mover os n-1 discos superiores de A para B usando C como
auxiliar */
towers(n-1,from,aux,to);
/* Mover o disco restante de A para C */
printf("Mover disco %d do pino %c para o pino %c\n",
n, from, to);
/* Mover os n-1 discos de B para C usando A como auxiliar */
towers(n-1,aux,to,from);
return;
}
/* end towers
*/
40