[MÚSICA] Na aula de hoje vamos aprender uma técnica muito poderosa, embora simples, da ciência da computação, que é a ideia da recursão. O que é recursão? Muitos problemas contém, dentro de si, problemas menores. Para você resolver esse problema maior você precisa resolver esse problema menor que está dentro do problema maior. Esses problemas menores são similares ao problema maior. A gente diz que esses problemas tem uma estrutura recursiva. Principalmente, quando problema grande tem dentro de si problema menor que dentro de si tem problema menor que tem problema menor. E vai diminuindo esse problema até que chega momento que o problema é trivialmente resolvido. A gente pode, então, aplicar algoritmo recursivo para resolver esse tipo de problema. Como seria então, aí algoritmo recursivo para resolver esse problema recursivo? O algoritmo é o seguinte, se o tamanho do problema for pequeno, ele é tão pequeno que você consegue resolver. Daí resolva diretamente aí. A gente chama isso aí de base da recursão. É momento que o problema está muito pequenininho é muito fácil de resolver a base da recursão você resolve diretamente. Caso contrário, ou seja, o problema não é pequeno, você tem que quebrar esse problema partes menores. Então, reduza esse problema a uma instância menor do mesmo problema e daí, aplique o algoritmo recursivamente a essa instância menor. Depois que você aplicou o algoritmo recursivamente a essa instância menor, aí você pega o resultado do algoritmo e volta à instância original e tenta resolver o problema original. Então, isso é aí, abstratamente, como os algoritmos recursivos funcionam. Exemplos de algoritmos recursivos que a gente vai ver aqui, que são problemas que têm essa estrutura recursiva que a gente pode resolver com o algoritmo recursivo. O cálculo do fatorial é muito simples porque o fatorial de número n é o proprio número n multiplicado pelo fatorial de n menos. Então, você, para resolver o fatorial de n você pega o n multiplica por uma versão menor do mesmo problema que é o fatorial de n menos. A sequência de Fibonacci, que é essa sequência aí dada por essa formulinha, também a gente pode resolver de uma forma muito simples com o algoritmo recursivo, a gente vai ver como fazer isso. Aí tem outros problemas pouco mais sofisticados, por exemplo, a busca binária, ela pode ser resolvida muito simplesmente também, por meio de algoritmo recursivo. A gente já tinha visto algoritmo interativo, sem usar recursão para resolver a busca binária. A gente vai ver agora algoritmo recursivo para a busca binária. E finalmente, tem alguns algoritmos de ordenação aí mais sofisticados do que a gente viu. Por exemplo, o MergeSort, mas tem outros também o HeapSort e QuickSort, que usam recursão e conseguem, dessa forma, com algoritmo muito simples, ter desempenho muito rápido, muito eficiente. Então, algoritmos do tipo MergeSort são muito mais eficientes que o BubbleSort que a gente viu, por exemplo, só que eles são aí pouquinho mais sofisticados por que eles usam recursão. Vamos voltar aqui para o fatorial ver como é que a gente podia implementar fatorial recursivo. Vou abrir aqui novo arquivo para a gente. Então, vamos definir uma função fatorial. Fatorial é muito simples, ele recebe o número n como parâmetro e a gente quer resolver aqui esse fatorial. Primeira coisa, a gente precisa de uma base da recursão. Quando que a gente tem aquele caso muito trivial onde é muito fácil de resolver o fatorial? Eu diria fatorial de zero, fatorial de. Esses são casos triviais. Então, a gente poderia dizer aqui se o n, particular, se o n é menor do que. Daí, a gente pode dizer aqui que o fatorial é. Então, quando o n for a gente devolve quando o n for zero a gente devolve. Quando n for negativo aí não faz sentido você perguntar o fatorial de número negativo, daí a gente simplesmente vai devolver também. Caso contrário, aí sim é o caso que a gente cai fora da base da recursão. Ou seja, não é o caso trivial, é o caso que a gente precisa fazer alguma conta. Então, qual que é o fatorial de n quando a gente tem n grande? O fatorial de n é n multiplicado pelo fatorial de n menos. Ele simplesmente escreve aqui fatorial de n menos. Então, o que a gente está fazendo aqui? A gente está fazendo o que a gente chama de uma chamada recursiva. A função fatorial está chamando a própria função fatorial. E aqui cima o que nós temos é o que a gente chama de a base da recursão. Então, a gente já tem aqui uma implementação da função fatorial. Vamos agora testar. Vou usar aqui o pytest para a gente testar, que essa nossa implementação está funcionando e eu vou usar aquela versão do pytest parametrizada. Então, a gente usa o parametrize e eu botei aqui, eu vou dar pares de entrada e o valor esperado. E então vamos ver, fatorial de zero tem que dar. Fatorial de tem que dar. Fatorial de dois tem que dar dois. Fatorial de três tem que dar seis. Fatorial de quatro, tem que dar 24. Fatorial de cinco tem que dar 120. Terminou nossa lista. Fecha o parênteses aqui do parametrize. Então, esses aí são os casos e daí a gente define agora a função de teste. Então, vai ser o teste da fatorial, vai receber a entrada e o valor esperado. E a gente vai verificar essa inserção de que o fatorial da entrada é igual ao valor esperado. Então, vamos executar aqui, eu vou salvar isso aqui, eu vou salvar no fatorial, nesse meu diretório aqui. Aqui, vamos para aulas, vamos para a parte três, aqui fatorial. Salvei. Pronto e agora eu vou rodar aqui o pytest. Nesse diretório aqui, na parte três. Pytest fatorial. Deu problema. O problema foi aqui, caractere que não é aceite, eu botei alguns acentos e ele não gostou desses acentos. Vamos ver aqui a recursão, simplesmente fica mais simples eu simplesmente tirar esses acentos da recursão aqui. Pronto. Deu certo. Então, os seis testes passaram aqui no meu fatorial. Então, para esses seis casos aqui a nossa implementação recursiva do fatorial funcionou. Então, perceba aí muito bem essa questão de ter uma chamada recursiva e ter a base da recursão. Vamos ver outro exemplo aqui. O Fibonacci. Então, Fibonacci aqui é uma sequência, definida dessa seguinte forma: Fibonacci de zero é zero, Fibonacci de é e para n maior que o número de Fibonacci vai ser a soma do número de Fibonacci para n menos mais o número de Fibonacci para n menos dois. Ou seja, cada elemento dessa sequência é a soma dos dois anteriores. Então, essa aqui é a base da recursão e essa aqui é a fórmula recursiva. Então, como é que a gente poderia implementar aí o Fibonacci? Eu vou começar, eu vou até copiar isso aqui, salvar isso aqui como Save as, chamar de Fibonacci, e a gente reutiliza as coisas. Então, vai ser aqui Fibonacci. E a base da recursão aí vai ser diferente. Então, note que quando o n é menor estritamente que dois, ou seja, zero ou o valor de Fibonacci é o próprio n, né, zero, zero. Então, vou fazer o seguinte, if n é menor que dois devolve n, essa vai ser a base da recursão aqui do Fibonacci. Então, para zero vai devolver zero, para vai devolver que é exatamente o que diz a fórmula aqui. E depois o cálculo recursivo. A gente vai dizer o seguinte. [SEM ÁUDIO] O Fibonacci de n, então, vai ser o Fibonacci de n menos mais o Fibonacci de n menos dois, que é o que diz essa fórmula aqui. Fibonacci menos mais Fibonacci n menos dois. Então, aqui a gente tem essa chamada recursiva. E note que, nesse caso a chamada recursiva está chamando duas vezes a própria função Fibonacci. E agora, vamos escrever aqui teste. O teste aqui vai ter que ser valores diferentes. Então, o teste do Fibonacci aqui, vamos apagar esses valores. [SEM ÁUDIO] E vamos ver, Fibonacci de zero tem que ser zero e Fibonacci de tem que ser. Fibonacci de dois é a soma dos dois anteriores, mais zero que dá. Fibonacci de três é mais que dá dois. Fibonacci de quatro é dois mais que dá três. Fibonacci de cinco é três mais dois que dá cinco. Vamos colocar mais alguns aqui? Fibonacci de seis, vai ser cinco mais três que é oito. Fibonacci de sete vai ser oito mais cinco que é 13. Está bom. Se quiser você pode continuar. E daí a gente vai ter aqui o teste da Fibonacci, acerta aqui, que eu Fibonacci. Então, vamos ver se está funcionando a nossa implementação recursiva aqui do Fibonacci. Então, na parte, vamos aqui, pytest, Fibonacci py. Oito testes passaram. Então, para esses oito casos aqui, a nossa implementação recursiva do Fibonacci está funcionado. Então, lembrar que sempre tem essa base da recursão aqui e depois a chamada recursiva. Então, por hoje é só, mas vamos daqui a pouco, num próximo vídeo, dar uma olhada como que a gente pode fazer a busca binária e o MergeSort utilizando algoritmos recursivos. [MÚSICA] [MÚSICA] [MÚSICA]
