Universidade Federal do Vale do São Francisco
Curso de Engenharia da Computação
Matemática Discreta - 06
Prof. Jorge Cavalcanti
[email protected]
www.univasf.edu.br/~jorge.cavalcanti
www.twitter.com/jorgecav
1
Recursividade e relações de recorrência
2
1
Recursividade e Relações de Recorrência
Definições Recorrentes
Uma definição onde o item a ser definido aparece como
parte da definição é chamada de definição recorrente ou
definição por recorrência ou ainda definição por
indução.
Como definir algo em torno de si mesmo?
1.
2.
Uma base, ou condição básica, onde alguns casos simples
(pelo menos um) do item que está sendo definido são dados
explicitamente.
Um passo de indução ou recorrência, onde novos casos do
item que está sendo definido são dados em função dos casos
anteriores.
O item 1 nos dá o começo, fornecendo casos simples e
concretos.
O item 2 nos permite construir novos casos, a partir dos
simples e ainda outros casos a partir desses novos e assim
por diante.
3
Recursividade e Relações de Recorrência
Sequências definidas por Recorrência
Uma sequência S é uma lista de objetos que
são numerados em uma determinada ordem.
Existe um primeiro objeto, um segundo e
assim por diante.
S(k) denota o k-ésimo objeto da sequência.
Uma sequência é definida por recorrência
nomeando-se o primeiro valor (ou alguns
primeiros) na sequência e depois definindo os
demais valores subsequentes em termos dos
valores anteriores.
4
2
Recursividade e Relações de Recorrência
Sequências definidas por Recorrência
Ex. 01:A seqüência S é definida por recorrência por
1.S(1)
=2
= 2S(n -1) para n ≥ 2
Pela proposição 1, S(1) = 2. Depois, pela proposição 2, o
segundo objeto em S é S(2) = 2S(1) = 2(2)=4.
Novamente, pela proposição 2, S(3)=2S(2) = 2(4) = 8.
Continuando desse modo, vemos que a sequência S é:
2, 4, 8, 16, 32...
2.S(n)
Uma regra como a da proposição 2, que define um
valor de uma sequência em termos de um ou mais
valores anteriores é uma relação de recorrência.
5
Recursividade e Relações de Recorrência
Sequências definidas por Recorrência
Ex. 02:A seqüência T é definida por recorrência por
1.T(1)
=1
= T(n -1) + 3 para n ≥ 2
Escreva os cinco primeiros valores da sequência T.
2.T(n)
Ex. 03: A famosa sequência de Fibonacci é uma
sequência de números definida por recorrência por:
F(1) = 1
F(2) = 1
F(n) = F(n-2) + F(n-1), para n>2
Nesse caso, são dados os dois primeiros valores e relação
de recorrência define o n-ésimo valor em termos dos dois
valores precedentes.
Na sua forma mais geral, a relação de recorrência é a
soma de F em seus dois valores anteriores.
Ex. 04: Escreva os oito primeiros valores da sequência
de Fibonacci.
6
3
Recursividade e Relações de Recorrência
Sequências definidas por Recorrência
Ex. 05: Prove diretamente que, na sequência de
Fibonacci, a fórmula F(n+4)=3F(n+2) – F(n), para todo n
≥ 1, é verdadeira.
A relação de recorrência da sequência de Fibonacci pode
ser escrita como: F(n+2)=F(n)+F(n+1) ou,
F(n+1) = F(n+2) – F(n) (1)
Logo, F(n+4)=F(n+2)+F(n+3)
F(n+4)=F(n+2)+F(n+2)+F(n+1) //Reescrevendo F(n+3)
F(n+4)=F(n+2)+ F(n+2)+[F(n+2)-F(n)] // de (1)
F(n+4)=3F(n+2)-F(n)
7
Recursividade e Relações de Recorrência
Sequências definidas por Recorrência
Ex. 06: Prove diretamente que, na sequência de
Fibonacci, a fórmula F(n+1)+F(n-2) = 2F(n), para todo n
≥ 3, é verdadeira.
Da relação de Recorrência:
F(n+1)=F(n-1) + F(n) e
F(n)=F(n-1)+F(n-2)
= F(n-1)+F(n) + F(n-2) = [F(n-1)+F(n-2)] + F(n)
=F(n)+ F(n) = 2F(n)
Observar que só é válida porque n ≥ 3.
8
4
Recursividade e Relações de Recorrência
Sequências definidas por Recorrência
Ex. 07: Prove diretamente que, na sequência de
Fibonacci, a fórmula F(n+3)=2F(n+1) + F(n), para todo n
≥ 1, é verdadeira.
9
Recursividade e Relações de Recorrência
Operações definidas por Recorrência
Certas operações comuns em objetos podem ser
definidas de forma recorrente, conforme os exemplos
a seguir:
Ex. 08: Uma definição recorrente da operação de
exponenciação an de um número real não nulo a, onde
n é um inteiro não negativo é:
1.
2.
a0=1
an=(an-1)a para n≥1
Ex. 09: Uma definição recorrente para a multiplicação
de dois inteiros positivos m e n é:
1.
2.
m(1) = m
m(n) = m(n-1) + m para n≥2
10
5
Recursividade e Relações de Recorrência
Resolvendo Relações de Recorrência
Tomando por base novamente o Exemplo 01
Ex.01: A seqüência S é definida por recorrência por
S(1) = 2
S(n) = 2S(n -1) para n ≥ 2
(1)
(2)
Como:
S(1) = 2 = 21
S(2) = 4 = 22
Solução em
S(3) = 8 = 23
forma fechada
para a relação de
S(4) = 16 = 24
recorrência (2)
e assim por diante, vemos que
sujeita à condição
básica (1)
n
S(n) = 2
(3)
É possível calcular diretamente S(n) sem ter que
calcular explicitamente ou por recorrência.
11
Recursividade e Relações de Recorrência
Resolvendo Relações de Recorrência
Relações de recorrência são usadas em programas
computacionais, estudos de decaimento químico,
crescimento populacional etc.
Seria bom encontrar sempre soluções fechadas!
Uma técnica para resolver relações de recorrência é
uma abordagem do tipo “expandir, conjecturar e
verificar”.
Essa técnica usa repetidamente a relação de recorrência
para expandir a expressão a partir do n-ésimo termo até
que se tenha uma idéia da forma geral.
Após obtida a forma geral, a conjectura é provada por
indução matemática.
12
6
Recursividade e Relações de Recorrência
Resolvendo Relações de Recorrência
Ex. 10: Considere novamente a seqüência S
S(1) = 2
S(n) = 2S(n -1) para n ≥ 2
(1)
(2)
Desconsiderando que já sabemos a solução fechada,
vamos usar a abordagem de expandir, conjecturar e
verificar para encontrar a solução.
A relação S(n) = 2S(n -1) estabelece que um elemento S
pode ser substituído por duas vezes o elemento anterior.
Seguindo essa receita, expandimos para n, n-1, n-2, assim
por diante:
S(n) = 2S(n -1)
= 2[2S(n -2)] = 22S(n-2)
= 22[2S(n-3)] = 23S(n-3)
Olhando o padrão que está se formando, conjecturamos
que, após k expansões, a equação tem a forma:
S(n) = 2kS(n-k)
13
Recursividade e Relações de Recorrência
Resolvendo Relações de Recorrência
Ex. 10: Forma geral da expansão:
S(n) = 2kS(n-k)
A expansão dos elementos de S em função dos
elementos anteriores pára quando n-k=1 (significa que
estamos com o último e o penúltimo elemento da
relação).
n-k =1 então, k=n-1 e nesse ponto temos:
S(n) = 2n-1S[n-(n-1)] = 2n-1S(1)
2n-1(2) = 2n que é a solução em forma fechada
A solução encontrada é apenas a conjectura, que
precisa ser confirmada, ou seja devemos provar que
S(n)=2n para n≥ 1.
Provaremos usando a indução matemática.
14
7
Recursividade e Relações de Recorrência
Resolvendo Relações de Recorrência
Ex. 10: Provar que S(n) = 2n para n≥ 1.
Base da indução S(1) = 21 é verdadeiro
2. Hipótese da indução S(k) = 2k
3. Devemos provar que S(k+1) = 2k+1
S(k+1) = 2S(k)
S(k+1) =2(2k)
S(k+1) =2k+1 – Isso prova que a solução fechada
encontrada está correta.
1.
15
8