Mudanças entre as edições de "Pensamento Computacional - Tópicos Adicionais"
(9 revisões intermediárias pelo mesmo usuário não estão sendo mostradas) | |||
Linha 1: | Linha 1: | ||
=Conceito de Recursividade= | =Conceito de Recursividade= | ||
+ | Determinados problemas podem ser resolvidos de forma muito elegante e compacta usando o conceito de recursividade. | ||
+ | |||
+ | A recursividade acontece quando um método chama a ele mesmo resolvendo um determinado problema para um subconjunto de dados. | ||
+ | Um bom exemplo de solução com recursividade é o problema de calcular o fatorial. Observe que o fatorial de 5, por exemplo, é: | ||
+ | |||
+ | |||
+ | <math>5! = 5 \times 4 \times 3 \times 2 \times 1 </math> | ||
+ | |||
+ | Por sua vez, podemos reescrever da seguinte forma: | ||
+ | |||
+ | <math>5! = 5 \times 4! </math> | ||
+ | <math>4! = 4 \times 3! </math> | ||
+ | <math>3! = 3 \times 2! </math> | ||
+ | <math>2! = 2 \times 1! </math> | ||
+ | <math>1! = 1 </math> | ||
+ | |||
+ | Observe se tivermos um método para o cálculo de fatorial de n, então ele pode se "autoinvocar" para calcular para n-1. Vamos a um exemplo: | ||
+ | <syntaxhighlight lang=java> | ||
+ | public class FatorialRecursivo { | ||
+ | public static void main(String[] args) { | ||
+ | // Testando o método fatorial | ||
+ | int numero = 5; | ||
+ | long resultado = calcularFatorial(numero); | ||
+ | System.out.println("O fatorial de " + numero + " é: " + resultado); | ||
+ | } | ||
− | + | // Função recursiva para calcular o fatorial de um número | |
+ | public static long calcularFatorial(int n) { | ||
+ | // Caso base: fatorial de 0 ou 1 é 1 | ||
+ | if (n == 0 || n == 1) { | ||
+ | return 1; | ||
+ | } else { | ||
+ | // Chamada recursiva: fatorial(n) = n * fatorial(n-1) | ||
+ | long fat = n * calcularFatorial(n - 1) | ||
+ | return fat; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </syntaxhighlight> | ||
+ | Observe que um método recursivo deve ser cuidadosamente planejado, pois em algum momento a chamada recursiva não é executada. Neste exemplo é o caso quando n=1 ou n=0. Até que você tenha experiência em programação, não recomenda-se o uso pois pode levar a efeitos indesejáveis. Lembre-se que chamadas recursivas acabam demandando mais memória da PILHA (STACK), pois variáveis locais são criadas a cada nova chamada do método. | ||
+ | ==Exercício 1== | ||
− | + | Implementar usando recursividade um método java para somar uma sequÊncia de números naturais. O método recebe, por exemplo, 5 e o método deve retornar: | |
+ | <math> 5 + 4 + 3 + 2 + 1 + 0 </math> | ||
+ | OBS: A solução deste pŕoblema acaba sendo ineficiente pela elevada chamada de métodos... | ||
+ | =Chamada Recursiva Indireta= | ||
+ | Um exemplo PROBLEMA de chamada recursiva indireta é mostrado abaixo. Neste exemplo, o método menuPrincipal chama (potencialmente) o método gerenciarSala() que por sua vez chama o método menuPrincipal() e assim cuessivamente. Em algum momento ocorrerá estouro da pilha (STACK). | ||
+ | <syntaxhighlight lang=java> | ||
+ | import java.util.Scanner; | ||
− | + | import javax.swing.plaf.basic.BasicBorders.MenuBarBorder; | |
+ | public class HierarquiaMenu { | ||
+ | public static Scanner teclado; | ||
+ | public static int contador = 0; | ||
+ | public static void main(String[] args) { | ||
+ | teclado = new Scanner(System.in); | ||
+ | menuPrincipal(); | ||
+ | } | ||
+ | public static void menuPrincipal() { | ||
+ | contador++; | ||
+ | System.out.println(contador); | ||
+ | System.out.println("Menu Principal! Escolha: \n1.Gerenciar Usuario\n2.Gerenciar Sala\n3.Sair\n"); | ||
+ | int opcao = 2; // teclado.nextInt(); | ||
+ | switch (opcao) { | ||
+ | case 1: | ||
+ | menuGerenciarUsuario(); | ||
+ | break; | ||
+ | case 2: | ||
+ | menuGerenciarSala(); | ||
+ | break; | ||
+ | case 3: | ||
+ | System.out.println("Deixe sua nota para este software..."); | ||
+ | int nota = teclado.nextInt(); | ||
+ | default: | ||
+ | break; | ||
+ | } | ||
− | + | } | |
+ | public static void menuGerenciarSala() { | ||
+ | System.out.println("Menu Gerenciar Sala! Escolha: \n1.Bla bla\n2.Blabla\n3.Voltar principal\n"); | ||
+ | int opcao = 1; //teclado.nextInt(); | ||
+ | switch (opcao) { | ||
+ | case 1: | ||
+ | System.out.println("Blabla"); | ||
+ | break; | ||
+ | case 2: | ||
+ | System.out.println("Blabla"); | ||
+ | break; | ||
+ | default: | ||
+ | break; | ||
+ | } | ||
+ | menuPrincipal(); | ||
+ | } | ||
+ | public static void menuGerenciarUsuario() { | ||
+ | |||
+ | } | ||
+ | } | ||
+ | </syntaxhighlight> |
Edição atual tal como às 22h25min de 11 de dezembro de 2023
Conceito de Recursividade
Determinados problemas podem ser resolvidos de forma muito elegante e compacta usando o conceito de recursividade.
A recursividade acontece quando um método chama a ele mesmo resolvendo um determinado problema para um subconjunto de dados. Um bom exemplo de solução com recursividade é o problema de calcular o fatorial. Observe que o fatorial de 5, por exemplo, é:
Por sua vez, podemos reescrever da seguinte forma:
Observe se tivermos um método para o cálculo de fatorial de n, então ele pode se "autoinvocar" para calcular para n-1. Vamos a um exemplo:
public class FatorialRecursivo {
public static void main(String[] args) {
// Testando o método fatorial
int numero = 5;
long resultado = calcularFatorial(numero);
System.out.println("O fatorial de " + numero + " é: " + resultado);
}
// Função recursiva para calcular o fatorial de um número
public static long calcularFatorial(int n) {
// Caso base: fatorial de 0 ou 1 é 1
if (n == 0 || n == 1) {
return 1;
} else {
// Chamada recursiva: fatorial(n) = n * fatorial(n-1)
long fat = n * calcularFatorial(n - 1)
return fat;
}
}
}
Observe que um método recursivo deve ser cuidadosamente planejado, pois em algum momento a chamada recursiva não é executada. Neste exemplo é o caso quando n=1 ou n=0. Até que você tenha experiência em programação, não recomenda-se o uso pois pode levar a efeitos indesejáveis. Lembre-se que chamadas recursivas acabam demandando mais memória da PILHA (STACK), pois variáveis locais são criadas a cada nova chamada do método.
Exercício 1
Implementar usando recursividade um método java para somar uma sequÊncia de números naturais. O método recebe, por exemplo, 5 e o método deve retornar:
OBS: A solução deste pŕoblema acaba sendo ineficiente pela elevada chamada de métodos...
Chamada Recursiva Indireta
Um exemplo PROBLEMA de chamada recursiva indireta é mostrado abaixo. Neste exemplo, o método menuPrincipal chama (potencialmente) o método gerenciarSala() que por sua vez chama o método menuPrincipal() e assim cuessivamente. Em algum momento ocorrerá estouro da pilha (STACK).
import java.util.Scanner;
import javax.swing.plaf.basic.BasicBorders.MenuBarBorder;
public class HierarquiaMenu {
public static Scanner teclado;
public static int contador = 0;
public static void main(String[] args) {
teclado = new Scanner(System.in);
menuPrincipal();
}
public static void menuPrincipal() {
contador++;
System.out.println(contador);
System.out.println("Menu Principal! Escolha: \n1.Gerenciar Usuario\n2.Gerenciar Sala\n3.Sair\n");
int opcao = 2; // teclado.nextInt();
switch (opcao) {
case 1:
menuGerenciarUsuario();
break;
case 2:
menuGerenciarSala();
break;
case 3:
System.out.println("Deixe sua nota para este software...");
int nota = teclado.nextInt();
default:
break;
}
}
public static void menuGerenciarSala() {
System.out.println("Menu Gerenciar Sala! Escolha: \n1.Bla bla\n2.Blabla\n3.Voltar principal\n");
int opcao = 1; //teclado.nextInt();
switch (opcao) {
case 1:
System.out.println("Blabla");
break;
case 2:
System.out.println("Blabla");
break;
default:
break;
}
menuPrincipal();
}
public static void menuGerenciarUsuario() {
}
}