Método Recursivo - Conceitos Básicos

Método Recursivo

Em programação, a recursividade é um mecanismo útil e poderoso que permite a uma função chamar a si mesma direta ou indiretamente, ou seja, uma função é dita recursiva se ela contém pelo menos uma chamada explícita ou implícita a si própria.

Muito utilizado na Computação Gráfica e na resolução de problemas matemáticos. Como por exemplo: Sequência Fibonacci, Torre de Hanói, etc.

Para entendermos mais a fundo. Antes precisamos entender alguns Conceitos Básicos.

Caso Básico

Na recursividade, um método recursivo só é capaz de resolver apenas casos básicos. Se o método é chamado com um caso básico, ele retorna um resultado.

Ou seja, a ideia básica de um algoritmo recursivo consiste em diminuir sucessivamente o problema em um problema menor ou mais simples, até que o tamanho ou a simplicidade do problema reduzido permita resolvê-lo de forma direta, sem recorrer a si mesmo.

Caso o método chamado for um problema complexo , geralmente ele se divide em duas partes conceituais

• uma parte que o método sabe como fazer
• e uma parte que ele não sabe

Para tornar a recursão realizável, a última parte(parte que ele não sabe) deve assemelhar-se ao problema original, mas ser uma versão ligeiramente mais simples ou menor dele. Portanto, quando uma função recursiva é executada, ela geralmente se divide em subproblemas menores e mais simples até que um caso básico seja alcançado, que é a condição que permite que a função pare de chamar a si mesma e retorne um valor.

Em resumo, o caso básico é uma condição fundamental que define a base para a recursão, permitindo que a função retorne um valor e evitando que a recursão continue indefinidamente.

Exemplo:

Por exemplo, em um método recursivo que calcula o fatorial de um número, o caso básico seria quando o número é igual a 1 ou 0, pois o fatorial desses números é 1.

→ 1! = 1

→ 0! = 1 “o produto de todos os números positivos de 1 a 0 é igual a 1.”

class Recursivo {
     public static int fatorial(int n) {
         if (n > 0) {
             return n * Recursivo.fatorial(n - 1);
         }
        return 1; // caso básico
     }

Chamada Recursiva

Agora que temos um problema semelhante ao original de uma forma reduzida, o método chama um copia dele mesmo pra trabalhar no problema menor — isso é referido como c*hamada recursiva* e também é denominado passo de recursão.

O chamada recursiva normalmente inclui a instrução return uma vez que seu resultado será combinado com a parte do problema que o método sabia como resolver para formar um resultado que será passado de volta para o chamador original.

Recursiva indireta

Recursão indireta é um tipo de recursão em que um método recursivo chama outra método que por sua vez chama o primeiro método novamente. Isso é conhecido como uma chamada recursiva indireta ou recursão indireta.

Recursão vs. iteração

Tanto iteração como recursão se baseiam em uma estrutura de controle: A iteração utiliza uma instrução de repetição (por exemplo, for, while ou do…while), enquanto a recursão usa uma instrução de seleção (por exemplo, if, if…else ou switch).

Ambas envolvem repetição: a iteração utiliza explicitamente uma instrução de repetição, enquanto a recursão alcança a repetição por meio de repetidas chamadas de método. Tanto uma como outra envolvem um teste de terminação: A iteração termina quando a condição de continuação do loop falha, enquanto a recursão termina quando um caso básico é alcançado.

Tanto uma como outra podem ocorrer infinitamente: Ocorre um loop infinito com a iteração se o teste de continuação do loop nunca tornar-se falso, enquanto a recursão infinita ocorre se o passo de recursão não reduzir o problema sempre em uma maneira que convirja no caso básico, ou se o caso básico não for testado.

A recursão tem muitas negativas. Ela invoca repetidamente o mecanismo, e consequentemente o overhead, das chamadas de método. Essa repetição pode ser cara tanto em termos de tempo de processador como de espaço de memória. Cada chamada recursiva faz com que outra cópia do método (na verdade, somente as variáveis do método, armazenadas no registro de ativação) seja criada — esse conjunto de cópias pode consumir espaço considerável de memória. Visto que a iteração ocorre dentro de um método, as chamadas de método repetidas e a atribuição extra de memória são evitadas.

Referências:
https://www.ic.unicamp.br/~ripolito/peds/mc102z/material/Recursividade.PDF
DEITEL, P. J. Java como programar. 8.ed. São Paulo: Pearson Prentice Hall,2010. E-book.