Recursão

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..

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!!!

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...

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!

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!

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.

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.

Ou seja, se n for diferente de 0, exibe o último dígito (n%10) e depois exibe verticalmente o resto dos dígitos (n//10).

Obs: caso você não lembre bem, a gente tá separando o último dígito do número. Olha o exemplo:

Viu?! Com as operações //10 e %10, a gente consegue separar o último dígito de um número inteiro. Beleza! Mas se a gente executar esse código e testar o número 198, não vai ficar igual ao enunciado!

O resultado foi:

Ala! Ficou ao contrário! Precisamos rever isso!

Calma, relaxou, o que acontece é que a gente tá exibindo o último dígito pra depois exibir o resto verticalmente, mas a gente também pode fazer na ordem contrária (por isso falei sobre a linha de execução no primeiro passo).

Se a gente fizer a chamada recursiva antes de exibir o último dígito, então todos os dígitos vão ser exibidos na ordem contrária! Lembra que falamos agora pouco que as funções recursivas vão e voltam?! Olha o que acontece quando a gente executa esse programa agora:

Agora ficou exatamente como no enunciado! A ideia é que dá pra mudar a ordem que as funções recursivas vão executar seus comandos, se é de trás pra frente ou de frente pra trás, só de colocar o comando antes ou depois da chamada recursiva. Nesse caso, colocar o print(n//10) antes da chamada recursiva exibe_vert(n//10) devolve o resultado na ordem contrária de chamar depois, sacou?!

Agora nosso programa já funciona. Mas eu queria te lembrar que “if (n!=0):” é a mesma coisa que “if n:”.

Essa função faz exatamente a mesma coisa que a função que a gente já tinha feito, mas assim fica mais limpa bonitinha!

Essa matéria é bem confusa, né?! Mas calma, continua aqui nos exercícios que a gente vai ficar craque em recursão! Te espero no próximo exercício, hein!

Fala aí, doido! Cara, tenho que te contar que essas questões de recursão, depois que você pega o jeito, são bem repetitivas. Então o macete é fazer bastante exercício, jae?! Depois que pega o jeito fica tranquilo! Então vem comigo!

Bora começar falando da estrutura que nossa função vai ter. Os dados externos que nossa função vai receber são n1 e n2, de acordo com o enunciado. Então esses vão ser nossos parâmetros. E o nome a gente mesmo escolhe, e eu vou escolher “intercala”.

Beleza! Vamos dar uma olhadinha no exemplo de resultado que o enunciado deu.

Até intercalei as cores pra tu reparar que, de trás pra frente, o que tá acontecendo é foi concatenando o último dígito de n1 com o último de n2 até um deles acabar, sacou? Olha…

Assim fica mais fácil de enxergar! Com exceção dos dois primeiros, os outros são o último dígito de n1 com o último dígito de n2. Depois penúltimos, depois ante penúltimos, etc. Bora tentar fazer essa proeza em Python.

Se liga, a primeira coisa que a gente tem que verificar é se os números n1 e n2 são diferentes de 0, né? Levando em consideração que a gente vai cortando o último dígito a cada chamada recursiva, quando um deles acabar, então podemos acabar a recursão. Então vamos começar com o caso base!

Então, se os dois números, n1 e n2, ainda existirem, a gente vai fazendo aquela parada que a gente observou! Concatenando o último dígito de cada um deles. Pra pegar o último dígito de um número, a gente só precisa calcular o resto da divisão por 10 (%10). E pra concatenar, usamos a função str().

Mas ainda não é só isso nessa linha. Essa função retornaria apenas o 68 do exemplo do enunciado. A ideia é a gente concatenar a chamada recursiva na frente desses dígitos, aí o resultado vai intercalar todos os dígitos, e não só os dois últimos. Se liga:

Viu? Olha de novo o exemplo:

Levando em consideração que o primeiro a ser calculado vai ser o 68, depois a gente concatena o 35 na frente usando a função intercala de novo, sem os últimos dígitos (já que tiramos usando o //10), e assim por diante… Agora, só falta a gente lidar com o caso onde um dos dois números acaba.

Mano, quando um dos dois números acaba, a gente só precisa concatenar com o outro todo. Pra fazer isso de forma fácil, vamos usar um truquezinho malandro. Saca só!

Quando um dos números n1 ou n2 acabar, esse número vai ser igual a zero. A gente não precisa saber qual deles acabou primeiro, porque basta a gente somar n1+n2 e o resultado vai ser idêntico ao número restante, já que somar com 0 não vai mudar em nada.

Só que isso ainda não vai funcionar! Isso porque a função tá retornando string no primeiro return, mas no segundo tá retornando um número inteiro. A gente precisa fazer com que todos os casos retornem string. Pra isso, a gente também precisa usar str() no segundo return.

E pronto! Agora a função tá funcionando! Bora testar??

Pra gente testar, bora usar os mesmos dados do enunciado e ver se a resposta sai igual também!

Quando eu executo esse programa, o resultado é esse:

Exatamente igual ao do enunciado! Ufa! Parece que funcionou hahhaha. Te vejo no próximo, capitão!

A primeira coisa que nós temos que fazer é definir o escopo da nossa função recursiva, observe que ela deve ser capaz de calcular , logo tanto quanto serão parâmetros da função.

Definindo a função :

Agora que temos a função definida, temos que identificar o caso básico da nossa recursão, que nada mais é do que a solução de um problema trivial que dará início ao retorno das chamadas recursivas:

Nesse caso, quando nos referimos a uma solução trivial na potenciação temos que , logo quando o valor retornado pela função será 1.

Da mesma forma que identificamos o caso básico, temos que identificar o passo recursivo, que nada mais é do que o padrão de chamadas da própria função que será realizado enquanto :

Esse passo consiste em multiplicar o valor de pela chamada da função com os parâmetros e , observe nesse exemplo como ficarão as chamadas para :

Coe, truta! Muita coletividade na quebrada! Dinheiro no bolso, sem miséria… É nós!

A primeira coisa que a gente tem que fazer pra resolver essa questão é… saber o que é sequência de Fibonacci. Segundo o Wikipédia, é uma sequência que começa com 0 e 1 e depois vai sendo a soma dos últimos dois números. Tipo assim:

E assim vai! Parece que a gente tem que criar uma função recursiva que recebe como parâmetro um número inteiro e retorna o número correspondente na sequência… E, pela definição, a gente já saca que a sequência é naturalmente recursiva. Se liga só:

Vamos começar escrevendo o cabeçalho da função!

Pronto! Agora, a gente precisa pensar no caso base…

Bora começar vendo o caso que a função termina. Bom, se for 0 ou 1 a gente já sabe a resposta. Olha os números dos itens…

Se liga que o n dá um índice e a gente tem que retornar o número da sequência, heinn! Não confunde! E repara, mano, que os índices e os números da sequência são iguais nos dois primeiros itens. Esses dois itens também são, coincidentemente, nossos casos base. Quando queremos fibonacci de 0, podemos retornar 0. Mesma coisa com o 1, retornamos 1. Vamos escrever em Python!

Pronto! Se for menor que 2 (0 ou 1), a gente retorna o próprio valor… Mas se for maior a gente precisa retornar a sequência.

Pra gente retornar o valor da sequência caso seja maior que n, bora dar uma segunda olhada na definição de fibonacci…

Olha, a gente pode retornar de boas igualzinho na definição da sequência.

E pronto! Só falta a gente testar!!

Pra testar, eu vou rodar o programa com alguns prints e vou testar com os dados que o professor passou no enunciado pra ver se bate.

Ala! Depois de executar, deu certinho!

O resultado foi exatamente como no enunciado! hihihi Finalizamos por hoje, capitão! Te vejo na próxima jornada (chamada exercício de fixação)!

Fala aí, maninho! Tudo na paz? Se liga, nessa questão o professor quer que a gente some todos os dígitos de um número inteiro usando recursão.

Bora segurar as lágrimas e tentar fazer a questão. Se liga, o que a nossa função precisa saber de dado externo pra funcionar?! Bom… Ela precisa saber qual o número que a gente quer somar os dígitos e só! Então esse vai ser nosso único parâmetro.

E se liga que você pode dar o nome que você quiser pra função e pro parâmetro. Siga seu coraçãozinho! Mas é uma boa ideia dar nomes intuitivos, ok? Usar o nome “n” não é legal, mas eu sou rebelde.

Mentira! Eu escolho nomes pequenos aqui só pra não gastar muito espaço na tela, caso você esteja lendo pelo seu celular… Mas enfim, bora começar a escrever nossa função!

Bom, pra resolver recursivamente a gente precisa fazer o problema grande virar o mesmo problema, só que menor… Como fazer isso nesse caso?! Hmmmmm.

Vamos pensar no número 215, que o professor passou de exemplo no enunciado. Tu percebe que o somatório desse número é um dígito + o somatório do resto?

Obs: na teoria, não faz diferença se a gente for separando o último dígito ou o primeiro dígito.

Mas na prática faz, porque a gente não sabe separar, de forma matemática. o primeiro dígito do resto. Mas a gente sabe separar o último, usando divisões por 10. Olha nesse exemplo como a gente pode fazer pra separar o último dígito de um número:

Show! Mas vamos dar só mais uma olhada em qual vai ser nosso caso base. Percebeu que na ilustração a gente parou de subdividir o problema quando o número só tinha um dígito? Ou seja, quando o número é menor que 10 a gente pode parar. Esse é o nosso caso base. Mas não é a única forma! Dá uma olhada:

Olha! A gente também consegue fazer n == 0 como um caso base. Problemas de programação sempre têm mais de uma resposta, e eu tô querendo enfatizar que se você fizer diferente não tá errado, ok? Nessa resolução, vou escolher usar o caso base como n

Agora a gente já pensou em qual vai ser o caso base e em como subdividir o problema do enunciado. A gente só precisa escrever essa lógica no corpo da nossa função, em Python.

Pronto! Se for menor que 10 a gente retorna o próprio n, e se for maior a gente retorna a soma do último com o somatório do resto dos dígitos. Vamo só fazer um teste pra ver se a função tá funcionando de boas...

A gente espera que o resultado desse programa seja 8, e quando a gente executa:

O resultado foi 8 mesmo! EBAAA

Mas antes de finalizar o exercício, vou te falar sobre umas coisas… Se você estiver sem tempo, pode pular pra próxima questão!

Cara, vou copiar e colar aqui a ideia usando n == 0 como caso base.

O resultado no fim vai ser exatamente o mesmo, mas pode ser que você prefira fazer dessa forma (eu, geralmente, prefiro). Então eu vou adaptar a última resposta pra usar esse caso base pra você ver como ficaria, ok? Olha:

Se liga que o if tá invertido também. O que tá acontecendo é: “se n for diferente de 0, retornar o último dígito + a soma dos outros. Caso contrário, retornar 0”. E é exatamente isso que a gente fez ali em cima nas continhas! Outra coisa que queria falar sobre é que a gente omitiu o else dessa vez. Cadê o else??

Então… Lembra que quando a gente tava falando de funções, eu comentei que a função acaba quando chegamos em um return?! A ideia nesse programa é que se o primeiro if for verdadeiro, a função vai chamar o return e vai chegar ao fim. O segundo return só vai ser executado se o if for falso. Reparou que, nesse caso, o else se tornou desnecessário?!

Se você tivesse colocado também não teria problema, mas eu queria comentar em algum lugar que nem sempre você precisa do else. Quando o primeiro if tem o return dentro, o else se torna desnecessário! Mas isso é só pra complementar seu conhecimento, ok? Na dúvida, coloca o else lá!

Valeuuuuuu!

E aí, maninho! Nessa questão, o enunciado descreve como deve ser nossa função. Até o nome da função foi ditado! Bora obedecer solenemente e criar o cabeçalho da função conforme as ordens do professor...

Pronto! Criamos a função e o parâmetro com os mesmos nomes que foram ditos no enunciado. Agora só falta o resto.

Mas, se liga que além disso, o enunciado também deu spoiler de qual vai ser nosso caso base. Nossa recursão tem que parar quando n for igual a 1, certo? Então a gente já sabe que nosso caso base é esse. E também, nossa função tá contando quantas vezes ela mesma foi chamada. Quando n for igual a 1, é pra parar de contar. Então a gente retorna 0!

Pronto! Agora sim, só falta o resto.

Bom, se o número não for igual a 1, a gente precisa aplicar a função f(x) que tá escrita no enunciado. Mas ela depende da paridade do número n! Se n for par temos que fazer uma coisa, e se for ímpar, outra. Pra isso a gente vai ter que usar outro if. Mas, calma, como a gente pode checar se um número é par ou não?

Pô, se um número for par e a gente dividir por 2, não vai sobrar nada. Mas se for ímpar, vai sobrar 1. A gente pode usar isso a nosso favor. Vamos usar o operador de resto de divisão inteira (%)!

É claro que você não precisa, de forma alguma, fazer exatamente igual a mim. Existem várias formas de pensar sobre cada uma das decisões que eu tomo aqui na hora de resolver o exercício, ok?! Show! Agora, no enunciado tá mandando a gente contar quantas vezes vamos chamar a função. Então, bora retornar 1 + a chamada recursiva.

Repara que eu chamo a função recursiva com os parâmetros que foram dados no enunciado. No fim, essa função vai retornar quantas vezes a função foi chamada até n se tornar 1. Vamo testar!

No enunciado diz que, quando chamamos com o parâmetro 5, a função tem que retornar 5. Vamos executar pra conferir.

Retornou mesmo! Então, até aqui tá funcionando de boas. Mas ainda precisamos fazer a função exibir todos os itens da sequência, igual tá no enunciado.

Cara! A cada elemento da sequência de chamadas de funções é recebido como parâmetro n da função. Então, a gente só precisa, antes de tudo, dar um print() no n.

Se liga só!

A gente tá exibindo o n antes de qualquer coisa. Agora, se a gente fizer o mesmo teste que a gente fez antes, o resultado vai ser esse:

Parece que tem um 5 a mais no fim, mas tá certo. A função collatz só exibiu até o 1, assim como o enunciado diz. O último 5 foi exibido pelo nosso print() que tá fora da função. A gente usou ele pra testar só!

Por isso, a gente já acabou nossa questão. Finalizamos o exercícioooo!