Recorrência

Universidade do Oeste de Santa Catarina - Unoesc
Ciências Exatas e da Terra
Curso de Ciência da Computação

Análise e Complexidade de Algoritmos
Recorrência
Herculano De Biasi – [e-mail]

Campus de Videira

Tópicos





Relação de Recorrência
Soluções em Forma Fechada
Verificação por Indução
Demonstração por Indução

2

Relação de Recorrência (1)




𝑃: ℕ → ℤ

Definição recursiva para o conjunto de todos os números ímpares:
1.

2.




Relação: entra um número natural e sai um inteiro

Caso base: o número 1 está no conjunto Χ
Se x está em Χ, então x + 2 também está
𝑛 ∈ ℕ|𝑛 = 2𝑘 + 1 𝑝𝑎𝑟𝑎 𝑎𝑙𝑔𝑢𝑚 𝑖𝑛𝑡𝑒𝑖𝑟𝑜 𝑘

𝑃 𝑛 =

𝑛(𝑛+1)
2

Fórmula explícita

3

Relação de Recorrência (2)












Definição recursiva:
1
se n = 1 P é definida em termos de si mesma
𝑃 𝑛 =
𝑛+ 𝑃 𝑛−1 se 𝑛 > 1
O cálculo pode ser feito de duas formas diferentes: ascendente ou descendente Exemplo com P(5):
Ascendente:
n=1 P(1)=1 n=2 P(2)=2+P(1)=2+1=3 n=3 P(3)=3+P(2)=3+3=6 n=4 P(4)=4+P(3)=4+6=10 n=5 P(5)=5+P(4)=5+10=15











Descendente:
P(5)=5+P(4)
=5+4+P(3)
=5+4+3+P(2)
=5+4+3+2+P(1)
=5+4+3+2+1
=15

A equação 𝑃 𝑛 = 𝑛 + 𝑃 𝑛 − 1 sozinha não define uma relação de recorrência, pois não tem condição de término. É necessário, portanto, um caso base, não recursivo, que é, nesse caso, 1 se n = 1
4

Relação de Recorrência (3)












Problema: um casal de coelhos é colocado em um local cercado. Todo mês o casal gera um novo par que se torna produtivo a partir do segundo mês. Quantos pares podem ser produzidos a partir do par original em um ano?
𝐹(1) = 𝐹(2) = 1
1
𝐹 𝑛 =
𝐹(𝑛 − 1) + 𝐹 𝑛 − 2

se 𝑛 = 1 ou 𝑛 = 2 se 𝑛 > 2

𝐹 𝑛 − 1 : número de pares de coelhos no mês anterior
𝐹(𝑛 − 2): número de pares de coelhos dois meses atrás

Essa é a mesma definição da Sequência de Fibonacci,