[INF1025] Resumo Recursão

Prévia do material em texto

INF1025: Introdução à Programação 
Monitor: André Vicente Pessanha 
Resumo Recursão​: 
 
*************************************************************************************************** 
 
OBS:​ Essa matéria será cobrada na P1 e talvez na P2 e P3. 
 
*************************************************************************************************** 
 
 
- Definição: 
 
Existem duas formas de se resolver qualquer problema: Forma​ Iterativa​ e ​Recursiva​. 
 
Iterativa é justamente a forma que viemos usando nas primeiras listas de exercício, ou seja, 
você desenvolve uma solução de um problema através de um sequência de passos. Essa é 
a forma de pensamento mais natural e usado em praticamente todos os casos. 
 
Recursiva é a nova forma de solução em que você chama a própria função várias vezes, 
até resolver o problema. Pode ser complicado de entender no começo, ainda mais por não 
ser uma forma natural de pensamento, mas é só praticar bastante que vai ficando tranquilo 
aos poucos! :) 
 
------------------------------------------------------- // ------------------------------------------------------------ 
 
 
- Como se usa recursão? 
 
 
Primeiro vamos revisar como funciona uma chamada comum de função: 
 
Sempre que uma função "X" chama uma função "Y", a função X fica lá parada, esperando o 
retorno da função Y. Mas vamos imaginar que a função "Y" chama uma função "Z", percebe 
que agora a função "X" e "Y" estão paradas esperando o retorno de "Z"? 
Agora imagine que a função "Z" não precisou chamar mais ninguém e retornou algo para a 
“Y” que por sua vez retorna algo para “X” e resolve o problema. 
 
OBS:​ Percebeu que tudo começou na função "X" , "avançou" até a função "Z" e depois 
"voltou tudo" e terminou na própria função "X"? Começou e terminou na função X! É 
essencial visualizar isso pra entender recursão. 
 
 
 
 
 
 
- Então o que muda usando recursão? 
 
 
Basta trocar as funções "X", "Y" e "Z" da explicação acima por >> "X", "X" e "X" <<! 
 
Mas pra isso funcionar, precisamos impor um limite, uma condição de fim da recursão 
chamado >> ​Caso Base​ <<! Então no exemplo acima, a última chamada da função "X" 
precisa cair no Caso Base! 
 
 
- E se não tiver caso Base, o que acontece? 
 
"X" chama "X" que chama "X" que chama "X" que chama "X" que chama "X" que chama 
"X"......infinitas vezes! (Sim! Dava pra fazer até um remix top dessas chamadas! Haha) 
 
É muito importante entender isso! Principalmente essa parte de que você chama uma 
função e a outra fica "esperando" e essa ideia de "avançar" até o caso Base e ir "voltando" 
para a função que fez a primeira chamada! Pois é justamente assim que a recursão 
funciona! 
 
OBS:​ Recursão é como se fosse uma repetição while! (Repetição infinita) 
Então >>​NUNCA​<< use while ou 'for' com recursão! Justamente pelo fato da recursão já ser 
uma repetição! 
 
 
------------------------------------------------------- // ------------------------------------------------------------ 
 
Recursão em Strings​: 
 
Primeiro passo é pensar numa forma de parar a recursão (​Um caso Base​), pois quando 
usamos recursão, a função chama a si própria infinitas vezes (Como se fosse uma repetição 
infinita!) Então é obrigatório colocar >>​SEMPRE​<< antes de qualquer coisa, uma condição 
que será o limite onde a recursão vai parar! 
 
 ​EX:​ ​Crie uma função recursiva que retorne o tamanho (Quantidade de caracteres) de 
uma string: 
 
def lenRec(s): 
if(not s): 
 return 0 
return 1 + lenRec(s[1:]) 
 
 
print(lenRec("Pombo Voador")) # Exibe 12 
 
 
O uso de recursão em string é tratar um caracter de cada vez, mas observe que nesse 
exemplo, a cada chamada da função é passado como parâmetro a string menos seu 
primeiro caracter! (Lembrando que o primeiro índice é zero!) E a cada chamada recursiva 
da função, cada vez mais vamos nos aproximando do caso base. É como se a gente 
dividisse um problema grande em pequenos pedacinhos e obrigatoriamente no final vamos 
cair no caso base! (String vazia) 
 
Em strings, o caso base é quando a string não possui mais caracteres, ou seja, a string está 
>> ​vazia​ <<! E a melhor forma de verificar é usando a seguinte condição: 
 
if(not s): 
 
OBS:​ A condição if será True se a string s está vazia OU será false caso contrário. 
Não lembra como funciona o critério de True e False em Python? É só dar uma lida no 
tópico >> Critério de Verdadeiro e Falso em Python: (Atalho)​ ​<< no PDF Dicas Gerais. :) 
 
 
EX2: Faça uma função recursiva que retorne a quantidade de letras maiúsculas de 
uma string. 
 
def qtdMaiuRec (s): 
if(not s): 
 return 0 
elif(s[0] >= 'A' and s[0] <= 'Z'): 
 return 1 + qtdMaiuRec(s[1:]) 
 
return qtdMaiuRec(s[1:]) 
 
print(qtdMaiuRec("PomBo VoaDor")) # Exibe 4 
 
É exatamente o mesmo esquema, mesmo caso base, só que dessa vez temos uma 
restrição, só podemos contabilizar caracteres que são >> Maiúsculos << e qualquer tipo de 
restrição nos enunciados, traduzimos para código através de condições! Por isso 
precisamos acrescentar essa condição >> elif(s[0] >= 'A' and s[0] <= 'Z'): << logo após o 
caso base. 
 
OBS: ​Lembrando que somente em Python é correto usar elif( ‘A’ <= s[0] <= ‘Z’) 
E como essa notação é completamente errada em outras linguagens (Como C, Lua, etc) 
então prefiro usar a outra justamente pra não confundir. Mas como ambas estão corretas 
em Python, fique à vontade pra usar qualquer uma delas. :) 
 
 
 
 
------------------------------------------------------- // ------------------------------------------------------------ 
 
 
Recursão com números​: 
 
EX: Crie uma função recursiva que exiba cada um dos algarismos de um número 
verticalmente na tela. 
 
def exibeVertRec (x): 
if(x < 10): 
 print(x) 
 ​return 
 
exibeVertRec (x // 10) 
print(x % 10) 
 
print(exibeVertRec(326)) 
 
O caso base é quando x é um valor menor que 10, ou seja, só possui um único algarismo! 
Então é só exibir na tela com print e encerrar a recursão. Caso contrário x possui 2 ou mais 
algarismos, então por isso só colocarmos >> ​x % 10​ << no print (Pra exibir somente o que 
está mais à direita) e na chamada recursiva usamos >> ​x // 10​ << para enviar o número x 
>>​Sem ​<< o primeiro algarismo da direita. 
 
OBS: ​Observe que em questões de recursão que só é pedido pra exibir algo na tela, 
devemos encerrar a recursão colocando o >> ​return​ << no caso base! (Nos próximos 
exemplos isso não vai ser necessário, justamente por ser pedido que a função retorne 
algum valor.) 
 
OBS: ​Observe que pra exibir exatamente na ordem do número recebido, precisamos 
colocar a chamada recursiva >> ​Antes​ << do print. Pois precisamos "avançar" a recursão 
até o Caso Base e só depois começamos a imprimir cada algarismo à medida que a 
recursão vai "voltando"! 
 
 
EX: Modifique a função do item anterior para que seja exibido verticalmente na ordem 
inversa. 
 
def exibeVertRec (x): 
if(x < 10): 
 print(x) 
 return 
 
print(x % 10) 
exibeVertRec (x // 10) 
 
print(exibeVertRec(326)) 
 
OBS:​ Notou que foi só mudar de lugar a chamada recursiva? :)