Vamos tentar com algo mais simples (a essência de criar algoritmos recursivos é partir do caso mais simples e ver se, por indução, você consegue resolver o caso complicado.
Vamos somar um vetor unidimensional recursivamente.
Como sabemos, de antemão, que não é fácil criar listas com um elemento a menos em Java, vamos então usar uma outra abordagem.
A primeira coisa é definir os casos extremos e mais simples:
- A soma de um vetor vazio é zero.
- A soma de um vetor de um elemento é esse próprio elemento, ou seja, vetor[0].
A segunda coisa é definir o que fazer no caso de indução (ou seja, você tem um problema menor e quer saber como resolver o problema maior a partir dele).
No caso de um vetor:
- A soma de um vetor que vai de 0 até N - 1 é igual ao primeiro elemento mais a soma do vetor que vai de 1 até N - 1.
Isso seria algo como:
class SomaRecursiva {
public static int soma (int[] vetor, int inicio) {
if (inicio >= vetor.length)
return 0; // "a soma de um vetor vazio é zero"
else if (inicio - 1 == vetor.length)
return vetor[inicio]; // a soma de um vetor de um elemento é o próprio elemento"
else
return vetor[inicio] + soma (vetor, inicio + 1);
}
public static void main (String[] args) {
int[] vetor = {1, 2, 3, 4};
System.out.println (soma (vetor, 0)); // deve resultar 10
}
}
Você viu que, como em Java não é trivial representar uma lista que tem um elemento a menos, eu tive de passar um parâmetro chamado “inicio” que indica a partir de onde eu quero começar a olhar o vetor. Não consegui um mapeamento muito direto do algoritmo em si para a linguagem.
E é por isso que certas coisas são meio difíceis de representar em Java, porque ela não é uma linguagem muito adequada para representar essas relações recursivas.
