Recursão é quando uma função se chama a si mesma para resolver um problema, dividindo-o em subproblemas menores. O padrão clássico para problemas recursivos é ter: - uma condição base (caso simples que pode ser resolvido diretamente), e - um passo recursivo (a função chama a si mesma com argumentos menores).
Exemplo prático: sequência de Fibonacci
Definições usadas no conteúdo:
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) para n >= 2
Construção recursiva típica (em pseudocódigo/python):
def fib_rec(n):
if n < 2:
return n
return fib_rec(n-1) + fib_rec(n-2)Exemplo de cálculo passo a passo para F(4):
Observação: a implementação recursiva simples pode ser ineficiente para N maiores devido à repetição de subproblemas.
Comparando recursão e iteração: - Recursão usa a pilha de chamadas. Cada chamada empilha informações de retorno e parâmetros. Em alguns problemas, como fibonate, a solução recursiva pura realiza muitas chamadas repetidas e pode ter crescimento exponencial no tempo de execução. - Iteração (loops) evita chamadas recursivas, usando estrutura de repetição (for/while). Em muitos casos é mais rápida pois não envolve push/pop intensivo na pilha de chamadas.
Resumo prático:
Exemplos práticos de comparação de desempenho (parcial, conforme o conteúdo):
Observação adicional: a versão iterativa tem crescimento de tempo muito mais estável em função de N, enquanto a recursiva cresce de forma exponencial.
Memoização é uma técnica de otimização que armazena os resultados de chamadas custosas de uma função e retorna o valor já calculado quando a função é chamada com os mesmos argumentos. Em problemas como Fibonacci, isso evita recalcular F(k) várias vezes.
Como funciona (visão conceitual em Python):
memo = {}
def fib_memo(n):
if n < 2:
return n
if n in memo:
return memo[n]
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n]Impactos práticos:
Exemplos de métrica de desempenho com memoização (conforme o conteúdo):
Observação: mesmo usando recursão, memoização reduz drasticamente o tempo, tornando a solução mais prática para N maiores.
Resultados de tempo de execução para diferentes abordagens (Fibonacci):
Implemente usando recursão (com memoização opcional) em Python:
Obs.: As soluções com memoização podem ser aplicadas para otimizar recursões, especialmente se os subproblemas forem repetidos.
Qual das assertivas abaixo descreve corretamente o propósito da memoização?
Resposta correta: B) Memoização armazena resultados para evitar recomputar subproblemas repetidos, reduzindo o tempo de execução.
Observação: a memoização acelera recursões que geram muitas subChamadas repetidas, ao custo de consumir memória para armazenar os resultados.
Qual é a principal desvantagem da implementação recursiva simples para o cálculo da sequência de Fibonacci?
Resposta correta: B) A principal desvantagem da recursão para Fibonacci é o tempo de execução exponencial devido à recomputação de subproblemas.
Comentário: sem memoização, muitas chamadas repetem os mesmos cálculos, levando a crecimiento exponencial do tempo.
Como a memoização afeta a complexidade de tempo e espaço da solução recursiva para o problema de Fibonacci?
Resposta correta: A) A memoização reduz o tempo de execução, mas consome memória extra; para Fibonacci, a solução costuma ter tempo O(N) com memória O(N).
Observação: o ganho de tempo depende da duplicação de subproblemas; memoização evita essa duplicação.
Considere a implementação recursiva ingênua de Fibonacci e a mesma implementação com memoização. Assinale a alternativa que apresenta corretamente as ordens de crescimento de tempo (e, quando aplicável, de memória) de cada abordagem.
Resposta correta: A) Recursiva: O(2^N) e Memoização: O(N) de tempo (com memória O(N)).
Justificativa: para fibonnaci simples sem memoização, o número de chamadas cresce exponencialmente; com memoização, cada F(k) é calculado uma vez, resultando em tempo linear em N, com uso adicional de memória.
Música Olá pessoal, como vocês estão? Estamos de volta aqui na nossa Visualas da Disciplina Alvorítimos e programação de computadores 2.
Essa é a nossa segunda a o videoaula sobre o tema Recursão, quem ainda não assistiu a videoaula anterior ou sugiro que vocês assistam aquela videoaula primeiro antes de assistir esta.
E hoje a gente vai ver um pouquinho mais sobre Recursão, mas especificamente a gente vai ver uma comparação entre funções recorcivas e funções interativas.
E também uma técnica para tentar melhorar o desempenho de funções recorcivas em casos onde elas devem ser empregadas e mais alguns outros exercícios também que eu vou deixar para vocês fazerem.
Bom, então a gente vai então, a gente viu na aula passada, eu deixei para vocês como exercícios e implementar a função recorciva para encontrar o NES-mutemo da sequência de Fibonate.
Então só relembrando um pouquinho, Fibonate é definido como o F de zero é igual a zero, o F de um é igual a um e o F de N para N maior do que um é definido como o F de N menos um mais o F de N menos dois.
Então para o termo de N de zero, o valor é zero.
Para o termo de N de C1, o valor é um para o N de C2, R1 para o N3 é dois, N4 é três e assim por diante, tá? Bom, e no caso da função recorciva é essa daqui, que está lá do esquerdo.
Então para N, menor do que dois, o resultado é o próprio N, tá? Então para N, menor do que dois, seria esses casos que estão aqui.
Então o valor, o resultado é o próprio N, o zero é zero e um é zero.
Mas o contrário, quer dizer, o N for maior do que maior ou igual a dois, aí eu tenho essa fórmula que é exatamente as chamadas recorcivas à própria função.
Então vai ser o retorno da função para N menos um, mas o a função para N menos dois.
Muito bem, aí eu tenho aqui desse lado direito, a mesma a função para calcular o N mesmo termo, mas na sua versão iterativa.
Então o reparem que eu não faço nenhuma chamada recorciva e eu consigo calcular também o N mesmo termo de fórmula atir, sem usar a recorção.
Reparem que esse algoritmo, ele tem muito mais linhas de código, acaba sendo até um pouco mais complicado de entender.
Então por exemplo, isso daqui já é um indício, de que funções recorcivas podem ser bastante úteis, em casos onde você tem problemas que dependem da resolução de subproblemas dele mesmo.
Mas aí eu posso perguntar para vocês, quem é melhor a versão recorciva ou a versão iterativa.
Nessa versão iterativa, apesar de eu ter muito mais linhas de código, essa função vai executar muito mais rápido do que a versão recorciva.
Porque isso, porque o que acontece é que, nesse processo de chamar a própria função, é feito um empilhamento do endereço de retorno e também das variáveis e dos parâmetros que estão envolvidos aí naquela execução.
Então esse processo de empilhar esses dados de armazenares a eles e depois desenpilar o que faz com que as funções secorcivas fiquem bem lentes.
E além disso, pessoal, no caso deste problema e de fibronate, a gente tem outros problemas também.
Um deles é que você vai tá calculando várias vezes o resultado para o mesmo valor de N.
Então repare que eu estou chamando para N menos 1, e aqui para N menos 2, mas no caso, quando você chama para N menos 1, ele vai chamar naquela dentro, naquela chamada, ele vai executar de novo para N menos 1, que equivale ao N menos 2.
Então você tá duplicando os processamentos, as chamadas para os mesmos valores de N.
Então isso também vai gerar uma latência muito maior aí para chegar no resultado final.
Então olha só, aqui eu tenho uma tabelinha comparando a versão recursiva com a versão iterativa.
Essa tabela aqui foi definida aqui por esses autores em 1996.
Repare que para determinados valores, quando você aumenta o valor de N, o tempo necessário para calcular o fatorial de N, acaba aumentando considerávelmente para a versão recursiva, que é essa primeira linha.
E na versão iterativa, apesar de você aumentar um pouco, isso acaba, esse aumento é muito mais comportado.
Eu tenho uma versão aqui também, dessa tabelinha que a gente pode fazer no meu programa.
Vamos dar uma olhada aqui na prática como se comporta essas duas versões aí da função para calcular o fatorial de Fibonacci.
Então olha aqui, eu tenho a implementação já do Fibonacci Recursivo, que é isso que está aqui.
E o Fibonacci iterativo, que é isso que está aqui desse lá.
Então é a mesma implementação que está no Moses Lides.
E o que eu estou fazendo aqui embaixo? Eu estou chamando o Fibonacci Recursivo para um valor de N, e o Fibonacci iterativo também para o mesmo valor de N.
Só que antes da chamada de cada uma dessas funções, eu armazendo o tempo atual do meu sistema.
E depois, quando saio da função, eu pego de novo aquele tempo do meu sistema e subtraio do tempo inicial antes de chamar a função.
Então, no caso, eu vou ter aqui como resultado dessa subtração, um tempo em segundos do tanto tempo que levou para executar aquela função que está ali no meio.
E a mesma coisa aqui para a versão interativa, para a versão interativa, antes eu pego o tempo inicial, e depois eu pego o tempo final e subtraio do inicial.
É certo? Então, eu vou ver o que está acontecendo.
Eu vou colocar um N menor aqui primeiro, colocar igual a 10 por enquanto.
Para N igual a 10, o resultado é 55, Reparem que a versão recursiva levou 0,0039 segundos.
E a versão interativa levou 5,29 vezes 10 elevada a menos 5.
Então, esse negócio aqui é notação científica.
Então, é vezes 10 elevada a menos 5, que é um valor muito mais baixo do que a recursiva.
Vamos aumentar um pouco mais esse valor de N e colocar 20.
Então, o Fibonacci do Vigésimo termo é 6.
765.
A versão recursiva levou 0,001 segundos, e a versão interativa 3,79 vezes 10 elevado a menos 5.
Então, é muito mais rápido.
Vamos aumentar mais um pouco, eu vou colocar 30 agora.
Então, a recursiva já passou de um segundo, 1,31 segundos para executar.
E a iterativa 0,001 segundo.
Vamos aumentar mais um pouco, 35.
Aqui ele vai demorar um pouco mais.
Então, aqui, a versão recursiva levou 18 segundos.
18 segundos e meio para encontrar o trigésimo 5 elemento de a sequência.
E a versão interativa ainda estava lá no 3,1 coisa vezes 10 a menos 5.
Então, quer dizer, a versão interativa é muito mais rápida.
Ele é muito mais comportado o crescimento em função de N.
Muito bem.
Então, uma técnica pessoal que pode ser utilizada para poder minimizar esse tipo de problema, é o que a gente chama de memoização.
Não é porque a função recursiva é mais lenta, que a gente não pode utilizar ela.
A gente pode utilizar.
E em alguns casos é possível fazer algumas otimizações no nosso código para permitir que essa latência seja minimizada também.
E uma dessas técnicas é a memoização.
O que significa a memoização? Então, é uma técnica que armazena os resultados e chamadas de funções custosas e que retorno a valor armazenado quando a função é chamada novamente.
Então, por exemplo, para calcular o inésimo termo de fibronate, eu falei para vocês que a função recursiva vai chamar várias vezes a função para o mesmo valor de N.
Então, o que é possível a gente fazer? A gente vai chamar para um determinado valor de N.
Vamos gerar o resultado.
E esse resultado, a gente vai armazenado uma tabela, uma estrutura do Python.
E quando forfeito uma nova chamada com esse mesmo valor de N, a em vez de a gente executar a função, a gente já retorna aquele valor que foi previamente armazenado.
Olha um exemplo aqui do fatorial.
Então, por exemplo, aqui eu estou usando essa estrutura dict, que é adicionado.
Essa estrutura dict, pessoal, ela vai criar como se fosse um vetor, onde os elementos que a gente vai colocar aqui, é o que a gente chama de chaves.
De chave.
Então, cada quadradinho desse é uma chave única.
E cada quadradinho desse aponta para um valor, alguma coisa aqui.
A gente está armazenando lá na nossa memória.
Então, por exemplo, o N, é esse dict, o que eu faço? Eu faço N de N, N de N, recebe alguma coisa.
Então, esse N que está aqui é a minha chave.
E esse é alguma coisa que está recebendo, que eu estou atribuindo ao N de aquela chave.
Eu chamo isso de valor, algo que você vai armazenar.
Então, olha só.
Eu tenho a definição da função FAT, se o N for zero retorno um, eu tenho essa condição aqui.
Se esse g et de N, N g et, quer dizer que eu vou verificar se aquela chave já foi utilizada no meu adicionário.
Então, supondo que lá na com a chave N, você vai ter acesso àquele, aquela posição da sua tabela, que seria essa daqui.
Se você fizer N ponto g et, N, isso te retornar noni, significa que essa posição ainda não foi utilizada, ela está vazia aqui.
E nesse caso, eu vou entrar nessa parte aqui, vou calcular o FAT, de N, e vou armazenar na tabela, na posição N de N, e eu retorno esse valor aqui para fora.
Supondo que o chame, o g et de N, aqui em cima, isso daqui te dá um valor que é diferente de noni, significa que o FAT, de N já foi calcular, e aí, eu só retornar esse resultado aqui para fora.
Aqui, eu tenho um exemplo de uso de memorização para o Enésimo Thermo da Sequência de Fibonade.
É a mesma ideia, tá pessoal? Eu tenho a criação aqui do meu dicionário.
Se o meu N é menor do que 2, é a minha condição base, já vou retornar o valor de N.
Aqui, eu estou verificando, se o Enésimo Thermo já foi calculado, está por meio de M.
g et N.
Se isso daqui não te retornar um valor que é diferente de noni, quer dizer que está preenchida aquela posição, e isso significa que já foi calculado o Enésimo Thermo.
Então, é só eu retornar o valor lá da tabela.
Caso contrário, eu vou, aí sim, calcular o Enésimo Thermo por meio da função recursiva normal, só que, ao invés de eu retornar isso direto, eu primeiro armazeno na tabela e depois eu retorno esse valor da tabela.
Por que? Porque essa tabela vai ser usada em futuras chamadas a esta função.
Então, aqui pessoal, eu tenho também a implementação desta versão de conuso, de memoisação, eu vou colocar ela aqui junto com as outras funções, e eu vou colocar aqui também a medida para esse, para essa chamada, com memoisação.
Fime de memoisação.
Memoisseixam.
Então, ele vai me retornar que o tempo, que foi feita o cálculo do Enésimo Thermo, com uma versão otimizada.
Vou diminuir um pouquinho aqui o En primeiro.
Então, olha só, enquanto que a recursiva levou 0,01 segundos, a iterativa levou 4 vezes 10 a menos 5, e a memoisação levou 7,6 vezes 10 a menos 5.
Reparem que a versão de memoisação ainda está usando a função recursiva, só que o tempo dela é bem menor do que a versão recursiva pura, sem nenhum tipo de otimização.
Vamos aumentar um pouquinho mais.
Vou colocar 30 agora.
Então, a versão recursiva levou 3,9 segundos, e a iterativa levou 8,7 vezes 10 a menos 5 segundos, e a conmemoisação levou 0,001 segundos.
Então, ainda, apesar de ser um pouco mais lento do que a iterativa, quer dizer, bem mais lento do que a iterativa, ainda assim, ela é muito mais comportada do que a recursiva.
Então, é uma técnica de otimização, aí que é muito eficiente, em caso, onde é necessário realmente utilizar funções recursivas, mas você quer ainda presar pela velocidade, pela eficiência do seu código.
Bom, então, para finalizar essa video-al, eu vou deixar como exercício, esses dois problemas para vocês tentarem fazer a versão recursiva, e com a memoização, se vocês conseguirem.
Então, primeiro, o exercício é dada uma lista L com N números, implementar uma função recursiva que retorna o maior elemento deste conjunto.
E o segundo é dada uma lista L de N números, implementar uma função recursiva que retorna a soma de todos os elementos deste conjunto.
Então, essa foi a nossa videoaula sobre recursão.
A gente finalizou mais uma assunta aí da disciplina, e a gente vai se ver agora na próxima semana com mais um assunto novo, envolvendo um pouco mais a parte de estruturas de dados.
Então, a gente se vê lá, e até mais.
Valeu, gente!