Aula Prática #09 - Recursividade

Exercício 1) Exemplos de Recursividade

  1. Verifique o seguinte código que calcula o máximo de um intervalo dado de um array de três formas diferentes (uma iterativa e duas recursivas)

    TestMax.java

    // -----------------------------------------------------------
// Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
// https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed
// -----------------------------------------------------------
// 3 versoes para descobrir o maximo de um intervalo de um array:
// (uma iterativa e duas recursivas)
// (Pedro Ribeiro @ DCC-FCUP)
// -----------------------------------------------------------

public class TestMax {
   
   // Os 3 metodos seguintes recebem array v[] e duas posicoes start e end
   // e devolvem o maior numero do array entre start e end (inclusive)
   
   // --------------------------------------------------------
   
   // Versao iterativa   
   static int maxIt(int v[], int start, int end) {
      int maxSoFar = v[start];                // Maior ate agora
      for (int i=start+1; i<=end; i++)        // Percorrer intervalo
         maxSoFar = Math.max(maxSoFar, v[i]); // Actualizar maximo
      return maxSoFar;
   }

   // --------------------------------------------------------
   
   // Versao recursiva 1: dividir em elemento inicial e resto da lista
   static int maxRec1(int v[], int start, int end) {
      if (start == end) return v[start];  // caso base (tamanho 1)
      int max = maxRec1(v, start+1, end); // chamada recursiva (resto da lista)
      return Math.max(v[start], max);     // combinar resultado
   }
   
   // --------------------------------------------------------
   
   // Versao recursiva 2: dividir em metade esquerda e metade direita
   static int maxRec2(int v[], int start, int end) {
      if (start == end) return v[start];    // caso base (tamanho 1)
      int middle = (start + end) / 2;       // ponto medio
      int max1 = maxRec2(v, start, middle); // recursao na metade esquerda
      int max2 = maxRec2(v, middle+1, end); // recursao na metade direita
      return Math.max(max1, max2);          // combinar resultado
   }
   
   // --------------------------------------------------------
   
   public static void main(String[] args) {
      int v[] = {1,5,2,8,4,3,7,6}; // Inicializacao de array

      System.out.println("maxIt: " + maxIt(v, 0, v.length-1));
      System.out.println("maxRec1: " + maxRec1(v, 0, v.length-1));
      System.out.println("maxRec2: " + maxRec2(v, 0, v.length-1));
   }

}
  2. Calculando recursivamente a soma de um array.
    Usando como base o código do máximo, implemente e teste duas versões recursivas de um método para calcular a soma do elementos entre start e end do array v[]:

Exercício 2) Capicuas

  1. Verifique o seguinte código que inverte um array de forma recursiva. Compile, teste e verifique que percebe exactamente como o código está a funcionar.

    TestReverse.java

    // -----------------------------------------------------------
// Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
// https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed
// -----------------------------------------------------------
// Invertendo um array (versao recursiva)
// (Pedro Ribeiro @ DCC-FCUP)
// -----------------------------------------------------------

import java.util.Arrays;

public class TestReverse {

   // Inverter array v entre posicoes start e end
   static void reverse(int v[], int start, int end) {
      if (start>=end) return;     // Caso base: array de tamanho < 2
      int tmp = v[start];         // Trocar primeiro com ultimo
      v[start] = v[end];
      v[end] = tmp;
      reverse(v, start+1, end-1); // Chamada recursiva para o resto
   }
   
   // -----------------------------------------------------------
   
   public static void main(String[] args) {
      int v[] = {2,4,6,8,10}; // Inicializacao de array

      System.out.println("Antes  do reverse: " + Arrays.toString(v));
      reverse(v, 0, v.length-1);
      System.out.println("Depois do reverse: " + Arrays.toString(v));
   }
}
  2. Capicuas.
    Usando como base o código da inversão, implemente e teste um método recursivo para saber se o array representa uma capicua (uma capicua é um número que é igual quando lido da direita para esquerda ou da esquerda para a direita).

Exercício 3) Flood Fill

  1. Verifique o seguinte código que permite executar a técnica de "flood fill" de forma recursiva. Compile, teste e verifique que percebe como o código está a funcionar. Note que precisa de dar input ao programa (um exemplo é fornecido na página com o código). Se o ficheiro com input se chamar floodfill.txt, uma maneira de executar o programa seria:

    java TestFloodFill < floodfill.txt.

    TestFloodFill.java

    // -----------------------------------------------------------
// Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
// https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed
// -----------------------------------------------------------
// Exemplo de flood fill
// (Pedro Ribeiro @DCC-FCUP)
// -----------------------------------------------------------

import java.util.Scanner;

public class TestFloodFill {
   static int rows;            // Numero de linhas
   static int cols;            // Numero de colunas   
   static char m[][];          // Matriz de celulas
   static boolean visited[][]; // Saber se uma dada posicao ja foi visitada

   // Tamanho da mancha que inclui posicao (y,x)
   static int t(int y, int x) {
      if (y<0 || y>=rows || x<0 || x>=cols) return 0; // Caso base: fora dos limites
      if (visited[y][x]) return 0;  // Caso base: celula ja visitada
      if (m[y][x] == '.') return 0; // Caso base: celula vazia
      int count = 1;        // celula nao vazia
      visited[y][x] = true; // marcar como visitada
      count += t(y-1, x);   // Adicionando celulas nao vizinhas
      count += t(y+1, x);
      count += t(y, x+1);
      count += t(y, x-1);
      return count;
   }
   
   // -----------------------------------------------------------
   
   public static void main(String[] args) {
      Scanner in = new Scanner(System.in);

      // Leitura de uma matriz de caracteres
      rows = in.nextInt();
      cols = in.nextInt();
      m = new char[rows][cols];
      visited = new boolean[rows][cols];
      for (int i=0; i<rows; i++)
         m[i] = in.next().toCharArray();

      // Teste do metodo t(y,x)
      System.out.printf("t(0,0) = %d\n", t(0,0));
      System.out.printf("t(2,5) = %d\n", t(2,5));
      System.out.printf("t(4,0) = %d\n", t(4,0));      
   }
   
}

    Exemplo de input manual (ver conteúdo do ficheiro floodfill.txt) 

    5 7
##.#...
.###...
.....##
.#...##
##.....
  2. Resolvendo um problema.
    Resolva o exercício [ED200] Contagem de Células e também submeter no Mooshak para testar a sua solução.

Exercício 4) Subconjuntos

  1. Verifique o seguinte código para gerar subconjuntos

    TestSets.java

    // -----------------------------------------------------------
// Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
// https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
// -----------------------------------------------------------
// Geracao de subconjuntos
// (Pedro Ribeiro @ DCC-FCUP)
// -----------------------------------------------------------

public class TestSets {
   
   // Escrever todos os subconjuntos do array v[]
   static void sets(int v[]) {
      // array de booleanos para representar o conjunto
      boolean used[] = new boolean[v.length];
      goSets(0, v, used); // chamar funcao recursiva
   }

   // Gera todos os subconjuntos a partir da posicao 'cur'
   static void goSets(int cur, int v[], boolean used[]) {
      if (cur == v.length) {  // Caso base: terminamos o conjunto
         // Escrever conjunto
         System.out.print("Set:");
         for (int i=0; i<v.length; i++) 
            if (used[i]) System.out.print(" " + v[i]);
         System.out.println();
      } else {                  // Se nao terminamos, continuar a gerar
         used[cur] = true;      // Subconjuntos que incluem o elemento actual
         goSets(cur+1, v, used);// Chamada recursiva
         used[cur] = false;     // Subconjuntos que nao incluem o el. actual
         goSets(cur+1, v, used);// Chamada recursiva
      }
   }

   // -----------------------------------------------------------
   
   public static void main(String[] args) {
      int v[] = {2,4,6,8}; // Inicializacao de array

      sets(v);
   }
}
  2. Resolvendo um problema.
    Resolva o exercício [ED201] PlayList e também submeter no Mooshak para testar a sua solução.

Exercício 5) Permutações

  1. Verifique o seguinte código que gera todas as permutações de um dado array.

    TestPerm.java

    // -----------------------------------------------------------
// Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
// https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
// -----------------------------------------------------------
// Geracao de permutacoes
// (Pedro Ribeiro @ DCC-FCUP)
// -----------------------------------------------------------

public class TestPerm {
    // Escrever todos as permutacoes do array v[]
    static void permutations(int v[]) {
    boolean used[] = new boolean[v.length]; // $i$ esta na permutacao?
    int perm[] = new int[v.length];         // permutacao actual
    goPerm(0, v, used, perm); // chamar funcao recursiva
    }
    // Gera todos os subconjuntos a partir da posicao 'cur'
    static void goPerm(int cur, int v[], boolean used[], int perm[]) {
    if (cur == v.length) {  // Caso base: terminamos a permutacao
        for (int i=0; i<v.length; i++) // Escrever a permutacao
	System.out.print(v[perm[i]] + " ");
	    System.out.println();
	} else { // Se nao terminamos, continuar a gerar
	    for (int i=0; i<v.length; i++) // Tentar todos os elementos
	    if (!used[i]) { 
	        used[i] = true; perm[cur] = i;
	        goPerm(cur+1, v, used, perm);
	        used[i] = false;
	    }
	    }
    }   

   // -----------------------------------------------------------
   
   public static void main(String[] args) {
       int v[] = {2,4,6,8}; // Inicializacao de array

      permutations(v);
   }
}
  2. Resolvendo um problema.
    Resolva o exercício [ED202] Procurando Pokemons e também submeter no Mooshak para testar a sua solução.

Baseado em material didático de Pedro Ribeiro (DCC-FCUP)