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
recursionHá 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.