[MÚSICA] Vamos, então, estudar pouquinho mais sobre recursão, que é essa técnica que é muito simples, mas muito poderosa ciência da computação. A gente já viu como implementar o Fatorial de forma recursiva, como implementar Fibonacci de forma recursiva, vamos agora para lembrar pouco da busca binária e ver como a gente pode implementá-la recursivamente. Se você lembrar a busca binária, é algoritmo que a gente pode usar, por exemplo, para encontrar número aqui no dicionário que nós temos, aqui o belo Houaiss. Vamos supor que eu quero procurar a palavra arcabouço aqui nesse dicionário, o dicionário tem muitas páginas, o Houaiss, vamos ver quantas páginas ele tem. Tem mais de 2900 páginas, então, se eu fizer uma busca sequencial aqui eu não vou achar nunca. Então, uma busca binária me ajuda bastante. Como é que eu faço? Quero achar a palavra arcabouço, eu abro bem aqui no meio, divido ao meio e vejo aqui a palavra que tem aqui é forma. Forma é uma palavra maior na ordem alfabética ou menor que arcabouço? É maior. Se é maior, quer dizer que o arcabouço está aqui para o lado esquerdo, nessa metade. Então, agora repito recursivamente essa mesma operação. Agora só preciso procurar esse pedaço, de novo divido na metade aqui. E agora, deu aqui carpintaria. Repito o processo, divido na metade aqui, carpintaria. Deu aporrinhado, arcabouço, a, p, r. Arcabouço é maior do que aporrinhado. Então, se eu tinha algo desse tipo aqui, e arcabouço agora está para a direita, então eu posso jogar para fora essa parte da esquerda e só tenho que procurar nesse pedaço. E de novo eu vou abrir na metade desse pedaço e vou indo assim sempre buscando na metade, recursivamente chamando a busca binária até que vai chegar o momento que acho a página que está a palavra. Vamos ver Python como que seria a implementação recursiva da busca binária. Eu já coloquei a implementação aqui para vocês. Vamos estudar pouco como isso aqui está funcionando. Então, tenho a função busca binária, recebe como parâmetro essa lista completa inicialmente, na qual eu vou fazer a busca, daí, aqui tem elemento que é o elemento pelo qual eu quero buscar. Nesse exemplo aqui, vamos supor que a gente está querendo buscar número dentro de uma lista de números. E depois, tem aqui esses parâmetros min e max que são parâmetros opcionais. Então, se eu quiser passar como parâmetro, eu vou passar qual é o começo e o fim, o mínimo e o máximo dentro dessa minha lista que eu quero buscar naquele momento. Então, inicialmente eu começo com a lista completa, por exemplo, uma lista de 5000 elementos. Então min começa no zero e o max lá no último. E à medida que eu vou executando o algoritmo, vou sempre dividindo pela metade, então, min vai subindo e o max vai descendo. Ou eu vou encontrar o elemento ali, ou uma hora o min vai passar do max, e daí, quer dizer que o elemento não está na lista. Eu coloquei elementos como parâmetros opcionais porque eu quero na primeira vez que eu chamo a busca binária, eu quero não passar nada. Então, se eu não passar nada, o que é que ele vai fazer? Ele vai, se não passar nada como parâmetro aqui para o min e para o max, o min vai receber o valor zero querendo dizer que eu começo da primeira posição, e o max eu estou atribuindo esse valor none, que é o valor como se fosse valor vazio Python. None é uma palavra reservada de Python que significa valor vazio. E eu faço aqui, se o valor inicial é none, o max fica sendo o comprimento da lista menos que é o último elemento da lista. Se ele não passa nenhum parâmetro, é a lista completa, se ele passa parâmetro, daí vai ser trecho menor ali daquela lista. Então, vamos ver agora o algoritmo da busca binária nessa forma recursiva. Esse pedaço aqui é o idêntico à forma interativa, não mudou nada. É o seguinte, se o max é menor que min, significa que aconteceu aquele caso que eu não encontrei o elemento e os dois se trocaram de valor, o max ficou menor que o min, quer dizer que o elemento não está nessa minha lista, então, eu devolvo false para indicar que não encontrei o elemento. Caso contrário, eu calculo o novo meio. O meio ali vai ser metade do caminho entre o min e o max. Então, o que é que é? É o min mais max menos min dividido por dois. Max menos min é o tamanho do trecho que ainda falta eu verificar, dividindo por dois é metade, e daí, o min mais essa metade, vai dar exatamente ali no meio. Isso aqui seria equivalente a eu fazer max mais min dividido por dois, que é a média entre o max e o min. Tanto faz, duas formas de calcular a mesma coisa. Então, o que importa é que o meio vai estar apontando para o elemento ali do meio e aqui eu estou usando a divisão inteira por dois, ele não vai, se o número for ímpar ele não vai ter ponto cinco, ele vai truncar a divisão para sempre ter índice ali da minha lista. Daí, tem esses três casos, primeiro caso, o elemento que está na lista de meio, o elemento que está na posição do meia da lista é maior do que o elemento que eu estou buscando. Se ele é maior que o elemento que estou buscando, eu tenho que ir buscar na parte esquerda da lista, no começo da lista, desde o começo da lista, que é desde a posição min até o meio menos. Então, eu chamo recursivamente a busca binária, passando como parâmetro a mesma lista, o mesmo elemento, só que agora é novo trecho. O novo trecho começa no min e vai até meio menos. Eu vou até antes do meio, porque ele está naquela parte esquerda da lista. Se ele cai nesse segundo caso aqui, daí quer dizer que o elemento que está no meio da lista é menor que o que eu estou buscando. Se ele é menor que o que eu estou buscando, quer dizer que o elemento que eu estou buscando está do lado direito, está para o final da lista, entre a posição meio mais e o final. Então, eu chamo a busca binária recursivamente, passando a mesma lista, o mesmo elemento, só que agora o trecho no qual eu vou buscar é do meio mais até o max, que é o final daquele elemento. Essas são duas chamadas recursivas. O terceiro caso é o caso que, se a lista de meio não é maior que o elemento e não é menor que o elemento, quer dizer que ele é igual ao elemento, ou seja, eu achei o elemento que eu estava buscando, daí eu simplesmente devolvo meio índice no qual eu achei. Então, isso aqui é a busca binária numa versão recursiva. Você vê que ela fica até mais simples do que aquela versão interativa, até menos comandos que você tem que dar. Tem essa ideia de a gente pegar problema maior e ir buscando formas de quebrar ele problemas menores. Vamos testar para ter certeza que isso está funcionado. Para testar, eu vou fazer o seguinte, eu vou pegar uma lista aqui, dez, 20, 30, 40, 50, 60, uma lista, e agora vou usar o pytest, aquela versão parametrizada que eu gosto bastante, porque a gente pode testar bastante coisa com pouco esforço. E eu vou fazer o seguinte, eu vou passar como parâmetro a lista, o valor que eu quero procurar e o índice esperado que ele deve devolver. São três coisas aqui, vai ser pouco mais complicado. E daí, é o seguinte, se eu passar com uma lista o A e eu buscar pelo valor dez, qual que tem que ser, o que é que ele tem que devolver? Ele tem que devolver que o dez está na posição zero, a primeira posição do retorno. Então, ele tem que devolver zero. Se eu passar a lista e o 20, ele tem que devolver posição porque o 20 está na posição do vetor. Se eu passar 30, posição dois, se eu passar o 40, posição três. 50, na posição quatro. Vamos ver aqui, 60 é seis, a 70. O 70 não está no vetor, então, o que é que ele tem que devolver? Ele tem que devolver false, que não está no vetor. Que outros casos interessantes eu poderia testar? Por exemplo, caso de elemento que está entre dois, mas que não existe, então, por exemplo o 15. Se for o 15, tem o dez e o 20, mas não tem o 15, então, tem que devolver false também. Outro caso, número negativo, ele estaria antes do início do vetor, mas não está. Então, tem que devolver false também. Acho que já testamos muitos casos, já está bom, termina aqui a minha lista de casos. E agora, uma função de teste, então, vai ser testa_busca_binaria. Ele vai receber como parâmetro a lista, o valor que deve ser buscado e o resultado esperado. E eu quero fazer assert busca_binaria, não preciso desse parêntesis, busca_binaria, vou passar como parâmetro a lista e o valor e o que ele me devolve é o índice esperado. Então, vamos salvar isso aqui. Salvei nesse buscabinaria.py que está nesse diretório Recursao. Vamos aqui, entrar nesse diretório Recursao e agora vou rodar o py.test. Como chama mesmo? Chama busca_binária. Vamos ver o que acontece. Opa, pytest not defined, eu preciso importar aqui, vamos importar o pytest, import pytest. De novo. Opa, olha o que que ele falou, teste falhou e oito passaram, então oito casos ele me deu a resposta certa e uma deu a resposta errada. Qual foi a que deu a resposta errada? Ele já pinta de vermelho aqui o que deu a resposta errada. Então ele falando, olha: busca_binária, passando esse vetor aqui, 10, 20 ,30 ,40, 50 e o 60, deveria devolver cinco mas você tava testando que era seis. Eu botei seis aqui, será? Deixa eu ver, zero, dois, três, quatro e cinco. Realmente tinha que ser cinco, eu que errei na hora de fazer o teste. então aqui o esperado não devia ser seis, devia ser cinco, então vamos consertar o meu teste. Aqui deveria ser cinco. E agora vamos executar novamente. Então pronto, passou os nove casos de teste, os nove deram certo, a gente testou aqui muitos casos diferentes que poderiam ter uma busca binária. Testamos todos elementos de vetor, testamos elementos depois do final, antes do começo, elementos no meio, acho que todos os casos que eu consigo imaginar no momento, então nossa busca binária parece que está bem corretinha. essa aí foi a busca binária. Então já vimos o Fatorial, o Fibonacci e a Busca Binária. Uma coisa que é interessante, não necessariamente simplesmente pelo fato de que você pode fazer o algoritmo recursivo, significa que ele vai ser mais eficiente, particular, o Fibonacci aqui, que a gente implementou recursivamente, ele chama muitas funções recursivas, porque cada Fibonacci, vamos supor, Fibonacci de 100, vai chamar recursivamente o Fibonacci 99 de 98 que vai ficar recalculando muitas coisa que ele já calculou. Então talvez se você fizer uma versão iterativa ela acaba sendo muito mais eficiente, então depende do caso, não necessariamente recursão é mais eficiente, geral é mais simples o código, mas não necessariamente mais eficiente. Fibonacci é caso que normalmente a versão recursiva não é muito eficiente. Busca Binária tende a ser bastante eficiente. Vamos ver agora o MergeSort. Então a gente tem ai vários algoritmos de ordenação que a versão recursiva consegue ser bastante eficiente, o MergeSort é desses algoritmos que é muito mais eficiente do que o BubbleSort, do que a seleção direta que a gente viu antes. Vamos ver ai como é que funciona o MergeSort. MergeSort é ordenação por intercalação. Como que funciona esse algoritmo? Então, é algoritmo de ordenação, a gente tem uma lista de elementos, vamos supor que é uma lista de números, e a gente quer colocar eles ordem crescente, eles estão fora de ordem e a gente quer colocar eles ordem crescente. Então como funciona o algoritmo? Divida a lista na metade recursivamente, ou seja, na metade, e depois na metade, na metade até que cada sublista contenha apenas elemento e portanto já esteja ordenada. Vamos supor que você começa com uma lista de 1024 elementos, você divide na metade, então duas de 512, depois, duas de 256, duas de 128 e vai recursivamente dividindo várias listas na metade até que você vai chegar 1024 listas de elemento cada uma, e daí cada elemento já tá ordenado. Daí repetidamente, intercale as sublistas para produzir novas listas ordenadas, então duas a duas você intercala elas, depois dois mais dois pra gerar uma de quatro depois quatro mais quatro pra gerar uma de oito, oito mais oito pra gerar uma de dezesseis intercalando de forma a manter essa ordenação. Deixa eu pegar aqui uma animaçãozinha que eu peguei da Wikipedia, que nos ensina muito bem como isso funciona. É o seguinte, vamos supor que a gente tenha essa lista aqui: 6 5 3 1 8 7 2 4. Como que a gente faria o MergeSort? A primeira, suponha que tem uma lista, array, vetor de elementos, a primeira coisa que a gente faz: separa dois, depois cada dois a gente separa dois de novo, depois cada dois a gente separa dois de novo, essa é a primeira parte do algoritmo onde a gente acaba chegando ali oito elementos, oito elementos, oito sublistas cada uma com elemento. A gente tá implementando aqui essa primeira parte, Divida a lista na metade recursivamente até que cada sublista contenha apenas elemento. É o que a gente fez aqui. Agora vamos pra essa segunda parte aqui. Repetidamente intercale as sublistas para produzir novas listas ordenadas. Então, primeira coisa, vamos intercalar o 6 e o 5 para produzir uma lista ordenada de tamanho dois. Como que faz isso? É isso aqui, 5, 6 é uma lista de tamanho dois que tá ordenada. Agora faz a mesma coisa pro 3 e pro 1. 1 e 3 é uma lista de tamanho dois e ordenada. O 7 e 8 e o 2 e 4 não precisa mudar a ordem já tá ordenado, então, pronto. Agora nós temos quatro listas de tamanho dois. Cada uma delas tá ordenada. E agora a gente vai intercalar duas a duas. Então vamos intercalar essas esse 5 e 6 com o 1 e 3. Primeiro a gente compara o 1 com o 5, o 1 é menor então o 1 entra antes. Depois compara o 3 com o 5, o 3 menor entra antes e o 5 com o 6 o 5 é menor e depois por último o 6. Então pronto, aqui temos uma lista de tamanho quatro já ordenada. fazemos a mesma coisa ali. 7 com 2, o 2 é menor entra, depois o 4 é menor, entra, depois o 7 e depois o 8. Pronto, temos duas listas, cada uma de tamanho quatro, cada uma ordenada, e agora a gente intercala essas duas, finalmente faz Merge dessas duas. Qual que é o menor? É o 1, comparando 1 e dois é o 1, depois é o 2, depois é o 3, depois é o 4, depois é o 5, depois é o 6. Intercalando essas duas listas terminamos com uma única lista de tamanho oito e que está ordenada. E terminamos por completo de resolver aquele problema de ordenação dos oito elementos. É assim que funciona o MergeSort, tem essa camada, esse passo de ir dividindo e depois o passo de ir intercalando. Então a gente vai repetindo até que tenhamos apenas uma lista no final, que vai estar totalmente ordenada. Como é esse algoritmo? Vamos abrir, então aqui está o algoritmo. Ele é composto de duas partes, o merge_sort si e o merge que é aquela intercalação. Vamos ver aqui. O merge_sort, ele recebe como parâmetro uma lista, e aqui a gente tem a base da recursão, lembra toda recursão tem que ter uma base. Essa aqui é a base da recursão. Ou seja, se o comprimento da lista é menor ou igual a não tem nada pra ordenar, simplesmente devolve a lista. Caso contrário a gente vai querer dividir a lista no meio, e daí o meio é o comprimento da lista dividido por 2, e a gente vai dividir o lado esquerdo da lista e o lado direito. O lado_esquerdo, o que vai ser, a gente vai chamar recursivamente o merge_sort só pro lado esquerdo. Esse lista de : meio, lembra, ele vai pegar tudo desde o começo da lista até o meio-1. Essa aqui é aquela divisão de sublistas do Python. Ele vai chamar recursivamente o merge_sort, passando como parâmetro apenas o lado esquerdo da lista, e o merge_sort, se ele estiver correto, ele vai ordenar esse lado esquerdo da lista e vai devolver aqui pro lado_esquerdo o lado esquerdo da lista já ordenado. E daí chamamos recursivamente aqui de novo, para o lado direito da lista, então, o meio : vai devolver desde a posição do meio até a posição final da lista. Chama recursivamente aqui também no merge_sort e o resultado ele vai devolver e guardar aqui nessa variável lado_direito. e daí ele vai devolver então dois pedaços da lista, o lado_esquerdo e o lado_direito, cada deles vai estar já ordenado, só falta agora intercalar os dois. Pra intercalar agente chama a função merge, passando como parâmetro o lado_esquerdo e o lado_direito. Agora, como funciona essa função merge? O merge aqui também ele é implementado utilizando recursão. Como que é? É o seguinte, primeiro tem essa aqui, a base, essa base da recursão, tá falando: if not lado_esquerdo, significa: se o lado esquerdo ali for uma lista vazia, daí devolve simplesmente o lado_direito. E a mesma coisa aqui, se não tiver o lado_direito, devolve simplesmente o lado_esquerdo, porque o merge, a intercalação de vazio com alguma coisa é o alguma coisa. Então aqui essa base da recursão. E depois aqui tem a recursão propriamente dita, que diz o seguinte: if lado esquerdo de zero, menor que lado direito de zero, esse é o momento que ele tá comparando, o primeiro elemento da posição do lado esquerdo com o primeiro Primeiro elemento da posição do lado direito. Se o que está do lado esquerdo é o menor, daí, é ele que vai ter que entrar no começo da nova lista intercalada. Então, se o lado esquerdo é menor, a nova lista intercalada aqui, ele cria uma nova lista tendo o lado esquerdo de zero como o primeiro elemento da lista. E o que que é o resto da lista? O resto da lista, ele chama recursivamente o Merge para o resto. O que que é o resto? É o lado esquerdo removendo o primeiro elemento, então esse 1: vai pegar do elemento que tá na posição que é o segundo elemento até o final, fazer o Merge com o lado direito. Caso contrário, se o lado esquerdo não é menor que o lado direito, daí, ele vai entrar nesse outro caso aqui, ele coloca o lado direito no começo da nossa lista, então cria essa lista aqui contendo o lado direito no começo e chama recursivamente o Merge para resto, ou seja, passando o lado esquerdo e o lado direito sem esse primeiro elemento que foi removido. Então, assim que funciona o Merge Sort. Você vê que é algoritmo bem mais sofisticado, bem mais complexo, para entender, é pouquinho mais complicado, e minha sugestão é que você pegue esse programa e tente rastrear ele, como que funciona a execução dele para ele ordenar uma lista, por exemplo, lista de oito elementos, você pode, por exemplo, abrir esse programa no depurador do Idle e executar passo a passo para ver como é que ele faz isso. Outra coisa interessante seria você construir uma bateria de testes aqui para testar que esse Merge Sort está funcionando. Uma coisa que eu gostaria de mostrar pra vocês, essa animação interessante que nós temos aqui de alguns algoritmos de ordenação. Então, deixa eu copiar isso aqui. Se vocês forem nesse site da da toptal.com, tem esses vários algoritmos de ordenação que a gente pode escolher, por exemplo, o tamanho do vetor, eu quero vetores de tamanho 50 aqui. E tem aqui vários algoritmos de ordenação. Então, tem aqueles mais simples e não tão eficientes, tipo o Insertion, Selection, Bubble, que a gente viu no começo desse curso, tem o Merge Sort que a gente viu aqui, tem o Heep, o Quick Sort que é muito famoso, tem Quick Sort ali que é super otimizado, que é esse Quick3, Heep Sort, tem vários algoritmos. E daí você tem vários tipos de dados, aqui, dados aleatórios, dados quase ordenados, dados ordenados na ordem inversa, e aqui vetores onde tem muita repetição de elementos. E daí, você pode, apertando cada desses botões aqui, executar todos os algoritmos para ver nesses diferentes casos qual que vai mais rápido, qual que vai mais lento, eu vou clicar aqui no play all que ele executa todos os algoritmos, vamos lá, olha, todos os algoritmos estão executando, a gente está vendo o Merge Sort está aqui e está ordenando esses vários tipos de vetores. A gente vê que o Bubble Sort e o o Selection estão muito ruins, olha o Merge Sort já terminou, e todos esses mais eficientes já terminaram de ordenar tudo aqui, enquanto que o, ainda estão terminando de ordenar esses aqui, enquanto que o Bubble Sort está muito devagarinho. Vocês podem ver que o Insertion Sort até que é pouquinho melhor desses, do Insertion, o Selection e do Bubble, mas os algoritmos que utilizam fortemente a recursão são muito mais eficientes, com exceção do Quick Sort. O Quick Sort, quando você tem muitos elementos repetidos ele não se dá muito bem olha, ele ainda não terminou, sendo que o Merge Sort já terminou de ordenar todos os tipos de elementos. Então, vocês veem que esse Merge Sort que a gente viu hoje é algoritmo bastante eficiente. O Bubble Sort e o Selection são dos piores, embora eles já ordenaram os vetores aleatórios e os vetores quase ordenados, eles ainda não terminaram os da ordem inversa e os que tem muitos elementos repetidos. O Bubble Sort já terminou aqui da ordem inversa, só falta o Selection terminar algumas coisas. É interessante ver que diferentes algoritmos têm desempenho diferente dependendo do tipo de dados que a gente tem. Então, a conclusão. Recursão é uma ferramenta poderosa para se lidar com problemas complexos. A gente consegue escrever programas simples e que resolvem problemas complexos. Ele aplica o princípio da divisão e conquista, que é muito utilizado computação. Você tem problema muito complicado, a gente tenta sempre dividir ele problemas menores pra conquistar a solução desse problema. Programação normalmente essa recursão é identificada por funções ou métodos que chamam a si mesmos. Então, a gente vai ver que alguns casos a gente vai querer usar recursão mas, lembrar que nem sempre uma solução recursiva é a mais eficiente. A gente tem que pensar nesse balanço entre uma solução simples e uma solução mais eficiente. Então, por hoje é só. [MÚSICA] [MÚSICA]
