Definição de função: Função é um bloco de código que recebe entradas (parâmetros) e retorna uma saída. Em recursão, a função pode chamar a si mesma para resolver um problema menor.
O que é recursão: Recursão ocorre quando uma função se define em termos da própria função, direta ou indiretamente, ou seja, a função chama a si mesma.
Exemplo simples (imprimir elementos de uma lista): Considerar uma lista L = [1, 2, 3] e imprimir cada elemento usando um índice i que começa em 0. Caso i < tamanho(L), imprime L[i] e faz uma chamada recursiva com i+1.
Como funciona a recursão (pilha de chamadas): a cada chamada recursiva, o sistema empilha o estado atual (variáveis e endereço de retorno). Quando a chamada recursiva atinge a condição de término, as chamadas vão retornando na ordem inversa, desfazendo a pilha até chegar ao chamador original.
Quando usar recursão: use recursão quando o problema natural pode ser dividido em subproblemas parecidos com o original. Se existe uma solução simples e não recursiva, prefira-a para evitar overhead de chamadas.
Conceitos importantes: - Condição básica (caso base): situação em que a recursão para de continuar. - Progresso: cada chamada deve aproximar-se da condição básica (normalmente diminuindo n, o tamanho do problema).
Fatorial: Definição recursiva: F(n) = n × F(n-1) com caso base F(0) = 1. A cada chamada, n é decrementado, até chegar a 0.
Fibonnaci: Sequência definida por F(0) = 0, F(1) = 1, e para n > 1: F(n) = F(n-1) + F(n-2). Observa-se que cada chamada reduz o problema, porém pode haver muitas chamadas repetidas, gerando overhead.
Observação: na prática, é comum discutir desempenho de recursão em visual seguinte, aprendendo técnicas de otimização (ex.: memorização, recursão de cauda, conversão para laços).
Resumo rápido: recursão envolve definição recursiva, caso base e progressão. Use-a quando o problema se naturaliza pela repetição de subproblemas semelhantes; caso contrário, prefira soluções iterativas simples.
Observação: este resumo facilita revisar rapidamente os conceitos e preparar a próxima parte sobre desempenho e otimizações.
Questão 1 (Média): Qual a definição correta de recursão em programação?
Resposta correta: C) Uma função definida em termos de si mesma, direta ou indiretamente.
Explicação: Recursão ocorre quando a função chama a si mesma (direta ou indiretamente). É essencial ter um caso base para terminar a recursão e garantir que cada chamada reduza o problema.
Questão 2 (Difícil): Quais são os três elementos básicos para definir um problema de forma recursiva?
Resposta correta: C) Caso base, progressão, e a garantia de que cada chamada aproxima o término.
Explicação: Um problema recursivo deve ter um caso base (terminação) e uma progressão que reduza o tamanho do problema a cada chamada para chegar ao caso base.
Questão 3 (Difícil): No exemplo do fatorial, qual é a condição básica e a definição recursiva?
Resposta correta: A) Base: F(0) = 1; Recursão: F(n) = n × F(n-1).
Explicação: Para o fatorial, o caso base é n = 0 (retorna 1). A definição recursiva usa F(n) = n × F(n-1), reduzindo n a cada chamada até chegar ao caso base.
Questão 4 (Extrema): Quais técnicas ajudam a otimizar a recursão quando necessário?
Resposta correta: A) Memoização, transformação em laço, tail recursion.
Explicação: Otimizações comuns incluem memorização (cache de resultados), converter recursão em laço quando possível, e explorar recursão de cauda (tail recursion) que pode ser otimizada por alguns compiladores/interpretações.
O pessoal bem-vindos novamente, massa de ciprina de algoritmos e programação de computadores 2 para o INVSP.
Nesta semana, a gente vai aprender um conceito novo de programação, que é bastante importante, principalmente para pessoas que vão se formar em computação, que é a ideia de recursão, funções recorcivas, que é uma ferramenta que é bastante poderosa para poder resolver determinados problemas computacionais, mas que deve ser bem empregada para que você possa atingir resultados satisfatórios, porque na segunda visual sobre esse assunto que a gente vai ver, vou mostrar para vocês que, se aplicamos a recursão de uma maneira indevida ou em momentos que não deve ser empregada, isso pode afetar bastante o desempenho do seu programa.
O aula de hoje é sobre recursão, a primeira visual sobre esse assunto, a gente vai ver mais uma, sobre esse assunto ainda na próxima visual.
Então, o que é uma função? O que é a recursão? Uma função é dita recorciva quando ela é definida em seus próprios termos, que seja diretamente ou indiretamente.
Por exemplo, a gente poderia modificar essa função aqui embaixo para que vai imprimir os elementos de uma lista.
Então, isso seria o meu L, seria a lista que eu estou passando.
Então, eu vou fazer com que o I variedie zero até o comprimento desta lista, e aqui eu vou imprimir cada elemento desta lista.
A gente poderia transformar esta função para a sua versão recursiva.
Então, ficaria algo assim.
A gente vai passar tanto a lista como um paranto, como também a posição que a gente quer imprimir no determinado momento.
Se essa posição for menor do que o tamanho da lista, a gente impreme aqui este elemento, e aí a gente vai fazer uma chamada recursiva.
Essa chamada recursiva indica aqui.
Você vai chamar a mesma função, só que agora com diferentes parâmetros.
Neste caso, é o mesmo a lista, ele, só que estou passando a segunda posição, que é o I mais um.
Então, ele vai entrar neste processo, esse loop, tantas vezes forem necessárias até, ou até que o seu I seja igual ao tamanho da lista, ele.
Então, quando uma função chama ela mesma, a gente diz que é uma função recursiva.
Vamos ver como que vai funcionar esta execução desta função.
Então, imagina que eu tenho aqui a minha lista formada pelos elementos 1, 2 e 3.
Quando a gente faz a chamada a função imprim-reque, nesse caso, o I tem o valor padrão zero, que em cima.
Então, a gente vai fazer uma chamada inicial a função imprim-reque, passando a minha lista e passando o meu I igual a zero.
O que vai ser feito dentro desta função? A gente vai verificar se o I é menor do que o tamanho da lista 3.
Então, como o I é igual a zero e é menor do que a 3, a gente vai imprimir o primeiro elemento, que é o L de zero.
E depois a gente vai ter essa chamada recursiva.
Essa chamada recursiva, pessoal, envolve você criar um novo escopo dentro ainda da função anterior, onde você vai passar novamente os parâmetros.
Então, é o L ainda só que agora o I valendo um.
Tudo bem? Então, nesse segundo escopo aqui, eu tenho a minha segunda execução desta função, onde eu vou verificar que I é menor do que 3.
E aí, eu vou imprimir o L de 1, que é 2, que vou fazer uma terceira chamada recursiva.
Então, ele vai chamado novamente agora com I igual a 2.
2 é menor do que 3, então, ele ainda entra nesse I, vai imprimir o L de 2, que é 3, e ele vai fazer mais uma chamada recursiva agora com L e igual a 3.
Nessa última chamada, como o I é 3 e não é menor do que 3, então, ele já afinaliza esta chamada, então, você vai finalizar esta chamada, e ele vai voltar para o escopo da anterior, e vai fechar também, porque não tem mais nada para executar em seguida a esta chamada que estava aqui.
Na chamada anterior, ele vai voltar também e vai finalizar, e depois, na última chamada, ele também finaliza, e aí, com isso, ele sai da função e volta aqui para o programa principal, para quem estava executando tudo bem.
Ois são os efeitos da recursão.
Então, a cada chamada, a gente vai empilhar na memória os dados locais, que são as variáveis, os parâmetros, e também o endereço de retorno, que pode ser a linha onde foi feita aquela chamada à função, e a função corrente só vai terminar quando a função chamada terminá.
A gente vai executar a nova chamada, que também pode ser recursiva, e ao retornar, a gente vai desempenhar os dados da memória, restaurando o estado que estava antes da chamada recursiva.
O efeito, pessoal, é o mesmo como se eu tivesse várias funções.
Então, imagina que eu faço uma chamada a esta primeira função aqui em primeis zero, que tem a única tarefa de imprimir o L de zero e chamar uma segunda função.
Eu imagina que ele chama a função imprimi1, que tem a função de imprimi o L de 1 e chamar a função imprimi2.
A função imprimi2 também vai imprimi o L de 2 e vai chamar a terceira a próxima função, que é o imprimi3.
E assim por diante.
Então, repare aqui esta chama esta, onde esta chama esta, e esta chama esta.
E quando esta aqui terminar, você volta para a de cima, quando esta terminar, você volta para a outra, e depois quando esta terminar, você volta para a anterior, para daí, quando esta terminar, você volta para quem chamou o imprimi de zero.
Está certo? Quando a gente deve usar a recursão, a gente usa depende, isso depende do problema.
Então, dependendo, a recursão pode ser bem ou mal empregada.
Se a regra mais básica é que, se existir uma versão simples de uma função que não seja recursiva, então ela deve ser usada no lugar da recursiva.
Então, por exemplo, esta função anterior, que a gente usou para imprimir os elementos de uma lista, eu gostaria para vocês que existe uma versão bastante simples, que não é recursiva.
E a gente só transformou ela em recursão para poder exemplificar, mostrar o que é a recursão.
Mas como ela existe, ela é bem simples, a gente prefere, a gente vai preferir usar a função não recursiva.
E quando a gente deve usar a recursão, é quando a gente pode definir o problema de uma forma recursiva na maneira bem natural.
Vamos ver um exemplo disso daqui a pouco.
Então, para a gente poder fazer isso, definir este problema na forma recursiva, a gente precisa definir três pontos principais.
Primeiro deles, a definir o problema de forma recursiva, ou seja, a gente temmos dele mesmo, definir uma condição de término, que a gente chama de condição básica.
E a cada chamada recursiva, a gente deve tentar garantir que se está mais próximo e se satisfazer a condição de término.
Então, vamos ver como ficaria esses três pontos para um problema específico.
No caso, aqui é o problema do fatorial.
Então, eu quero calcular infatorial.
Então, por exemplo, 3 fatorial é igual a 3 vezes 2 vezes 1.
Como que a gente define este problema de uma maneira recursiva? Então, n fatorial é o n vezes o n-1 fatorial.
Então, esse n-1 fatorial, que está aqui, é a chamada recursiva.
O segundo ponto é definir condição de término ou condição básica, que é quando n for igual a 0.
Então, quando n chegar no 0, quer dizer que você tem que finalizar o teu algoritmo.
E a cada chamada recursiva deve se tentar chegar mais próximo da condição básica.
E isso a gente pode verificar aqui no ponto 1, que quando você chama a função recursiva, você está decrementando o n.
Então, quando você está decrementando esse n, e o n, nesse caso, o pessoal é sempre o valor dispositivos, vai chegar ao momento que você vai chegar no n igual a 0, que é a condição de término.
Então, dado essa definição de fatorial, vou implementar uma função recursiva para calcular o fatorial de um número.
Então, eu vou criar uma função FAT, onde eu vou passar o valor de n.
E, o que eu vou fazer? Eu vou primeiro definir a minha condição básica, que é quando o meu n for igual a 0.
Então, o 0 fatorial, por definição, é 1.
Então, nesse caso, a gente já retorna 1.
Caso contrário, o que é dizer, se o meu n for maior do que 0, então, aqui, a gente está assumindo, que a gente não vai passar valores negativos, isso aqui é importante.
Se a gente passar valores negativos, não vai funcionar, ele vai entrar em loop infinito e não vai terminar nunca.
Então, quando, qual seria a minha definição para n maior do que 0? Então, o n fatorial, como a gente tinha visto, era o n vezes o n menos 1 fatorial.
Então, para a gente poder fazer isso em forma de código, netcograma, a gente vai fazer assim um resultado, que é uma variável, vai receber o valor de n, que é o parâmetro, que a gente está recebendo aqui na função, vezes, agora, ele, menos 1 fatorial, é a chamada a fát.
Então, eu vou fazer fát, que é a chamada a própria função, só que agora passando n menos 1.
Bom, isso aqui seria.
.
.
Ele vai calcular isso, vai chamar de novo a própria função com n menos 1, n menos 2, n menos 3, até que o n seja 0, aí, ele vai retornar 1, que vai multiplicar com o 2, ela é chamada anterior, que vai multiplicar depois com 3, a chamada anterior e assim por diante.
E aí, aqui a gente vai retornar esse resultado.
Então, aqui eu vou executar, com, por exemplo, um fát de 4, na qual seria o fatorial de 4.
Então, aqui, fazer assim, 4 de 4, 24, 5, e assim por diante.
Bom, como exercício, pessoal, eu vou deixar para vocês implementar uma função recursiva para calcular o enésimo termo da sequência de fibronate.
Fibronate, pessoal, é definido como uma sequência assim, começa com 0, depois 1, essa aqui seria a condição básica, para o elemento na posição 0, elemento na posição 1, e depois, a partir daqui, para o elemento na posição 2, você vai fazer a soma dos dois termos anteriores.
Então, 0 mais 1 vai te dar 1, e aí, para 3 seria esse mais esse, que seria 2, e para a posição 4 seria 1 mais 2, que seria 3.
Para a posição 5 seria esse mais esse, que é 5, e assim por diante.
Então, a gente já definiu aqui embaixo os três pontos principais.
O primeiro é definir em termos recursivos, então, o f de 0 é 0, o f de 1 é 1, isso daqui é a condição básica, e depois para n maior do que 1, a gente tem que o f de n é igual a f de n menos 1, mas ou mais f de n menos 2.
A minha condição deparada, ou condição base, é quando n for igual a 0, ou n equal a 1, e a gente tem o terceiro ponto, que é chegar cada vez mais próximo dessa condição básica, que é, a gente já verifica aqui, nessas chamadas recursivas, a gente está decrementando em uma ou em duas unidades.
Então, para n positivo, a gente consegue, algum momento, atingir essa condição básica.
Então, o exercício é que você implementa em uma função em Python, onde você recebe, como parâmetro, uma dessas posições aqui em cima, e a função te retorna aquele valor, está a sequência de fibonate.
Então, você passar, por exemplo, f de 5, que esse 5 aqui, ele vai te retornar esse 5.
Se você passar o f de 4, ele vai retornar 3.
Se ele passar o f de 6, ele vai retornar 5 mais 3, 8.
E assim por diante.
Então, pessoal, essa foi a nossa aula sobre recursão.
Na próxima vídeo aula, a gente vai ter mais um outro tópico sobre recursão, que é a parte de desempenho.
Então, quando a gente deve aplicar, quando a gente não deve quais são os efeitos, de se aplicar a recursão em momentos que não se deve utilizar.
E até maneiras de se otimizar o processamento, em caso onde você deve utilizar a recursão, mas você vai ter um desempenho ruim de processamento.
Então, a gente vai ver algumas técnicas de como a gente pode otimizar esse processamento.
Então, obrigado pela atenção de vocês.
A gente se vê na próxima vídeo aula.