Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / Java

Recursão e stack de chamadas

Recursão e stack de chamadas: Há recursão quando um método chama a si próprio direta ou indiretamente; cada chamada tem uma frame de stack, logo exige caso base e progresso.

Versão: Java SE 21 (JLS and Java SE API); examples verified on the repository Java runtime

Sintaxe

recursion

Há recursão quando um método chama a si próprio direta ou indiretamente; cada chamada tem uma frame de stack, logo exige caso base e progresso.

Usa-a em árvores limitadas e divisão e conquista; troca um percurso linear profundo por iteração com Deque.

Java não garante otimização de chamadas de cauda, portanto recursão correta mas profunda pode terminar em StackOverflowError.

A entrada vazia deve atingir o caso base e um grafo cíclico requer um conjunto de visitados para terminar.

Dois casos base terminam as chamadas: factorial(5) escreve 120 e o algoritmo de Euclides recursivo gcd(48,18) escreve 6.

Exemplos

public class Main {
    static int factorial(int n) {
        return n <= 1 ? 1 : n * factorial(n - 1);
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) {
        System.out.println(factorial(5));
        System.out.println(gcd(48, 18));
    }
}

Resultado

120
6

Dois casos base terminam as chamadas: factorial(5) escreve 120 e o algoritmo de Euclides recursivo gcd(48,18) escreve 6.

Fontes