CKTIS / Java
Recursion and the call stack
Recursion and the call stack: Recursion occurs when a method calls itself directly or indirectly; every invocation owns a stack frame, so the algorithm needs a base case and progress.
Version: Java SE 21 (JLS and Java SE API); examples verified on the repository Java runtime
Syntax
recursionRecursion occurs when a method calls itself directly or indirectly; every invocation owns a stack frame, so the algorithm needs a base case and progress.
Use it for bounded trees and divide-and-conquer; replace deep linear traversal with iteration and a Deque.
Java does not guarantee tail-call optimization, so a logically correct but deep recursion can end with StackOverflowError.
Empty input must reach the base case, while a cyclic graph needs a visited set or recursion will not terminate.
Two base cases terminate the calls: factorial(5) prints 120, and the recursive Euclidean gcd(48,18) prints 6.
Examples
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));
}
}
Result
120 6
Two base cases terminate the calls: factorial(5) prints 120, and the recursive Euclidean gcd(48,18) prints 6.