Definição recorrente: é uma definição em que o item definido aparece na própria definição. Em computador e matemática, isso é comum para definir sequências, conjuntos de cadeias e operações. Um passo base (ou condição inicial) é necessário, junto com uma regra que descreve como obter termos subsequentes a partir de valores anteriores.
Exemplo simples de sequência recursiva:
Observação: evidenciamos o passo base (T1) e a regra para obter T_{n+1} a partir de T_n.
Sequências famosas — sequência de Fibonacci: F1 = 1, F2 = 1 e, para n ≥ 3, F_n = F_{n-1} + F_{n-2}. Os cinco primeiros valores são: 1, 1, 2, 3, 5.
Aplicação da indução para propriedades envolvendo sequências recursivas: por exemplo, provar por indução que a relação de recorrência F_n = F_{n-1} + F_{n-2} vale para todos os n ≥ 3.
Para demonstrar propriedades de uma sequência recursiva, com frequência usamos indução (simples ou forte). Um esboço típico de indução:
Exemplo de uso: provar por indução que F_n ≥ 1 para todo n ≥ 1 (válido para Fibonacci).
Observação: em indução forte, assume-se que a propriedade vale para todos r entre 1 e k, e usa-se essa hipótese para provar para k+1.
Uma sequência pode ser entendida como uma lista ordenada de objetos. Em linguagens formais, cadeias (strings) são sequências de símbolos. Podemos definir conjuntos de cadeias recorrendo a regras de formação.
Exemplo simples de construção de cadeias recorrentes (linguagens formais):
Assim, podemos gerar várias cadeias com regras recursivas de formação.
Podemos também definir operações com regras recursivas:
Essas definições mostram como construir novos objetos a partir de regras simples, recursivamente.
Algoritmos recursivos resolvem um problema através de chamadas recursivas até atingir o caso base. Benefícios: código muitas vezes mais claro e direto; desvantagens: overhead de chamadas de função (pilha) e, às vezes, maior consumo de memória.
Exemplo: soma de 1 até m (soma(1..m))
Quando a recursão é profunda, pode haver estouro de pilha; porém, para alguns problemas, a recursão resulta em código mais legível e mais fácil de manter.
Nem todo problema é naturalmente resolvido com recursão simples. Em alguns casos, soluções iterativas são mais eficientes em tempo e memória; em outros, a recursão oferece uma solução mais clara e elegante. O uso de recursão delicadamente pode envolver recursão de cauda (tail recursion) para otimizar, caso o ambiente de execução suporte.
Observação prática: a escolha entre recursão e iteração depende do problema, da clareza desejada e das limitações de memória do ambiente.
Resposta correta: C) É uma definição na qual o item definido aparece na definição (regra recursiva).
Observação: esse é o cerne de uma definição recursiva — há uma base + uma regra que utiliza o próprio objeto definido.
Resposta correta: A) F_n = F_{n-1} + F_{n-2}.
Explicação: pela definição clássica, cada termo é a soma dos dois anteriores, com F1 = F2 = 1.
Resposta correta: B) Assuma que a propriedade vale para todos r entre 1 e k; prove para k+1.
Observação: indução forte utiliza a hipótese de que a propriedade vale para todo r ≤ k, e não apenas para k.
Resposta correta: B) O(n log n).
Justificativa: para T(n) = 2T(n/2) + n, pelo Teorema Mestre, T(n) = Θ(n log n).
Olá, alunas e alunos do curso de Fundamentos Matemáticos para a Computação.
Nesta videoaula eu vou falar de definições recorrentes.
Eu vou começar a estabelecendo o conceito de definições recorrentes e mostrando como elas são usadas para definições conjuntos e operações natemáticas.
Além disso, vamos ver se eu uso em algoritmos, nos algoritmos recorcivos.
Uma definição recorrente, o item definido faz parte da definição.
Você vai encontrar esse tipo de definição sendo chamada por definição por recorrencia ou definição recorciva.
Nós vimos isso quando estamos abordando a inferência em uma linguagem próxima ao Prologue, onde nós tínhamos uma regra definida em função dela mesmo, passando a ideia de recorrencia.
Bom, numa sequência, a sequência é uma lista de objetos que são numerados em determinada ordem.
Ou seja, você consegue estabelecer uma ordem entre esses elementos.
Quando temos sequência, nós conseguimos definir ela através de uma recorrencia identificando o primeiro ou alguns dos valores iniciais e depois estabelecendo uma fórmula para definir valores subsequentes em função de valores anteriores.
Como é o caso que, desse exemplo, onde o valor inicial tem um igual a um e depois os demandes que estão em função de uma função anterior adicionando três.
Como isso vai funcionar? Estabeleço, por exemplo, se eu quero gerar os cinco primeiros valores de um e igual a um, já o T₂ vai ser obtido em função de T₁ e eu tenho quatro.
O T₃ vai ser obtido em função do resultado de T₂ e o obtém o sete.
Da mesma forma, o T₃, ele vai ser obtido em função do T₃ e assim sucessivamente.
No caso, aqui até chegar ao T₃, também o obtido em função do T₃.
E aí, eu tenho a sequência dos cinco primeiros valores.
Bom, nas sequências, nós temos a famosa sequência de fibonate.
Ela foi introduzida no século 13 por Leonardo Fibonate, que era um filho de como é se antes e identificou esse padrão que é um padrão para a sequência de valores encontrado na natureza.
Nós podemos, por exemplo, inferir diferentes propriedades a partir da sequência de fibonate, como a regra de ouro, a gente tem que a janeificação de das árvores segue em um padrão da sequência de fibonate.
E outras coisas interessantes como a reprodução dos coelhos, muito famosa, baseada na sequência de fibonate.
Bom, em um caso que essa sequência, como que ela tem de curioso? Você tem dois valores iniciais e você obtém o próximo valor como uma soma dos anteriores.
Então, nesse contexto, se eu quero que eu coco-f3, eu vou cocular a partir de f1 e f2.
Se eu quero que eu coco-f4 ou de tenho a partir de f2 e f3.
E se eu quero que eu coco-f5, eu tenho a partir de f3, mas f4.
Então, é interessante que certas dispersões, como eu citei da janeificação das árvores, elas segue em um padrão desse tipo, na natureza.
Bom, no caso aqui de nosso interesse, nós vamos fazer trabalhar essa lógica da sequência de recursos, por exemplo, para provar que uma sequência de fibonate obedece também a essa regra.
Eu tenho fn4, sendo obtido em função de três vezes fn, mais dois menos fn.
Bom, como é que eu vou provar isso? Eu posso provar por indução e, nesse caso, eu começo pelo passum.
Observem que nós temos duas situações aqui.
Eu quero provar essa fórmula e eu sei que ela segue a sequência de fibonate.
Isso é o fato.
Então, eu sei que, para a n igual, vamos verificar essa fórmula.
Essa fórmula que me leva num f5, valendo 5.
Ok? 5 é o valor auditido para f5 numa sequência de fibonate.
Para a n igual a 2, eu vou ter f2 mais 4, eu vou ter 3 vezes f4 menos f2.
O que me leva, então, é f6.
O valor de f6 na sequência de fibonate é 8.
E eu vejo que ele bate com o valor da fórmula 3 vezes 3 menos 1.
Eu vou ter 8.
Ok? Verifiquei isso para 1, 2.
Com a hora, eu vou supor por indução que vale para n igual a 4.
Bom, nesse contexto, observem que eu vou usar hipótese de indução para assumir que a fórmula é verdadeira, até n igual a 4, por indução forte, assumindo que os valores intermediários seguem essa fórmula também.
E agora, eu vou provar para n igual a k1.
Para provar para n, na hipórica mais 1, eu quero provar, então, essa fórmula, considerando fdk mais 5 igual a 3 vezes fk, mas 3, minhas fk mais 1.
Então, substituca mais 1 no lugar do n.
Bom, para fazer essa demonstração, novamente, eu vou usar hipótese de indução, vou lembrar do fato de que f é uma sequência de fibonate e vou provar agora para n igual a k1.
Bom, para eu começar essa demonstração, como te costumo, eu vou sair aqui do meu lado, esquiar para chegar ao lado direito, de que mangue.
Bom, fdk mais 5, eu assumo, então, uma hipótese valida segue a sequência de fibonate, então, é dado a infusota soma dos anteriores.
Nesse contexto, eu sei que fk mais 4, pela hipótese de indução segue também essa regra.
Perfeito.
Só que o fk mais 3 também segue essa regra, porque o f, se ela vale até o k mais 4, ela vai valer para k mais 3.
Então, eu posso substituir o k mais 3 aqui.
Lembre-se, pela indução forte, vale para todo r entre 1 e 1.
Então, nesse caso, eu tenho a propriedade valendo para o k mais 3 e k mais 4.
Eu posso substituir por hipótese de indução.
E agora, o que vai acontecer? Dessa maneira, eu tenho 3 fk mais 1 com 3 fk mais 2, fk menos 1, menos né, e menos fk aqui, juntando, colocando 3 em evidência, o que eu vou ter? Agora, eu posso aplicar que bonate.
Eu sei que fk mais 1 mais fk mais 2, me leva a fk mais 3.
Da mesma maneira que colocando o sinal negativo em evidência, fk menos 1 mais fk, me leva a fk mais 1, o que me faz chegar ao que eu queria demonstrar aqui do lado direito.
Rept? Bom, nessa linha, eu poderia, por exemplo, ter baseado toda a linha de demonstração não na indução forte.
Eu poderia ter usado simplesmente fibonate à relação de fibonate.
Nesse caso, o que eu faço? Fn mais 4 é a soma dos anteriores.
Perfeito? Eu parte o direto da expressão.
Não estou usando a indução.
Fn mais 3, fn mais 2, mais fn1.
Perfeito? Da mesma forma, eu tenho que fn mais 1, fn menos 1, mas fn.
Perfeito? Eu estou expandindo usando fibonate.
Só que reparo, é uma relação de igualdade, ou seja, se fn mais 1 é igual a fn menos 1 mais fn, eu tenho pura equivalência, que eu posso simplesmente isolar o fn menos 1 passando fn para cá.
E por que eu fiz isso? Porque eu preciso chegar em 3 fn mais 2.
E eu só tenho 2 fn mais 2 aqui.
Então, quando eu fizer isso, o que vai acontecer? Eu vou ter uma combinação possível de fn mais 1 com fn.
Então, eu substituo aqui o fn menos 1 por esse termo, da sequência de fibonate.
E dessa forma, eu consigo chegar aqui em fn mais 2.
Agora, tenho 3 fn mais 2, menos o meu fn, que já tinha parecido, que aparece aqui também dessa substituição.
E dessa forma, eu chego na relação sempre a usar demonstração por ilusão, fazendo uma demonstração direta, partindo da hipótese, de que é da hipótese, de que f é uma obedeção na sequência de fibonate.
Quando a gente pensa na representação por reconrencia usando conjuntos, nós temos que ter nente que um conjunto de objetos que é uma coleção na qual não há nenhuma ordem imposta nos valores.
Então, alguns conjuntos, a gente vai ver que é possível você estabelecer uma definição recosiva para representar os elementos daquele conjunto.
Por exemplo, é um exemplo bem simples dentro do contexto que a gente já viu.
Qualquer letra de proposição é uma forma bem formulada.
Por exemplo, a dc, se eu estou usando para estabelecer uma proposição, é uma forma bem formulada.
Se pegue são fórmulas bem formuladas, então se duas letras são uma forma bem formulada, eu posso combinar-las desse jeito.
Isso aqui repare que o resultado disso aqui é uma FBF.
Então, se eu pegar duas FBF e combinar também com esses operadores aqui, eu gera outra fórmula bem formulada.
Reparou, eu tenho uma máquina de gerar fórmulas bem formuladas.
Vamos ver se é detalhe.
A b c são fórmulas bem formuladas pela regra única.
Eu passo baixo, tenho uma fórmula bem formulada.
Nesse caso, aqui com um único elemento, a b c.
Então, nesse caso, pela regra 2, eu posso combinar a e b.
E posso combinar, eu posso gerar a e b.
E posso gerar aplicando a regra 2, o c negado.
Agora, eu tenho uma FBF aqui, outra FBF aqui, que eu posso novamente aplicar o passo 2, recorcivelmente.
Nesse caso, o que eu vou fazer? Eu vou ter.
Eu estou aplicando com a implicação, jogando a e b com antecedente e o c negado como um consequente.
E assim, eu vou gerando fórmulas.
Se eu pegar agora, essa FBF aqui, como um todo, no único elemento.
E eu quiser negar ela, como eu posso fazer aqui, p negado, eu apliquei com o meu pé era esse termo, essa FBF.
E aí, eu tenho uma negação dela.
Então, dessa forma, com a regra 2, eu vou criando elementos desse conjunto de fórmulas bem formuladas.
Outra definição recorrente para a conjunta suponho seguinte.
Eu tenho uma cadeia, lâmbida, representa uma cadeia vazia.
Cadê esse em cinco? Pertencente ao conjunto a estreia.
Um único elemento, um único elemento qualquer dia, vai pertencer esse conjunto a estreia.
Bom, se x e pessoal são cadeias em estreia, então, com a cadenação, então, aqui eu tenho um operador para a geração x e pessoal, também vai pertencer a estreia.
Então, eu tenho aqui três regrinhas, a cadeia vazia pertence, um único elemento qualquer dia, a pertence a estreia, e a concatenação de elementos de a, já também vão pertencer a estreia.
Então, suponho seguinte, dá uma cadeia x.
Eu vou ter seu concateno com a cadeia vazia.
Eu vou ter sempre o próprio x, não importa a ordem que eu faço essa concatenação.
Se eu lembro de x por uma cadeia, por exemplo, binara, um zero, um, um, e y foram zero, zero, um.
Eu posso, agora, combinar-lo x y gerando essa cadeia y x, ou, por exemplo, fazer uma combinação agora desse termo com esse cocadeia, desse termo com x e com a cadeia vazia, gerando isso aqui.
Lembre-se que a cadeia vazia gera o próprio termo.
Certo? Bom, dessa forma, então, eu tenho uma maquininha para gerar cadeias de valor hoje.
Em termos de operações, mas também podemos definir operações usando definição recorrente, definição recursiva.
Considera definição recorrente abaixo para operação de potência.
Então, observe que, para eu definir potência, eu tenho passo básico, que nesse caso, considerando n inteiro não negativo, seria o n valendo zero.
Então, eu vou ter a elevado a zero igual a um.
Bom, para definir o a elevado a n, que eu faço, ele é o a vezes o a elevado a n menos um.
E assim, recursivamente, eu vou fazer o caldo.
Vamos pensar nisso, agora, se eu quero calcular a 2 elevado a 3.
Eu vou começar pela regra 2.
Eu vou ter 2 vezes 2 elevado a 3 menos um, que é 2 vezes 2².
Que vai me levar a regra 2 de novo, que é 2 vezes 2 elevado a 2 menos um, que é 2 a primeira.
Que vai me levar a regra de novo, que vai fazer com que eu calha em 2 elevado a zero.
E aí, eu cheguei no meu passo básico, no passo 1, na regra 1.
Quando eu chego na regra 1, eu tenho um resultado definido, que é o que? Que vai ser 2 elevado a zero, a a elevado a zero vale 1.
E eu retorno esse valor.
Quando eu retorno esse valor, eu posso operar aqui no 2 elevado a 1, que estava esperando o resultado.
E aí, eu tenho um 2.
E agora, eu posso operar no 2², que vai me retornar 4.
E assim, eu chego no 2 ao cubo 8.
Um outro exemplo de operação é a multiplicação aqui.
Vamos, acabei entregando o ouro aqui.
É, na verdade, o que essa operação recursiva vai fazer? Eu passo base em em e a regra seria, para um valor em de entrada, eu vou fazer em vezes em menos um.
Mas, em, o que significa isso? Então, se eu tenho em igual 4, eu vou estar fazendo em recebendo a relação recurseira.
Eu volto para o passo 2, só que agora, com um argumento em, valendo 3 e adiciono em.
Novamente, aqui, para m3, eu estou no passo 2, eu vou aplicar essa regra, porque o m é maior, eu igual a 2.
E daí, peguei o fotei.
2.
Mais m, não esqueçam do mais m aqui, que acumula com um outro m, que estava esperando aqui do m3.
Quando eu vou para o m2, ainda é igual a 2.
Então, eu vou na regra 2, subtraiu 1 e acrescenta, mais 1 m.
Agora, que eu cheguei em m1, eu caio no passo 1, na regra 1.
O que isso significa que agora eu tenho um valor de retorno, que vale m, que vai somar com os outros m's.
Então, o que eu estou fazendo aqui? Eu estou multiplicando o m 4 vezes.
Então, essa minu operação, essa definição recorrente, é uma definição para a multiplicação de dois inteiros positivos, m e m.
Onde eu criei uma função repulsiva de m em função de m.
Bom, agora a gente vai ver um uso das definições recorrentes em algoritmos.
No caso, nós somos introduzidos inicialmente algoritmos iterativos, ou seja, desiteram, eles executam a passo a passo a as operações e nesse caso, o que dentro do enlaço do tipo para.
O que isso significa? Significa que, por exemplo, eu vou cocorrar soma de um inteiro m com m igual a 5.
Quando eu começo, eu tenho m igual a 0 na linha 1, e aí eu interro para igual a 1.
Para igual a 1, eu vou ter s e valendo 1.
Perfeito, na linha 3.
Retorno para o meu aço, comia agora, valendo 2.
E na linha 3, eu cocorro 1, mais 2, 3.
Retorno para a linha 2, agora comia e valendo 3.
S igual a 3, mais 3, 6.
Eu estou pegando um resultado de s agora e eu disse o não anuí.
Na linha 2, agora, aí passa a valer 4.
Vou ter s igual ao resultado anterior, mais ui, que leva 10.
E, por último, eu vou ter i, valendo 5.
Com esse, agora, pegando o resultado anterior, 10, mais 5, igual a 15.
Quando eu interro novamente, o meu i já estoura o limite do n.
E nesse caso, eu saio e na linha 4 eu retorno s, valendo 15.
Esse é um algoritmo interativo.
Agora, a gente vai fazer um algoritmo recursivo.
Como funciona? Observe, então, que nós temos um passo base nessa relação recursiva, que é o quê? Ele vai, sinn for menor ou igual a 1, ele vai retornar o n.
Sinão, ele vai retornar a soma de n, menos 1, mais n.
Então, o que vai acontecer nesse caso? Eu começo com soma valendo 5.
Bom, n não é menor ou igual 1.
Então, eu vou pegar no senão soma 4, mais 5.
Vou agora, para o soma 4, executo.
Então, eu faço uma outra chamada a esse código, a essa função soma.
Essa função soma faz uma chamada a função soma 3.
E adicione, vai retornar o resultado de soma 3, mais 4.
Então, me serve, estou deixando códigos em sustenços, esperando o resultado.
Isso significa o quê? Eu entrei de novo nesse senão, já que o valor aqui é 3.
Então, agora, o que vai acontecer? Para soma 3, na chamada de soma 3, eu avaliu o que ele não é menor que 1.
Eu retorno soma 2, mais 3.
Fácil, uma outra chamada.
Então, repare que eu vou acumulando, empilhando chamadas de código até chegar no passo mais e quando ele retorna o n, que vale 1.
Nesse caso, com o n, valendo 1, eu começo a fechar.
Eu encerro essa caixinha que estava no início da pilha, a mais assim, eu encerro ela retornando 1.
Esse 1 vem para cá, que vai somar com 2.
Do código soma 2, que estava em suspensão.
Que agora retornar 3, pro código soma 3, que estava esperando o resultado de soma 2.
E assim, sucessivamente, até o retornar o resultado de soma 5, que vai ser 15.
A vantagem e desmontagens da repulsão, a repulsão é uma sobrecarga, que é o que se chama de overhead, com as com essas chamadas de função que nós limpos.
Gerando um gasto de tempo de processamento e espaço de memória, que você fica acumulando essas pilhas aqui.
Certo? Além disso, você tem uma cópia da função variáveis da função sendo criada, que é assim, que é um assunto menor.
Logo, a interação tem de ser mais rápida por não fazer repetida e chamadas de função.
Só que nem todo problema, você vai conseguir propor um algoritmo de uma maneira trivial usando um algoritmo iterativo.
Na recorção, nós temos estruturas condicionais, na interação de estruturas de repetição.
Na repetição, a repetição no algoritmo irreconcível é implície, da interação, por conta da estrutura, ela é bem explísta.
Você vai ter um caso base para estabelecer a parada da repulsão, assim como você tem um critério de parada, um emite para a susto de repetição, uma condição para a susto de repetição.
Ele tem de acima de lento irreconcivo e terativo mais rápido.
Porém, a repulsão, aí eu estava dizendo, muitas vezes é uma solução mais simples com o problema, que às vezes a solução iterativa vai ser muito complexa.
Além disso, você perceber o que o código irreconcível é muito mais limpo.
Ele é muito mais fácil de você enxergar o que ele faz e manter.
Ele fazia uma nutrição.
Já o iterativo, principalmente quando ele oferece uma solução complexa, ele tem uma nutrição mais difícil.
Bom, então esse foi o assunto da audi, hoje eu recomendo a leitura da sessão 3.
1 do nosso material base, e vejo vocês na próxima aula.