[INF1007] Resumo Recursão

Prévia do material em texto

Programação II 
Monitor: André Vicente Pessanha 
Resumo Recursão: 
 
*************************************************************************************************** 
 
OBS​: Essa matéria cai na P1 e >>talvez<< na P3! 
 
************************************************************************************************** 
 
­ Definição:  
 
Existem duas formas de se resolver qualquer problema: Forma Iterativa e recursiva. 
 
Iterativa é justamente a forma que viemos usando desde Prog 1, 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"?  
E dessa vez, 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 <<, precisa ser uma condição que funcione para todos os casos, 
por exemplo, se estamos usando recursão em string para tratar caracter por caracter, qual 
seria o Caso Base ideal?  
 
Quando esse caracter for o '\0' ! Pois além de indicar o final da string, é algo que toda string 
tem por definição! 
 
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 até pra fazer 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!  
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ // ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
 
Exemplo: Uma função que recebe como parâmetro uma string e imprime ela 
recursivamente: 
 
 
 
void imprime (char *frase){ 
if(frase[0] == '\0') return ; 
 
printf("%c",frase[0]); 
 
        imprime(&frase[1]); 
 
} 
 
int main (void){ 
char frase[] = "Pombo Voador"; 
 
imprime(frase); 
return 0; 
} 
 
 
Primeiro passo é pensar numa forma de parar a recursão (Um caso Base), pois quando 
você usa 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! 
 
No caso de strings, o caso base é quando chegamos no '\0' ! Pois é justamente o '\0' que 
indica o final da string.  
 
if(frase[0] == '\0') return ; 
 
OBS:​ return ; é uma forma de encerrar uma função do tipo void! 
 
 
printf("%c",frase[0]); 
imprime(&frase[1]); 
 
OBS:​ Lembrando que escrever frase[0] é o mesmo que *frase, ambas representam o 
começo da string! 
 
O uso de recursão em string é tratar um caracter de cada vez, mas observa que a cada 
chamada da função é passado o endereço do próximo caracter como parâmetro! Então 
esse próximo caracter será o começo da string na outra função! Por isso a gente sempre 
trata frase[0] em todas as condições! 
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 pedaçinhos. 
 
OBS:​ Outra forma de escrever &frase[1] é >> frase + 1 << , lembrando que frase é um 
ponteiro para o primeiro caracter da string, então se somar 1, esse ponteiro vai apontar para 
o próximo caracter.  
 
Eu recomendo usar &frase[1] por ser mais parecido com a forma que lidamos com vetor em 
Prog 1. Mas as duas formas estão 100% corretas! 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ // ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
Exemplo 2: Mesmo enunciado, mas dessa vez é pra imprimir ao contrário: 
 
 
void imprime (char *frase){ 
if(frase[0] == '\0') return ; 
   
        imprime(&frase[1]); 
 
printf("%c",frase[0]); 
 
} 
 
 
Percebe que só foi preciso mudar de lugar a chamada recursiva? :) 
 
Porque agora precisamos "avançar" a recursão até o Caso Base e só depois começamos a 
imprimir cada caracter à medida que a recursão vai "voltando"! 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ // ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
 
Exemplo 3: Função que calcula e retorna o tamanho de uma string: 
 
 
int Tamanho(char *frase){ 
if(frase[0] == '\0') return 0; 
 
return 1 + Tamanho(&frase[1]); 
} 
 
int main (void){ 
int tam; 
char frase[] = "Pombo"; 
 
printf("Tamanho: %d\n",Tamanho(frase)); 
return 0; 
} 
 
 
Como estamos lidando com string, o caso Base será o mesmo, mas dessa vez o tipo de 
retorno da função é int! Já que estamos contando a quantidade de caracteres da string, o 
return precisa ser zero. ( '\0' faz parte da string, mas não é contado!)  
 
E se não for '\0' é porque frase[0] é qualquer outro caracter! Nesse caso o retorno será 1 + o 
tamanho do resto da string! 
 
 
OBS: ​Questão de P1 que pede pra contar algo usando recursão é quase certeza! 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ // ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
­ Mas se existe sempre uma solução iterativa, porque usamos a recursiva?  
 
Todos os problemas podem ser resolvidos de ambas as formas! Então eu recomendo 
sempre usar a forma iterativa por ser algo mais tranquilo e menos arriscado, tirando os 
casos em que o enunciado peça pra usar recursão! (Questão quase que obrigatória em toda 
P1) 
 
Antigamente tinha uma matéria na P3 chamada árvore binária em que isso se inverte, usar 
recursão é a forma mais tranquila e a iterativa fica algo extremamente complexo! 
 
 
OBS: ​Mas não precisam se preocupar, pois houve uma mudança em 2015.1 e árvore foi 
removido da grade de Prog 2! Então sim, já podem comemorar! :D  
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ // ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­