Algoritmos Avançados 003

Prévia do material em texto

RECURSIVIDADE
DEFINIÇÕES RECURSIVAS:
Definição recursiva é  uma definição na qual o item que está sendo definido aparece como parte da definição.
 
A recursão pode ser usada para definir sequências de objetos, operações sobre objetos, conjuntos e algoritmos.
SEQUÊNCIA RECURSIVA:
Uma sequência é uma lista de objetos enumerados segundo uma ordem;
S(n) denota o en­ésimo elemento da sequência;
Uma sequência recursiva apresenta um primeiro valor que pode ser primeiros valores
e define os outros valores da sequência com base nos valores iniciais.
Sequência definida recursivamente:
EXEMPLO:
S(1) = 2 
S(n) = 2*S(n-­1) para n ≥ 2
O primeiro valor da sequência é fornecido. S(1)=2.
Os valores que seguem são calculados de forma sucessiva, tendo a definição recursiva como base:
S(2) = 2*S(1) = 2*2 = 4
S(3)= 2*S(2) = 2*4 = 8
S(4)= 2*S(3) = 2*8 =16
S(5)=2*S(4) = 2*16 = 32
RECURSIVIDADE
RECURSIVIDADE
Sequência definida recursivamente:
OUTRO EXEMPLO:
Demonstre os primeiros 4 valores da sequência X definida da seguinte forma:
X(1) = 1
X(n) = X(n-1) + 3 para n >= 2
X(1) = 1
X(2) = X(1) +3 = 1+3 = 4
X(3) = X(2) + 3 = 4+3 =7
X(4) = X(3) + 3 = 7+3 = 10 
RECURSIVIDADE
RELAÇÃO DE RECORRÊNCIA:
É uma regra que define um valor da sequência a partir de um ou mais valores anteriores.
SEQUÊNCIA DE FIBONACCI:
É uma sequência de números inteiros , começando normalmente por 0 e 1, na qual, cada termo subsequente corresponde à soma dos dois anteriores.
EXEMPLO:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Fn = Fn-1+ Fn-2, ...
DEFINIÇÃO RECURSIVA DA SEQUÊNCIA DE FIBONACCI
F(1) = 1
F(2) = 2
F(n) = F(n-1) + F(n-2) para n > 2
F(3) = 2+1= 3
F(4) = 3+2= 5
F(5) = 5+3= 8
RECURSIVIDADE
EXEMPLO:
Número natural n e a soma de todos os números de n até zero.
0=0
1=1+0
2=2+1+0
3=3+2+1+0
4=4+3+2+1+0
Elementos a serem levados em consideração – condição de parada e passo recursivo.
Caso base - último elemento é sempre zero.
Para cada valor de n, será diminuído de 1 até chegar a zero.
O somatório de um número é ele mesmo mais o somatório do anterior.
n=n+(n-1)+(n-2)+(n-3)...+0
Passo recursivo: n+soma(n-1)
Função recursiva:
int soma(int n){ 
 if(n == 0) 
 return 0; 
 return n + soma(n-1);
 }
RECURSIVIDADE
algoritmo ”fatorial“
var
n, i, f:inteiro
inicio
 F <- 1
 Escreva("Digite um número:")
 leia(n)
 para i de 1 ate n faca
 f <- f*i
 fimpara
 Escreva("Fatorial de ",n,"=",f)
fimalgoritmo
algoritmo ”fatorial“
funcao fatorial(n:inteiro):inteiro
iniciofuncao
 se n <= 1 então
 retorne 1
 senao
 retorne n*fatorial(n-1)
 fimse
fimfuncao
var
n, f:inteiro
inicio
 Escreva("Digite um número:")
 leia(n)
 f <- fatorial(n)
 Escreva("Fatorial de ",n,"=",f)
fimalgoritmo
SEM RECURSIVIDADE
COM RECURSIVIDADE