Java: Recursividade

Afluentes: Estrutura de Dados

O que é recursividade?

Quando uma função chama a si mesma, dizemos que é uma função recursiva. Alguns tipos de algoritmos podem utilizar de forma bastante eficaz este recurso. Contudo, temos que tomar muito cuidado ao utilizá-lo.

Toda vez que chamamos uma função, o programa aloca os recursos necessário para executá-la, incluindo ponteiros, variáveis, etc. Se esta função chama outra, o programa manterá esta na memória e irá alocar os recursos para a função que está sendo chamada por esta.

Uma função recursiva não é diferente de qualquer função quanto à alocação de memória, ou seja, a cada chamada recursiva, estaremos alocando mais espaço para poder conter os recursos necessários, é como se estivéssemos chamando qualquer outra função.

Por isso, é de essencial que haja um ponto de parada na função recursiva para que ela não fique sendo chamada infinitamente. Além disso, temos que cuidar muito com a utilização da memória. Há um limite e, se esse limite for extrapolado, o programa vai abortar.

Exemplo

Função para calcular o fatorial de um número.

 1import java.util.Scanner;
 2
 3class Recursivo {
 4    public static int fatorial(int n) {
 5        if (n > 0) {
 6            return n * Recursivo.fatorial(n - 1);
 7        }
 8        return 1;
 9    }
10    public static void main(String [] args) {
11        System.out.print("Valor: ");
12        Scanner scan = new Scanner(System.in);
13        int valor = scan.nextInt();
14        System.out.println("O fatorial de " + valor + " é " + Recursivo.fatorial(valor));
15        scan.close();
16    }
17}

Exercícios

1. Escreva uma função recursiva de nome soma() que recebe um numero inteiro positivo n como argumento e retorna a soma dos n primeiros números inteiros. Por exemplo, se a função recebe n = 5, deve retornar 15, pois 15 = 1 + 2 + 3 + 4 + 5.

2. Escreva um programa que utilize a função criada no exercício anterior.

3. Escreva uma função recursiva chamada potencia() que aceite dois argumentos inteiros positivos i e j. A função retorna o i elevado à potencia j; Por exemplo, potencial (2,3) é igual a 8.