Pensamento Computacional - Tópicos Adicionais

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, é:

  $5!=5\times 4\times 3\times 2\times 1$

Por sua vez, podemos reescrever da seguinte forma:

  $5!=5\times 4!$
  $4!=4\times 3!$
  $3!=3\times 2!$
  $2!=2\times 1!$
  $1!=1$

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)
            return n * calcularFatorial(n - 1);
        }
    }
}

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.