Brincando com recursividade em c#
Recursividade, o que é?
A idéia de recursividade é a de um procedimento que chama a si mesmo, seria como se uma ação pudesse desencadear a si mesma, O pãozinho vende muito porque está sempre quentinho ou está sempre quentiho porque vende muito? seria esta questão filosófica, recursiva? É difícil fazer uma analogia da recursividade com as coisas do mundo “real”, uma idéia interessante seria o ato de subir escadas, em que é preciso repetir os mesmos procedimento diversas vezes até atingir o objetivo.
Recursividade no contexto de programação
Neste contexto, podemos dizer que a recursividade é um procedimento (método, função, procedure, etc) que chama a si mesmo até que um objetivo seja atingido, ou seja, é um loop, um loop com condição de parada (se não não seria algoritmo).
Algoritmo para contar letras em uma palavra
Digamos que tenhamos que desenvolver um método que receba dois parametros, uma palavra e uma letra, e que o algoritmo tenha que contar o número daquela letra naquela palavra. Vamos fazer este exercício e 2 formas:
De forma iterativa
Como sabemos que em c# toda string é um vetor, basta fazer um for para percorrer os elementos deste vetor e ir incrementando um contador todas as vezes que se encontrar a letra procurada (tomando o cuidado para converter tudo para maiúsculas no teste condicional).
1 2 3 4 5 6 7 8 9 10 11 | <pre> public static int ContaLetraIteracao(String _string, String _letra) { int contador = 0; for (int i = 0; i < _string.Length; i++) { if (_string[i].ToString().ToUpper() == _letra.ToUpper()) contador++; } return contador; } |
De forma recursiva
Digamos que a linguagem não oferecesse nenhum comando que nos permitisse iteração (loop), então teriamos que construir o método sem a utilização do for, while ou qualquer outra estrutura de repetição, então uma possível solução para isto seria fazer com que o metodo chamasse a si mesmo tantas vezes até atingir o tamanho da palavra, e ir contando as vezes que letra aparecece.
É preciso observar que neste caso, teremos que usar variáveis externas ao método, pois cada vez que ele é chamado (não importa que seja ele mesmo que esteja se chamando) as variáveis são criadas, isto estragaria nossos contadores:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | <pre> int numVezes, numLetras; boolean inicio; public Int32 ContaLetra(String _string, String _letra) { if (inicio) { numVezes = 1; numLetras = 0; first = false; } if (numVezes <= _string.Length) { if (_string[numVezes-1].ToString().ToUpper() == _letra.ToUpper()) numLetras++; numVezes++; // O que acontecria se esta linha fosse a última? e a primeira? ContaLetra(_string, _letra); } inicio = true; return numLetras; } |
Explicando as variáveis:
Parametros:
_string = Palavra a qual vamos procurar pela letra
_letra = A letra a ser procurada
Variáveis externas ao método
inicio => Variável booleana que funciona como uma “sentinela” indicando a primeira vez em que o método é chamdo de “fora” dele mesmo, foi definida fora do método, isto é, na classe que implementa o metodo, para que as chamadas subsequentes não a redefina. Antes do return do método, esta variável é colocada em true, para que a proxima chamada (de fora) reinicie o processo.
numLetras => É o contador de letras, é zerado na primeira chamada ao método (chamada externa) e depois vai acumulando o número de vezes que encontra a letra procurada.
numVezes => É o numero de vezes que o método é chamado, esta variável é incrementada de uma unidade até que seja igual ao tamanho da string enviada (_string.Length)
Utilidade da recursividade.
Isto parece inútil e sem sentido, realmente é bem difícil dar um exemplo realmente útil de recursividade, mesmo porque poderia não fazer sentido para quem ainda está iniciando no assunto, mas é fácil perceber o valor da técnica neste simples exemplo, no caso estamos pesquisando em um vetor (lembrando que uma string em c# é um vetor de caracteres). Mas digamos que a estrutura de dados não fosse um simples vetor, digamos que fosse uma estrutura que pudesse comportar dentro dela, qualquer coisa, até mesmo vetores, ou vetores de vetores. Neste caso o único jeito seria a recursividade.
Exercícios
Exercício 1:
Faça um programa (aqui será mostrado somente o metodo) para calcular a potencia de um número. O método recursivo deve receber como parâmetro a base e o expoente, e devolver o valor da potência.
EX: double CalculaPotencia (int base, int expoente) CalculaPotencia (2,3) = 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | <pre> bool inicio; int resultPot; public Int32 CalcPot(int _base, int _expoente) { if (inicio) { resultPot = _base; inicio = false; } if (resultPot == 0) resultPot = _base; if (_expoente > 1) { resultPot = (resultPot * _base); CalcPot(_base, --_expoente); } inicio = true; return resultPot; } |
Exercício 2:
Faça um programa para imprimir a tabuada, usando recursividade.
Implementação
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | <pre> bool inicio; int dec, numTabuada; // Vetor com o resultado da tabuada, ja convertida em string string[] vetor_t new string[10]; public String[] Tabuada(int _num) { if (inicio) { numTabuada = _num; dec = 10; inicio = false; } if (dec > 0) { vetor_t[dec - 1] = Convert.ToString((dec * numTabuada)); Tabuada(--dec); } inicio = true; return vetor_t; } |
Exercício 3:
Faça um método para limpar todos os maskedit e os Textbox de um form, mesmo que eles estejam dentro de panels, groupbox, etc.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | <pre> public void LimpaForm(Control _Parent) { // Percorre todo o container foreach (Control c in _Parent.Controls) { // Se o objeto for outro Control, chama o proprio metodo if (c.Controls.Count > 0) LimpaForm(c); // Limpa se for um textbox if (c is TextBox) (c as TextBox).Clear(); // Limpa se for um MaskedTextBox if (c is MaskedTextBox) (c as MaskedTextBox).Clear(); } } |
Este é um exercicio realmente útil e que seria muuuito dificil (impossivel, talvez) resolve-lo sem a recursividade, explicando:
O método recebe o parametro _parent, do tipo Control, Control é uma coleção de controles ou um Container onde se pode armazenar outros controls, por exemplo, um Form é um control, um panel é um control.
O método faz um foreach percorrendo todos os objetos dentro de _parent, quando encontra um objeto do tipo Control (Um panel, por exemplo) o metodo chama a si mesmo enviando como parametro o objeto encontrado.
Se o objeto não for um control, o metodo verifica se é um TextBox, se sim, chama o metodo Clear() para limpa-lo, fazendo o mesmo como o MaskedTextBox.
Resolução no visual studio 2008.
O programa apresenta um Form com todas as soluções apresentadas neste texto, na parte de cima é solicitado uma base e a potencia, clicando no botão calcular, a potencia é calculada e o resultado é apresentado.
Em seguida é apresentado um panel onde é solicitado uma string e uma letra que deverá ser procurada nesta string, há 2 radio buttons para se escolher se a busca será feita de forma recursiva ou iterativa.
Logo em seguida é solicitado um numero e ao se clicar no botão, a tabuado do numero á apresentada no panel abaixo.
E, por último, um groupbox com panels internos para testar a limpeza do form, que devera ocorrer a se pressionar o botão “Limpa Form”