Recursividade

Recursividade

1. Recursividade é o mecanismo de programação no qual uma definição de função ou de outro objeto refere-se ao próprio objeto sendo definido. Assim função recursiva é uma função que é definida em termos de si mesma.

2. Como determinar a fórmula fechada de uma regra que é estabelecida por recorrência.

   • Método Expandir/Conjecutar/Verificar
     • Esse método possui três etapas, em que iremos expandir a fórmula, começando do i'néssimo termo, para tentar conjecturar uma fórmula fechada. Uma vez pensada em uma fórmula, verificamos se está correta.
     • Exemplo
       • Expansão
         • Na expansão, tentamos manipular a fórmula recursiva para tentar alcançar alguma fórmula fechada. No exemplo acima, verificamos que Q(n) será igual a 2^n.Q(n-1) para n elementos. Em algum momento, tirando 1 de n, ele valerá 1, o caso básico, assim conseguimos chegar a uma fórmula fechada, 2^n.
       • Conjecturar
       • Verificação
         • A verificação da conjectura será feito pelo método de indução
           • Passo básico
           • Hipótese de indução
           • Passo indutivo
             • Se estamos supondo que 2^k é verdadeiro, queremos provar que para todos os demais k's ele continuará verdaeiro, assim fazemos Q(k+1)=2^k+1. Partindo do lado esquerdo da fórmula, podemos dizer que Q(k+1) é igual a 2.Q(n-1). Substituindo o n por k e fazendo os calculos, chegamos em 2.Q(k). Como estamos supondo como verdadeiro que Q(k)=2^k, fazemos essa substituição, chegando em 2^k+1.
   • Fórmula fechada para relação linear, de primeira ordem com coeficientes constantes
     • Dada essa relação recursiva:
       • Sua fórmula fechada será:
     • Exemplo:
       • • • Neste exemplo, pegamos a fórmula e substituimos os valores por aqueles dados na relação recursiva.
   • Fórmula fechada para relação linear, homogênea, de segunda ordem e coeficientes constantes

3. Tipos de relação recursiva

   • Linear
     • S(n) é linar se os valores anteriores de S que aparecem na fórmula estão na primeira potência. Ex: S(n = f1(n).S(n-1) + f2(n).S(n-2) + ... + fk(n).S(n-k)+g(n)
     • S(n) é linear com os coeficientes constantes, se todos os fi são constantes. S(n) = c1.S(n-1) + c2.S(n-2) + ...
     • S(n) é linear, com os coeficientes constantes e de primeira ordem se dependem apenas do termo n-1. S(n) = c.S(n-1) + g(n)
     • S(n) é linear, com os coeficientes contantes, de primeira ordem e homogênia se g(n) = 0. S(n)= c.S(n-1)

Bilder und Dateien der Mindmap