DEFINIÇÕES RECURSIVAS: ○ Definição recursiva é uma definição na qual o item que está sendo definido aparece como parte da definição
○ Esse procedimento funciona porque as definições recursivas são formadas por duas partes:
1. Uma base, que determina explicitamente alguns casos simples do item que está sendo definido
2. Um passo indutivo ou recursivo, onde outros casos do item que está sendo definido são determinados em termos dos casos anteriores
○ 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(k) denota o k­ésimo elemento da sequência
○ Uma sequência recursiva explicita seu primeiro valor (ou primeiros valores) e define outros valores na sequência em termos dos valores iniciais

EXEMPLOS: ○ Sequência definida recursivamente
1. S(1) = 2
2. S(n) = 2S(n­1) para n ≥ 2
○ O primeiro valor da sequência é explicitamente dado, S(1) = 2, os valores seguintes são sucessivamente calculados com base na definição recursiva:
■ S(2) = 2S(1) = 2*2 = 4
■ S(3) = 2S(2) = 2*4 = 8
■ S(4) = 2S(3) = 2*8 = 16
■ ...
○ Escreva os primeiros 5 valores da Sequência T definida por: 1. T(1) = 1
2. T(n) = T(n­1)+3 para n ≥ 2
■ T(1) = 1
■ T(2) = T(1) + 3 = 1 + 3 = 4
■ T(3) = T(2) + 3 = 4 + 3 = 7
■ T(4) = T(3) + 3 = 7 + 3 = 10
■ T(5) = T(4) + 3 = 10 + 3 = 13

RELAÇÃO DE RECORRÊNCIA
○ É uma regra que define um valor da sequência a partir de um ou mais valores anteriores
○ A sequência de Fibonacci pode ser definida recursivamente como se segue:
F(1) = 1
F(2) = 2
F(n) = F(n­2) + F(n­1) para n > 2
F(3) = 1 + 2 = 3
F(4) = 2 + 3 = 5
F(5) = 3 + 5 = 8
○

Prove que na sequência de Fibonacci:
F(n+4) = 3F(n+2) – F(n)
para todo n ≥ 1
■ A indução completa é necessária porque a relação de recorrência para a sequência de Fibonacci usa mais termos do que o termo imediatamente anterior.
■ BASE: •
Para a base de indução devemos considerar os casos para n = 1 e n = 2
•
Para n = 1, F(5) = 3F(3) – F(1) = 3.3 – 1 = 9 – 1 = 8
•
Para n = 2, F(6) = 3F(4)– F(2) = 3.5 – 2 = 15 – 2 = 13
■ Hipótese Indutiva:
•
Para todo r, 1 ≤ r ≤ k, F(r+4) = 3F(r+2) – F(r)
•
Vejamos agora o ocorre com k+1, onde (k+1)≥3
•
Desejamos mostrar que: ○ F(k+1+4) = 3F(k+1+2) – F(k+1), ou F(k+5) = 3F(k+3) – F(k+1)
•
Da relação de recorrência de Fibonacci temos:
○ F(k+5) = F(k+3) + F(k+4)
•
Pela hipótese de indução:
○ Para r = k – 1, F(k+3) = 3F(k+1) – F(k­1)
○ Para r = k, F(k+4) = 3F(k+2) – F(k)
•
Substituindo na recorrência de Fibonacci:
○ F(k+5) = [3F(k+1) – F(k­1)] + [3F(k+2) – F(k)]
○ F(k+5) = 3[F(k+1) + F(k+2)] – [F(k­1) + F(k)]
○ F(k+5) = 3F(k+3) – F(k+1)
○ Ou seja, para r = k + 1, F(r+4) = 3F(r+2) – F(r)
○ c.q.d
CONJUNTOS RECURSIVOS: Enquanto objetos de uma sequência são ordenados, um conjunto é uma coleção de objetos na qual nenhuma regra de ordenação é imposta. Certos conjuntos podem ser definidos recursivamente:
○ Definição recursiva para o conjunto dos ancestrais de um ser vivo:
Os pais de um ser vivo são seus ancestrais
Todo pai de um ancestral também é um ancestral
•
•
○
Seja S o conjunto dos inteiros positivos divisíveis por 3, definido recursivamente por:
1. 3 ∊ S
2. (x + y) ∊ S se (x ∊ S) e (y ∊ S)
○
Prova: ■
Seja A o conjunto de todos os inteiros positivos divisíveis por 3. Para mostrar que A = S, é necessário que A ⊆ S e S ⊆ A
■
Parte I: Prove que A ⊆ S (usando indução matemática)
•
Seja P(n) a afirmativa “3n pertence a S”.
○
Passo básico:
■
P(1) é verdade, porque 3 ∊ S
○
Passo Indutivo: ■
■
●
Assuma que 3n ∊ S. Como 3 ∊ S, da definição recursiva de S temos que 3n + 3 = 3(n + 1) ∈ S.
●
Conclusão da Parte I: A ⊆ S
Parte II: Mostrar que S ⊆ A
•
•

Se P(n) → P(n + 1)
Passo básico:
○
Todos os elementos iniciais de S estão em A. ○
3 está em A. (TRUE)
Passo Indutivo: (x ∈ S) ∧ (y ∈ S) → (x + y) ∈ A
○
Se x e y estão em A, Então 3|x e 3|y. Da propriedade da linearidade da divisibilidade (c|a e c|b) → c|(ra+sb) para quaisquer inteiros a,b,c,r,s) segue que 3|(x+y).
○
Conclusão da Parte II: S ⊆ A. Logo: A = S
OPERAÇÕES RECURSIVAS: Certas operações sobre objetos podem ser definidas recursivamente:
○
n
Definição recursiva para a operação de exponenciação a , definida para um número real a diferente de zero e n inteiro não­negativo:
0
1. a = 1
0
2. a = (a

n­1
).a para n ≥ 1
○
Definição recursiva para a multiplicação de dois inteiros positivos m e n:
1. m(1) = m
2. m(n) = m(n­1) + m para n ≥ 1
○
Definição recursiva para o fatorial de um inteiros positivo m:
1. m(0) = 1
2. m(n) = m(n­1) x m para n ≥ 1
ALGORITMOS RECURSIVOS
○
Considere a definição recursiva da sequência S:
■ S(1) = 2
■ S(n) = 2 * S(n­1) para n ≥ 2
○
Essa definição pode ser usada para escrever um algoritmo para obter S(n) para algum inteiro positivo n.
○
Versão iterativa do algoritmo que calcula os valores de S(n) para a sequência S
int S(int n)
{
int i, current;
SE (n = 1) ENTÃO
return S;
SENÃO
{
i = 2;
current = 2;
ENQUANTO(i ≤ n)
{
current = 2 * current;
i = i + 1;
}
return current;
}
}
○
Versão recursiva do algoritmo que calcula os valores de S(n) para a sequência S
int S(int n)
{
SE (n = 1) ENTÃO
return 2;
SENÃO
return (2*S(n­1));
}
○
Ambas as versões têm vantagens e desvantagens. em alguns casos, como no exemplo acima, a versão recursiva oferece uma abordagem mais natural. Em certos casos a versão iterativa poderia ser extremamente complexa. Em contrapartida, a versão recursiva pode demandar grande quantidade de memória e causar “estouro de pilha”.
○
Considere a sequência definida recursivamente por:
1. T(1) = 1
2. T(n) = T(n­1)+3 para n ≥ 2
■ Escreva o corpo da função recursiva para computar T(n)
int T(int n)
{
SE (n = 1) ENTÃO
return 1;
SENÃO
return (T(n­1)+3);
}