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
Chamadas recursivas de funções
1
2
11
3
5
10
19
14
8
17
6
12
15
18
7
16
4
9
13
8
Exemplo de Procedimentos
Recursivos
Cálculo do fatorial de um inteiro
Série de Fibbonacci
Torres de Hanói
9
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);
}
}
10
Série de Fibonacci
public static int fib(int n)
{ // Série de Fibonacci de ordem 4
int x,y;
if (n <= 1) return 1;
else {
x = fib(n-1);
y = fib(n-2);
z = fib(n-3);
return x + y + z;
}
}
11
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.
12
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
14
Exemplo de uso de pilha
x = n-1
y = fact(x)
fact(n) = n * y
15
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
17
Programa simulador de recursão (2)
O programa assim obtido será uma
simulação não recursiva do programa
recursivo.
Os laços recursivos serão substituídos por
laços até obter uma pilha de recursão vazia
Dentro dos laços uma seleção múltipla
(switch..case) governa os retornos e desvios
do programa
18
Alteração inicial
1.
2.
3.
4.
Declarar uma pilha e inicializá-la como vazia
Atribuir aos dados correntes os valores
adequados
Criar uma repetição até obter pilha vazia
contendo uma seleção múltipla cujo parâmetro é
o endereço de retorno da recursão
O primeiro caso da seleção é a condição de
término da recursão
19
Chamadas recursivas
5.
6.
7.
Quando os argumentos da chamada do procedimento
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
20
Substituição do return
Desempilhar os parâmetros, variáveis
locais e endereço de retorno
9. Se o procedimento for uma função avaliar
as expressões que se seguem ao return e
empilhar o resultado
8.
21
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
22
Exemplo
Será apresentado um problema clássico de
recursão :

cálculo do fatorial de um inteiro
23
Fatorial recursivo
long int fact(int n)
{
Long 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
*/
24
Elemento da pilha de recursão
class CFactNode
{
private:
//atributos encapsulados
long int value;
long int x;
long int y;
short int retAddr;
25
Alterações iniciais
long int FactSwitch(long int n)
{
stack<CFactNode>
FactStack;
long int
Result;
short int
i;
short int
RetAddr;
CFactNode
currNode;
//Empilha termo vazio para desempilhamento no final do
processo
FactStack.push(CFactNode(0));
//Atribui aos parâmetros e endereço de retorno os valores
adequados
currNode.setValue(n);
currNode.setRetAddr(4);
currNode.setX(0);
currNode.setY(0);
i = 0;
26
Estrutura do programa
while (FactStack.size())
{
switch (i)
{
case 0: // início do procedimento recursivo
{
if(currNode.getValue()== 0) //caso básico, Saída da Recursão
{
}
else //entrada normal da recursão
{
}
break;
}
//end case 0
case 1:
// retorno da chamada recursiva
{
break;
}
//end case 1
default: // retorno final
{
return (Result);
break;
} //end default
} //end switch
27
} //end While
Case 0: início do procedimento
case 0: // início do procedimento recursivo
{
if(currNode.getValue()== 0) //caso básico, Saída da Recursão
{
Result = 1;
i = currNode.getRetAddr(); // para aonde vai
currNode = FactStack.top();
FactStack.pop(); //Desempilha
i = currNode.getRetAddr();
}
else //entrada normal da recursão
{
currNode.setX(currNode.getValue() - 1) ;
FactStack.push(currNode); //Empilha o currNode
//O novo currNode recebe o Valor n-1
currNode.setValue(currNode.getX());
currNode.setRetAddr(1);
//vai para case 1
i = 0;
// chamada recursiva
}
break;
}
//end case 0
28
Case 1: retorno da chamada recursiva
case 1:
// retorno da chamada recursiva
{
//Parâmetro x recebe o valor de Fact(n-1);
currNode.setY(Result);
Result = currNode.getValue() * currNode.getY();
i= currNode.getRetAddr();
currNode = FactStack.top();
FactStack.pop();
//chamada recursiva
break;
}
//end case 1
29
Case Default: retorno final
default:
{
// retorno final
return (Result);
break;
} //end default
} //end switch
} //end While
}
30