Recursão Java

Recursão Java

A recursão é a técnica de fazer uma função chamar ela mesma. Esta técnica fornece uma maneira de quebrar problemas complicados em problemas simples que são mais fáceis de resolver.

A recursão pode ser um pouco difícil de entender. A melhor maneira de descobrir como funciona é experimentando.

Exemplo de recursão

Adicionar dois números é fácil de fazer, mas adicionar um intervalo de números é mais complicado. No exemplo a seguir, a recursão é usada para adicionar um intervalo de números, dividindo-o na simples tarefa de adicionar dois números:

public class Main {
  public static void main(String[] args) {
    int result = sum(10);
    System.out.println(result);
  }
  public static int sum(int k) {
    if (k > 0) {
      return k + sum(k - 1);
    } else {
      return 0;
    }
  }
}

Exemplo explicado

Quando a sum()função é chamada, ela adiciona parâmetro kà soma de todos os números menores que ke retorna o resultado. Quando k se torna 0, a função retorna apenas 0. Ao executar, o programa segue os seguintes passos:

Como a função não chama a si mesma quando ké 0, o programa para por aí e retorna o resultado.

Condição de parada

Assim como os loops podem se deparar com o problema do loop infinito, as funções recursivas podem se deparar com o problema da recursão infinita. Recursão infinita é quando a função nunca para de chamar a si mesma. Toda função recursiva deve ter uma condição de parada, que é a condição em que a função para de chamar a si mesma. No exemplo anterior, a condição de parada é quando o parâmetro kse torna 0.

É útil ver uma variedade de exemplos diferentes para entender melhor o conceito. Neste exemplo, a função adiciona um intervalo de números entre um início e um fim. A condição de parada para esta função recursiva é quando end não é maior que start :

public class Main {
  public static void main(String[] args) {
    int result = sum(5, 10);
    System.out.println(result);
  }
  public static int sum(int start, int end) {
    if (end > start) {
      return end + sum(start, end - 1);
    } else {
      return end;
    }
  }
}