Resumo_Recursão

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

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)
E além disso, na verdade esse "sempre" é entre aspas! Existe 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!
Então eu recomendo já entender recursão logo no começo, porque na p3 não tem escapatória!
**********************************************************************************
OBS: Houve uma mudança no esquema desse período (2015.1), árvore foi removido da grade de Prog 2! Então sim, já podem comemorar! :D 
**********************************************************************************