Roteiro
Recursividade e Relações de Recorrência
Prof. Dr. Leandro Balby Marinho
Matemática Discreta
Prof. Dr. Leandro Balby Marinho
1/1
UFCG CEEI
Recursividade
Prof. Dr. Leandro Balby Marinho
2/1
UFCG CEEI
Sequências
Sequência
Uma definição onde um item é definido em termos de si mesmo é
chamada de uma definição recursiva ou definição por recorrência.
Uma sequência s é uma lista de objetos numerados em determinada
ordem. s(n) denota o n-ésimo elemento da sequencia.
Por exemplo a sequência s(n) = 2n − 1, onde n ∈ Z+ , é definida
por:
Uma definição recursiva tem duas partes:
1. Um caso base, onde casos mais simples do item sendo
definido são especificados.
s(1) = 2(1) − 1 = 1
2. Um passo recursivo, onde novos casos são construı́dos em
função de casos anteriores.
s(2) = 2(2) − 1 = 3
s(3) = 2(3) − 1 = 5
..
.
Prof. Dr. Leandro Balby Marinho
2/1
UFCG CEEI
Prof. Dr. Leandro Balby Marinho
3/1
UFCG CEEI
Sequências Definidas Recursivamente
Sequências Definidas Recursivamente
Considere a sequência s abaixo.
Sequência de Fibonacci
A sequência de Fibonacci f é definida por:
1. s(1) = 1 (condição básica)
1. f (0) = 0 (condição básica)
2. s(n) = s(n − 1) + 2 para n ≥ 2 (passo recursivo)
2. f (1) = 1 (condição básica)
O primeiro elemento é s(1) = 1 pela condição básica. A partir disso,
aplicando o passo recursivo temos:
s(2) = s(1) + 2 = 1 + 2 = 3
3. f (n) = f (n − 1) + f (n − 2) para n ≥ 2 (passo recursivo)
Por exemplo, a sequência de Fibonacci para 2 ≤ n ≤ 6 segue abaixo:
s(3) = s(2) + 2 = 3 + 2 = 5
f (2) = f (1) + f (0) = 1 + 0 = 1
s(4) = s(3) + 2 = 5 + 2 + 7
..
.
f (3) = f (2) + f (1) = 1 + 1 = 2
f (4) = f (3) + f (2) = 2 + 1 = 3
f (5) = f (4) + f (3) = 3 + 2 = 5
f (6) = f (5) + f (4) = 5 + 3 = 8
Também são chamadas de relações de recorrência.
Prof. Dr. Leandro Balby Marinho
4/1
UFCG CEEI
Conjuntos Definidos por Recorrência
Prof. Dr. Leandro Balby Marinho
5/1
UFCG CEEI
Exercı́cio 1
Um conjunto é uma coleção não ordenada de objetos.
Dê uma definição recursiva para o conjunto de pessoas que são
ancestrais de João. A condição básica é dada abaixo:
Por exemplo, o subconjunto S dos inteiros definido por
1. 3 ∈ S (condição básica)
2. Se x ∈ S e y ∈ S, então x + y ∈ S (passo recursivo).
1. Os pais de João são seus ancestrais (condição básica)
2. Passo recursivo ?
Alguns elementos de S são 3 + 3 = 6, 3 + 6 = 6 + 3 = 9,
6 + 6 = 12 e assim por diante. S se trata dos múltiplos positivos
de 3 (verifique isso).
Prof. Dr. Leandro Balby Marinho
6/1
UFCG CEEI
Prof. Dr. Leandro Balby Marinho
7/1
UFCG CEEI
Cadeias Definidas por Recorrência
Operações Definidas por Recorrência
Cadeia
Certas operações em objetos podem ser definidas por recorrência.
O conjunto Σ∗ de cadeias sob o alfabeto Σ pode ser definido por:
1. λ ∈ Σ∗ (no qual λ é a cadeia vazia) (condição básica)
2. Se w ∈ Σ∗ e x ∈ Σ, então wx ∈ Σ∗ (passo recursivo).
Por exemplo, uma definição recursiva para a exponenciação an de
um número real não nulo a, no qual n é um inteiro positivo é
1. a0 = 1 (condição básica)
2. an = a(an−1 ) para n ≥ 1 (passo recursivo)
Por exemplo, seja Σ = {0, 1}. O conjunto Σ∗ de todas as cadeias
em Σ pode ser dado usando-se a definição recursiva acima.
A condição básica forma a cadeia vazia λ. Na primeira aplicação do
passo recursivo, as cadeias 0 e 1 são formadas. Na segunda aplicação
do passo recursivo, as cadeias 00, 01, 10 e 11 são formadas e assim
por diante.
Prof. Dr. Leandro Balby Marinho
8/1
UFCG CEEI
Roteiro
Outro exemplo é a definição recursiva para a multiplicação dos
inteiros positivos a e b:
1. a(1) = a (condição básica)
2. a(b) = a(b − 1) + a para b ≥ 2 (passo recursivo)
Prof. Dr. Leandro Balby Marinho
9/1
UFCG CEEI
Relações de Recorrência
As vezes é conveniente expressar uma relação de recorrência como uma
solução fechada. Por exemplo, expandindo a recorrência
S(1) = 2
S(n) = 2S(n − 1) para n ≥ 2
S(1) = 2 = 21
S(2) = 4 = 22
S(3) = 8 = 23
S(4) = 16 = 24
..
.
vemos que S(n) = 2n . Prove!
Prof. Dr. Leandro Balby Marinho
10 / 1
UFCG CEEI
Prof. Dr. Leandro Balby Marinho
10 / 1
UFCG CEEI
Expandir, Conjecturar e Verificar
Exemplo 1
I
Expandir: usa repetidamente a recorrência para expandir a
expressão a partir do n-ésimo termo até o caso base.
I
Conjecturar: a expansão nos ajuda a conjecturar a solução da
recorrência.
I
Resolva a seguinte relação de recorrência:
S(1) = 2
S(n) = 2S(n − 1) para n ≥ 2
Verificar: a conjectura é finalmente verificada por indução.
Prof. Dr. Leandro Balby Marinho
11 / 1
UFCG CEEI
Exemplo 1 cont.
Prof. Dr. Leandro Balby Marinho
12 / 1
UFCG CEEI
Exemplo 1 cont.
Expandindo aplicando a definição para n, n − 1, n − 2, etc.:
A expansão tem que parar quando n − k = 1, ou seja, quando
k = n − 1. Nesse ponto temos:
S(n) = 2S(n − 1)
= 2[2S(n − 2)] = 22 S(n − 2)
2
S(n) = 2n−1 S[n − (n − 1)]
3
= 2 [2S(n − 3)] = 2 S(n − 3)
= 2n−1 S(1)
= 23 [2S(n − 4)] = 24 S(n − 4)
= 2n−1 (2)
..
.
= 2n
Analisando o padrão, conjecturamos que, após k expansões, a equação
tem a forma
S(n) = 2k S(n − k)
Prof. Dr. Leandro Balby Marinho
13 / 1
UFCG CEEI
Ainda falta provar que 2n é a solução da recorrência.
Prof. Dr. Leandro Balby Marinho
14 / 1
UFCG CEEI
Exemplo 1 cont.
Exemplo 2
A base da indução é S(1) = 21 que é verdade pelo caso base da
definição recursiva.
Supondo que S(k) = 2k , queremos provar que S(k + 1) = 2k+1 :
Resolva a seguinte relação de recorrência:
S(1) = 4
S(k + 1) = 2S(k)
S(n) = 2S(n − 1) + 3 para n ≥ 2
k
S(k + 1) = 2(2 )
S(k + 1) = 2k+1
E portanto fica provada a relação de recorrência.
Prof. Dr. Leandro Balby Marinho
15 / 1
UFCG CEEI
Exemplo 2 cont.
Prof. Dr. Leandro Balby Marinho
16 / 1
UFCG CEEI
Exemplo 2 cont.
Expandindo aplicando a definição para n, n − 1, n − 2, etc.:
A expansão tem que parar quando n − k = 1, ou seja, quando
k = n − 1. Nesse ponto temos:
S(n) = 2S(n − 1) + 3
= 2[2S(n − 2) + 3] + 3 = 22 S(n − 2) + 2 · 3 + 3
= 22 [2S(n − 3) + 3] + 2 · 3 + 3 = 23 S(n − 3) + 22 · 3 + 2 · 3 + 3
..
.
S(n) = 2n−1 S(1) + 2n−2 · 3 + 2n−3 · 3 + . . . + 22 · 3 + 2 · 3 + 3
= 2n−1 (4) + 3[2n−2 + 2n−3 + . . . + 22 + 2 + 1]
= 2n+1 + 3[2n−1 − 1]
Analisando o padrão, conjecturamos que, após k expansões, a
equação tem a forma
Prove por indução que 2n+1 + 3[2n−1 − 1] é a solução da
recorrência.
S(n) = 2k S(n − k) + 2k−1 · 3 + . . . + 22 · 3 + 2 · 3 + 3
Prof. Dr. Leandro Balby Marinho
17 / 1
UFCG CEEI
Prof. Dr. Leandro Balby Marinho
18 / 1
UFCG CEEI
Exercı́cio 2
Teorema 1
Se
Considere uma recorrência da forma
(
rT (n − 1) + a,
T (n) :=
b,
(
rT (n − 1) + a,
T (n) :=
b,
se n > 0,
se n = 0.
com r 6= 1 então
onde r e a são constantes. Conjecture uma forma fechada para essa
recorrência.
T (n) = r n + a
se n > 0,
se n = 0
1 − rn
1−r
para todo n ∈ N.
Prof. Dr. Leandro Balby Marinho
19 / 1
UFCG CEEI
Prova do Teorema 1
Caso base: T (0) =
r 0b
Prof. Dr. Leandro Balby Marinho
20 / 1
UFCG CEEI
Prova do Teorema 1 Cont.
1 − r0
+a
=b
1−r
Hip. Indutiva: T (n − 1) = r n−1 b + a
Mostrar: T (n) = r n b + a
T (n) = rT (n − 1) + a
1 − r n−1
n−1
=r r
b+a
+a
1−r
ar − ar n
= r nb +
+a
1−r
ar − ar n + a − ar
= r nb +
1−r
n
1
−
r
= r nb + a
1−r
Q.E.D
1 − r n−1
1−r
1 − rn
1−r
Q.E.D.
Prof. Dr. Leandro Balby Marinho
21 / 1
UFCG CEEI
Prof. Dr. Leandro Balby Marinho
22 / 1
UFCG CEEI
Exercı́cio 3
Recorrências Lineares de Primeira Ordem
Uma recorrência da forma T (n) = f (n)T (n − 1) + g (n) é chamada
de recorrência linear de primeira ordem. Quando f (n) é uma
constante, como r , expandindo a recorrência temos:
T (n) = rT (n − 1) + g (n)
= r (rT (n − 2) + g (n − 1)) + g (n)
Resolva a recorrência do Exemplo 2 usando o Teorema 1.
= r 2 T (n − 2) + rg (n − 1) + g (n)
= r 2 rT (n − 3) + r 2 g (n − 2) + rg (n − 1) + g (n)
= r 3 T (n − 3) + r 2 g (n − 2) + rg (n − 1) + g (n)
..
.
n
= r T (0) +
n−1
X
r i g (n − i)
i=0
Prof. Dr. Leandro Balby Marinho
23 / 1
UFCG CEEI
Recorrências Lineares de Primeira Ordem
Prof. Dr. Leandro Balby Marinho
24 / 1
UFCG CEEI
Exemplo 3
Teorema 1
Para as constantes positivas a e r e qualquer função g definida nos
naturais, a solução para a recorrência linear de primeira ordem
(
rT (n − 1) + g (n), se n > 0,
T (n) :=
a,
se n = 0.
Resolva a recorrência:
(
4T (n − 1) + 2n , se n > 0,
T (n) :=
6,
se n = 0.
é dada por
T (n) = r n a +
n
X
r n−i g (i)
i=1
Prof. Dr. Leandro Balby Marinho
25 / 1
UFCG CEEI
Prof. Dr. Leandro Balby Marinho
26 / 1
UFCG CEEI
Exemplo 3 Cont.
Roteiro
n
T (n) = 6 · 4 +
n
X
4n−i · 2i
i=1
n
=6·4 +4
n
n
X
4−i · 2i
i=1
= 6 · 4n + 4n
n i
X
1
i=1
2
n−1 1X 1 i
2
2
i=0
n 1
= 6 · 4n + 1 −
· 4n
2
= 7 · 4n − 2n
= 6 · 4n + 4n ·
Prof. Dr. Leandro Balby Marinho
27 / 1
UFCG CEEI
Algoritmos Recursivos
Prof. Dr. Leandro Balby Marinho
28 / 1
UFCG CEEI
Exemplo 4
Algoritmo recursivo para calcular n!
Algoritmo Recursivo
Fat(n)
Um algoritmo é recursivo quando ele resolve um problema
reduzindo-o a instâncias menores do mesmo problema.
1
2
3
4
Prof. Dr. Leandro Balby Marinho
28 / 1
UFCG CEEI
if n == 0
return 1
else
return Fat(n − 1) · n para n > 0
Prof. Dr. Leandro Balby Marinho
29 / 1
UFCG CEEI
Exemplo 5
Corretude de Algoritmos Recursivos
Algoritmo recursivo para calcular an
Pot(a, n)
1
2
3
4
if n == 0
return 1
else
return a · Pot(a, n − 1)
Prof. Dr. Leandro Balby Marinho
30 / 1
UFCG CEEI
Exemplo 6
I
Indução matemática pode ser usada para provar que
algoritmos recursivos estão corretos.
I
Defina a conjectura a provar.
I
Caso Base: condição de parada do algoritmo.
I
Assuma que as chamadas recursivas anteriores estão corretas
(hipótese indutiva).
I
Use a hip. indutiva para provar que a execução atual é correta
(passo indutivo).
Prof. Dr. Leandro Balby Marinho
31 / 1
UFCG CEEI
Exercı́cio 4
Prove que o algoritmo do fatorial recursivo é correto.
I
Conjectura: Fat(n) = n!, para n ≥ 0
I
Caso Base: Se n = 0, então Fat(n) = 1. Isso é correto já
que 0! = 1.
I
Hip. indutiva: Agora assumimos que Fat(k) = k!
I
Mostrar: Fat(k + 1) = (k + 1)!
I
Passo Indutivo: Como
Mostre que o algoritmo Pot é correto.
Fat(k + 1) = Fat(k) · (k + 1)
e pela hipótese indutiva Fat(k) = k!, segue que
Fat(k + 1) = (k + 1) · k! = (k + 1)!
Prof. Dr. Leandro Balby Marinho
32 / 1
UFCG CEEI
Prof. Dr. Leandro Balby Marinho
33 / 1
UFCG CEEI