Recursividade

Prévia do material em texto

CONCEITO DE RECURSIVIDADE
•FUNDAMENTAL EM MATEMÁTICA E CIÊNCIA DA 
COMPUTAÇÃO
• UM PROGRAMA RECURSIVO É UM PROGRAMA QUE CHAMA 
A SI MESMO
• UMA FUNÇÃO RECURSIVA É DEFINIDA EM TERMOS DELA 
MESMA
• DEFINE CONJUNTOS INFINITOS COM COMANDOS FINITOS
•EXEMPLOS
• NÚMEROS NATURAIS, FUNÇÃO FATORIAL, ÁRVORE
RECURSIVIDADE
•A RECURSIVIDADE É UMA ESTRATÉGIA QUE PODE SER UTILIZADA 
SEMPRE QUE O CÁLCULO DE UMA FUNÇÃO PARA O VALOR N, PODE 
SER DESCRITA A PARTIR DO CÁLCULO DESTA MESMA FUNÇÃO 
PARA O TERMO ANTERIOR (N-1).
Exemplo – Função fatorial:
n! = n * (n-1) * (n-2) * (n-3) *....* 1
(n-1)! = (n-1) * (n-2) * (n-3) *....* 1
logo:
n! = n * (n-1)!
RECURSIVIDADE
•DEFINIÇÃO: DENTRO DO CORPO DE UMA FUNÇÃO, CHAMAR
NOVAMENTE A PRÓPRIA FUNÇÃO
• RECURSÃO DIRETA: A FUNÇÃO X CHAMA A PRÓPRIA FUNÇÃO X; 
• RECURSÃO INDIRETA: A FUNÇÃO X CHAMA UMA FUNÇÃO Y QUE, 
POR SUA VEZ, CHAMA X
CONDIÇÃO DE PARADA
• NENHUM PROGRAMA NEM FUNÇÃO PODE SER EXCLUSIVAMENTE 
DEFINIDO POR SI
• UM PROGRAMA SERIA UM LOOP INFINITO
• UMA FUNÇÃO TERIA DEFINIÇÃO CIRCULAR
• CONDIÇÃO DE PARADA
• PERMITE QUE O PROCEDIMENTO PARE DE SE EXECUTAR
• F(X) > 0, ONDE X É DECRESCENTE
RECURSIVIDADE
•PARA CADA CHAMADA DE UMA FUNÇÃO,
RECURSIVA OU NÃO, OS PARÂMETROS E AS
VARIÁVEIS LOCAIS SÃO EMPILHADOS NA PILHA
DE EXECUÇÃO.
EXECUÇÃO
• INTERNAMENTE, QUANDO QUALQUER CHAMADA DE
FUNÇÃO É FEITA DENTRO DE UM PROGRAMA, É
CRIADO UM REGISTRO DE ATIVAÇÃO NA PILHA DE
EXECUÇÃO DO PROGRAMA
•O REGISTRO DE ATIVAÇÃO ARMAZENA OS
PARÂMETROS E VARIÁVEIS LOCAIS DA FUNÇÃO BEM
COMO O “PONTO DE RETORNO” NO PROGRAMA OU
SUBPROGRAMA QUE CHAMOU ESSA FUNÇÃO.
•AO FINAL DA EXECUÇÃO DESSA FUNÇÃO, O
REGISTRO É DESEMPILHADO E A EXECUÇÃO VOLTA
AO SUBPROGRAMA QUE CHAMOU A FUNÇÃO
EXEMPLO – FATORIAL DE UM NÚMERO
1. algoritmo "FatorialRecursivo"
2. var
3. f,n:inteiro
4. funcao Fat(n: inteiro): inteiro
5. inicio
6. Se (n<=0) entao
7. retorne 1
8. senao
9. retorne n * Fat(n-1)
10. fimse
11. fimfuncao
12.inicio
13. escreva("Informe um numero inteiro positivo: ")
14. leia(n)
15. f <- Fat(n)
16. escreva("O fatorial de",n," é:",f)
17.fimalgoritmo
Condição de parada
EXEMPLO – SÉRIE DE FIBONACCI
1. ALGORITMO "FIBONATTIRECURSIVO"
2. VAR
3. F,N,I:INTEIRO
4. FUNCAO FIB(N: INTEIRO): INTEIRO
5. INICIO
6. SE (N<=0) ENTAO
7. RETORNE 0
8. SENAO
9. SE (N<=2) ENTAO
10. RETORNE N-1
11. SENAO
12. RETORNE FIB(N-1) + FIB(N-2)
13. FIMSE
14. FIMSE
15. FIMFUNCAO
16. INICIO
17. ESCREVA("INFORME O TAMANHO DA SÉRIE (N>0): ")
18. LEIA(N)
19. ESCREVA("A SÉRIE FIBONATTI DE TAMANHO",N," É: ")
20. PARA I<-1 ATE N FACA
21. ESCREVA(FIB(I)," ")
22. FIMPARA
23. FIMALGORITMO