Linguagem de
programação I A
Carlos Oberdan Rolim
Ciência da Computação
Sistemas de Informação
Recursão
Recursão
Recursão é o ato de uma função chamar ela mesma. Uma
função que chama a ela mesma é chamada função
recursiva.
O exemplo padrão de função recursiva é uma função que
calcula o fatorial de um número. O fatorial de um número é
igual ao produto dos números inteiros de 1 até o número.
fatorial de 3 = 3 * 2 * 1
Se você observar com cuidado verá que:
fatorial de 3 = 3 * fatorial de 2
fatorial de 2 = 2 * fatorial de 1
fatorial de 1 = 1 * fatorial de 0
Ou seja
fatorial de um número = número * (fatorial de número - 1)
Fatorial recursivo
Definição não recursiva (tradicional):
N! = 1, para N = 0.
N! = 1 x 2 x 3 x .... x N, para N>0
Definição recursiva:
N! = 1, para N = 0;
N! = N x (N - 1)!, para N > 0.
Decomposição do Fatorial(3)
Fatorial(3) = 3 * Fatorial(2)
Fatorial(2) = 2 * Fatorial(1)
Fatorial(3) = 3 * 2 = 6
Fatorial(2) = 2 * 1 = 2
Fatorial(1) = 1*Fatorial(0)
Fatorial(1) = 1*1 = 1
Fatorial(0)=1
Características dos programas recursivos
a) Chama a si mesmo para resolver parte do
problema;
chamada recursiva
b) Existe pelo menos um caso base que é
resolvido sem chamar a si mesmo.
Condição de parada
Projeto para implementar funções recursivas
Toda função recursiva possui dois elementos:
•
Resolver parte do problema (caso base) ou
•
Reduzir o tamanho do problema (caso geral).
No caso do nosso exemplo, Fatorial(0) é o
caso base
Recursão
/* Exemplo de função recursiva */
#include <stdio.h>
int fatorial(int nr) {
if(nr == 1) return(1);
return (nr * fatorial(nr-1) );
}
int main() {
int a;
printf("\nEntre com um valor inteiro :");
scanf("%d",&a);
printf("O fatorial de %d é %d\n\n",a, fatorial(a));
return(0);
}
Segmentos de memória
Stack (pilha): local onde as variáveis
locais as funções são armazenadas
Armazena os dados de chamadas de
funções
Heap
p = (int *) malloc...
Objetos
Dados são “empilhados” no topo da pilha
Usa FIFO (First In First Out)
Heap: local para os dados alocados
dinamicamente, variáveis globais,
constantes e definidas como “static”
Stack
int main()
Int y;
Valores são armazenados de forma
“desordenada”
Tempo de execução
Segmento de código: local onde os
dados de código compilados residem
Codigo
Chamada de método
Quando um método é chamado:
é necessários inicializar os parâmetros formais com os valores
passados como argumento;
sistema precisa saber onde reiniciar a execução do programa;
Informações de cada método (variáveis e endereço de retorno)
deve ser guardada até o método acabar a sua execução.
Mas como o programa diferencia a variável n da primeira
chamada da variável n da segunda chamada do método
fatorialr?
int fatorial(int nr) {
if(nr == 1)
return(1);
return (nr * fatorial(nr-1) );
}
Registro de ativação
Registro de ativação:
área de memória que guarda o estado de uma função, ou
seja:
variáveis locais
valores dos parâmetros;
endereço de retorno (instrução após a chamada do método corrente);
valor de retorno.
Registro de ativação são criados na pilha em tempo de
execução;
Existe um registro de ativação (um nó na pilha) para cada
método;
Quando um método é chamado é criado um registro de
ativação para este e este é empilhado na pilha;
Quando o método finaliza sua execução o registro de ativação
desse método é desalocado.
Registro de ativação
Registro de
ativação de
f3()
Registro de
ativação de
f2()
Registro de
ativação de
f1()
Registro de
ativação do
método
main()
Parâmetros e
variáveis locais
Endereço de retorno
Valor de retorno
Parâmetros e
variáveis locais
Endereço de retorno
Valor de retorno
Parâmetros e
variáveis locais
Endereço de retorno
Valor de retorno
topo
void f3() {
int x = 3;
}
void f2() {
int x = 2;
f1();
}
void f1() {
int x = 1;
f2();
}
int main() {
f1();
}
n=1
Registro de
ativação de
fat(1)
1
Registro de
ativação de
fat(4)
=24
3*fat(2) =6
4*fat(3)
topo
PC=6
2*fat(1)
2
n=3
Registro de
ativação de
fat(3)
fat (4)  main
PC=6
n=2
Registro de
ativação de
fat(2)
fatorial de 4
topo
topo 3 int fatorial(int n) {
PC=6
6
n=4
PC = 11
24
resultado =24
…
topo
=2
1
4
5
if(n == 1)
return(1);
6
return (n * fatorial(n-1) );
7
8
}
9 int main(){
10
int resultado
11
resultado = fatorial(4);
12
printf(”%d”, resultado);
13 }
Registro de ativação
A cada término de FATORIAL, o controle retorna para a
expressão onde foi feita a chamada na execução
anterior, e o último conjunto de variáveis que foi alocado
é liberado nesse momento. Esse mecanismo utiliza uma
pilha.
A cada nova chamada do método FATORIAL, um novo
conjunto de variáveis (n, FATORIAL) é alocado.
Vantagens e Desvantagens
Vantagens da recursão
Redução do tamanho do código fonte
Maior clareza do algoritmo para problemas de definição
naturalmente recursiva
Desvantagens da recursão
Baixo desempenho na execução devido ao tempo para
gerenciamento das chamadas
Dificuldade de depuração dos subprogramas recursivos,
principalmente se a recursão for muito profunda
Evitando recursão
A recursão sempre deve ser evitada basicamente por
dois fatores.
Primeiro que uma função recursiva é difícil de compreender.
Segundo que as funções recursivas são mais lentas que suas
correspondentes não recursivas.
Normalmente uma função recursiva também pode ser
escrita com laços de repetição tipo for ou while de modo
a remover a recursão.