Recursão

Teoria Completa

Definição de recursão

Fala aí! Aqui na playlist a gente já trocou uma ideia sobre como fazer repetições em Python usando os laços For e While. Mas cada um desses laços tem vantagens e limitações. Por isso eu vim te contar hoje que também dá pra fazer repetições sem usar nenhum laço de repetição, usando uma técnica chamada “recursão”. Essa técnica dá pra gente mais flexibilidade. Bora ver como funciona essa técnica doida!

Cara, primeiramente, calcula pra mim quanto que dá o resultado dessa continha aqui:

Foi?! Fez a conta?! Eu imagino que o resultado deu 8. Agora, eu vou fazer uma pequena modificação e você calcula de novo, ok?!

Agora deu 9. Mas, doido… tenho certeza que dessa vez você calculou MUITO mais rápido que na primeira vez. E eu vou te contar o que aconteceu: você já sabia a resposta de parte do processo, então você só somou mais um.

A verdade é que nenhum ser humaninho é capaz de resolver a primeira conta de cara. Eu aposto que quando foi calcular, você fez, malandramente, isso:

Ou seja, no início tu disse que a resposta é 1 + o resto, depois 2 + o resto, até acabar. Isto é, você, sem se dar conta, subdividiu o seu problema várias vezes até chegar em um problema que tu sabe resolver, que é 1+1, porque aí a gente sabe que é 2 só de olhar. Quando eu mudei o problema, aí você fez:

O nome dessa forma de resolver problemas se chama recursão. A gente usa recursão mentalmente, sem perceber, pra resolver vários problemas da vida real! Mas eu tô te contando isso porque a gente pode usar essa técnica pra resolver problemas de computação também. Tenta lembrar que a ideia da recursão em programação é transformar o mesmo problema em um problema mais simples e resolver ele com a mesma função.

Funções são blocos de código que resolvem um problema específico. Por isso que, na prática, funções recursivas são funções que chamam a si mesmas, jae?! Deixa eu te mostrar um caso onde essa parada é realmente útil.

Aplicação de recursão

Ok! Agora que a gente entendeu o conceito, vamos resolver mais um problema de forma recursiva pra ficar bem claro na sua cabecinha. Eu vou te mostrar um caso clássico, que pode cair na sua prova!

Lembra de fatorial, lá do ensino médio?! O fatorial de n é o produto de todos os números naturais menores ou iguais a n, sem contar com o 0. Um número fatorial é escrito como número inteiro, positivo e seguido de um sinal de exclamação (!). Olha o exemplo de 5 fatorial:

Agora vamos tentar resolver esse problema. Mano, eu não sei, só de olhar, quanto é 5 * 4 * 3 * 2 * 1. Porém, eu sei que 4 * 3 * 2 * 1 é a mesma coisa que 4 fatorial. Então, a resposta do nosso problema é:

Pronto. Essa é a resposta. Você talvez se pergunte como que a resposta de um problema pode conter o mesmo problema (nesse caso, o problema era o fatorial e na resposta do problema TEM FATORIAL). E a ideia é justamente essa!

Se a gente não sabe resolver o problema todo, a gente reduz o mesmo problema pra uma ordem menor. 5! É igual a 5 * fatorial do resto do problema. Bom, pra gente resolver esse novo problema, teríamos que, agora, resolver o fatorial de 4.

Cara***! Caímos no mesmo problema de novo! Não sabia fatorial de 4 e continuo sem saber fatorial de 3.

Mas repara que uma hora o problema vai ser tão simples que a gente vai conseguir resolver.

Pra calcular o fatorial de 0 a gente não precisou fazer conta, tá ligado?! Foi um caso muito mais simples. Por isso, a gente usa como condição final. Assim que a gente chega no 0 fatorial, podemos parar de calcular. Agora, a gente volta substituindo os valores que a gente foi encontrando no caminho, afinal, a gente queria o fatorial de 5, lembra?

Viu?! Agora a gente pode voltar substituindo… Assim, a gente consegue, com uma mesma metodologia, resolver qualquer problema de fatorial. E a gente pode generalizar:

Olha que maravilha!

Bora escrever essa técnica doida em Python!

Aplicação de recursão em Python

Vamos escrever uma função que é capaz de resolver qualquer fatorial. Primeiramente, vamos lembrar do manual da recursão:

“Sabe resolver o problema?! Resolva. Não sabe?! Diminua a ordem do problema.”

E como a gente acabou de ver, aplicar essa ideia em problemas fatoriais é tipo assim (com uma linguagem mais pythoniana rsrs):

E olha como a gente poderia escrever em Python:

Olha como fica o código da função recursiva que resolve problemas fatoriais… Se n for igual a zero a gente sabe resolver, né?! Então resolvemos. Retornamos 1. Caso contrário, a gente retorna o mesmo problema com uma ordem menor. Guarda bem a cara dessa função, porque a maioria das questões de recursão têm a resposta MUITO parecida com essa, só mudando o que tá nos returns e no if, jae?!

Vamos testar esse programa!

Coloquei uns prints pra gente conferir o resultado. Executando esse programa, a resposta é:

Olha lá! Num passe de mágica a resposta saiu! Uma função relativamente simples, de só 4 linhas, resolveu o problema (e dava pra ser menor!). O mais difícil é pensar recursivamente, e pra ficar craque nisso, é importante fazer um montão de exercícios.

Mas dá uma segurada! Às vezes (muitas vezes) a nossa função dá errado, e vou te adiantar aqui algumas possíveis causas pra você checar caso a sua não funcione, tá?!

Loop infinito (muito tempo)...

Mano, uma função recursiva é a estrutura mais básica de repetição. Seu código entra em loop e só para quando a condição do if é atingida. Se nunca for atingida, o programa vai ficar num loop infinito (letrinhas vermelhas de erro vão te assombrar!).

Vem comigo que vou te mostrar outro exemplo de função recursiva! Imagina que a gente precisa fazer uma função que soma todos os números entre 0 e N, um número inteiro recebido como argumento da função. Vamos supor que o número recebido seja 10. Pô, tu consegue sacar que, assim como no fatorial, esse é um problema que pode ser subdividido em problemas parecidos?!

Quando a gente enxerga essa propriedade num problema, aí a gente consegue criar uma solução recursiva! Vamos generalizar...

Escrevendo essa maravilha em Python, fica assim:

Prontinho! Tá ERRADO! Isso porque, desse jeito, a função vai ficar rodando pra sempre. Do jeito que tá, a função vai chamar a si mesma pra sempre. Por isso que a gente precisa de uma condição que acabe com o loop. Aqui, a gente quer somar todos os números até o zero. Então, quando a gente chegar no zero, é só não chamar a recursão de novo!

Então olha como fica se a gente quiser interromper o somatório no zero:

Prontinho! Agora sim, a função vai chamar a si mesma se n for diferente de zero, mas se for igual, vai retornar 0 e acabou. Não vai mais ficar somando pra sempre. Reparou que essa função tá MUITO parecida com a função que calcula fatoriais??? É sempre a mesma cara! E se tu ficar craque em fazer elas, as questões de recursão vão começar a ficar menos complicadas, eu juro!

Por isso eu te espero nos exercícios de fixação! Valeuuuuu!!

Expandir

Exercício Resolvido #1

Elaboração Própria

Escreva uma função recursiva que calcule o fatorial de um número recebido como parâmetro.

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Fala, meu padrinho! Nessa questão a gente precisa calcular o fatorial de um número usando recursão!

Mas calma, a gente vai tirar essa de letra! Pra começar, nossa função recebe como parâmetro um número inteiro. A nossa função tem essa cara:

Se liga, a ideia da recursão é: sabe resolver? resolve. Não sabe? Diminui a ordem do problema.

Então, qual o caso de fatorial que a gente sabe resolver? Que não precisamos fazer nenhuma conta e nenhum esforço? Bom… É quando n é igual a 0, certo? Que aí podemos dizer de cara que o resultado é 1.

Mas quando não é zero, a gente precisa diminuir a ordem do problema, e pra isso a gente precisa lembrar na moral sobre o que é fatorial.

Cara, generalizando, a ideia é que o fatorial de n é a mesma coisa que n * fatorial de n-1.

Então, se a gente não sabe o fatorial de um número n de cara, a gente calcula como n * fatorial de n-1.

E pronto! Essa é a resposta! Mas antes, vamos testar..

Passo 2

Pra testar, eu vou colocar um print() embaixo da função, chamando-a com um número inteiro qualquer pra ver se o resultado fica certinho.

E, segundo minha calculadora, o resultado tem que ser 120.

Bora executar o programa pra ver no que dá!

Olha que maravilha! Funcionou!

Recursão pode ser uma matéria um pouco confusa, mas em geral as soluções são bem pequenininhas, viu?! Cê vai conseguir mandar bem nessa matéria, tenho certeza! Mas bora fazer mais alguns exercícios pra você ficar fera nessa parada. Te espero no próximo!!!

Resposta

Exercício Resolvido #2

PUC-Rio, Lista 7.

Escreva uma função recursiva que receba um número inteiro (n) como parâmetro e retorne o número de vezes que os algarismos 3 e 4 aparecem em n. Exemplo: se n for 239424, a função retornará 3.

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Fala, chefe! Aqui a gente precisa contar quantas vezes os números 3 e 4 aparecem em um número inteiro de forma recursiva.

Relaxa! Primeiramente, vamos montar nossa função. Pra contar, a gente só precisa de um dado externo, certo? Que é o número que a gente quer contar os 3 e 4. Então só teremos esse parâmetro, e vamos chamar de n, arbitrariamente.

Ok, qual é o caso mais fácil da gente saber se tem 3 ou 4? Bom, se o número for igual a 0 a gente sabe que não tem nenhum 3 e nenhum 4 nele, certo?!

Mas quando não é zero, a gente precisa diminuir a ordem do problema, e pra isso a gente precisa pensar um pouco sobre o que é diminuir a ordem do problema...

Passo 2

Se liga nesse número grandão aqui:

Mano, tu consegue perceber que a quantidade de 3 e 4 desse número grandão é a mesma coisa que a soma das quantidades de 3 e 4 se a gente dividir ele? Vamos chamar a quantidade de 3 e 4 de q34 pra economizar espaço na ilustração, ok? Olha só:

A gente separou o 5, e eu te digo que a quantidade de 3 e 4 do número de antes é a mesma que a soma da quantidade de 3 e 4 desses dois números que a gente separou agora. Basicamente, se o último dígito for 3 ou 4, a gente diz que a quantidade de 3 e 4 é 1 + quantidade de 3 e 4 sem o último dígito, sacou? Olha o código.

A gente pega o último dígito e checa se ele é 3 ou 4. Se for, a quantidade de 3 e 4 do número inicial é 1 + a quantidade de 3 e 4 que ainda restam, sacou?? Aí o ciclo se repete recursivamente. E caso o último não seja 3 e nem 4, então a quantidade de 3 e 4 é a mesma sem aquele número!

Já que 0 + conta_3_4 é a mesma coisa que não somar nada, a gente não precisa colocar! Mas essa é a resposta, ok? Apesar de ter várias outras respostas possíveis, essa é uma das soluções. O importante é entender a ideia, ok?! Agora, bora testar!

Passo 3

Pra testar, vou chamar a função dentro de um print() embaixo e ver se o resultado bate.

Olha, nesse código a gente espera que o resultado seja 3. Vamos executar!

E o resultado foi exatamente como esperávamos! MUAHAHHAA! Te espero no próximo, doido!

Resposta

Exercício Resolvido #3

PUC-Rio, Lista 7.

Escreva uma função recursiva que receba um número inteiro positivo como parâmetro e o imprima verticalmente, ou seja, um dígito por linha.

Exemplo:

Se o número recebido for 198 a função irá exibir

1

9

8

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Mermão, essa braba! Aqui a gente precisa se ligar em outra propriedade das funções pra gente entender bem o que tá acontecendo.

Mas se liga, vou te falar o segredo da parada. Tu já reparou que, quando uma função termina, a linha execução volta pra onde a gente chamou a função? Assim, olha:

Se a gente executar esse programa, o resultado vai ser esse:

Viu? Esse exemplo foi só pra enfatizar que, quando a função termina, o programa volta pra linha de onde a função foi chamada e continua o fluxo. Isso também acontece se você chamar uma função dentro de outra e, o ponto onde eu quero chegar é, também acontece nas chamadas recursivas! Olha essa função:

Se parâmetro recebido for diferente de 0, então vai retornar n * fatorial(n-1). Caso contrário (caso seja igual a 0), vai retornar 1. Essa função calcula n fatorial. Mas, vou adicionar uns print() pra te mostrar uma parada dahora!

Olha! Eu coloquei alguns prints e chamei a função depois pra calcular 5 fatorial. Olha o resultado desse programa depois de executado:

Olha isso! Sacou que as funções recursivas vão empilhando problemas cada vez menores até conseguir solucionar, e depois vai voltando até chegar no problema maior de novo?!

E você já vai sacar o porque eu to te dizendo isso, mas antes, bora voltar pro nosso enunciado e pensar na estrutura que a função do nosso exercício vai ter.

Passo 2

Se liga, se a nossa função vai exibir verticalmente um número, o que a gente precisa pra fazer a função funcionar?? Bom, precisamos do número a ser exibido, certo? Então esse vai ser nosso único parâmetro!

Beleza! Agora, a gente precisa verificar nosso caso base. Bom, o pensamento recursivo é o seguinte: exibe o último e depois exibe verticalmente o resto! Mas, caso o número seja 0, não precisamos fazer nada.