Java Recursion
In this page:
Introduction to Recursion
Recursion is when a method calls itself to break a problem into smaller versions of the same problem, similar to how a loop repeats but driven by the call stack instead of a loop counter. Every recursive method needs a base case, or it will call itself forever until the JVM throws a StackOverflowError.
Example: Introduction to Recursion
public class Main {
static void countDown(int n) {
if (n == 0) {
System.out.println("Done");
return;
}
System.out.println(n);
countDown(n - 1);
}
public static void main(String[] args) {
countDown(3);
}
}Login to try C/C++/Java/PHP code in the editor
Base Case and Recursive Case
The base case is the simplest version of the problem, the point where the method stops calling itself and just returns a value directly. The recursive case handles everything else: it does a small piece of work, then calls the method again with arguments that move closer to the base case.
Example: Base Case and Recursive Case
public class Main {
static int factorial(int n) {
if (n == 0) { // base case
return 1;
}
return n * factorial(n - 1); // recursive case
}
public static void main(String[] args) {
System.out.println(factorial(5));
}
}Login to try C/C++/Java/PHP code in the editor
Fibonacci Series
The Fibonacci sequence, where each number is the sum of the two before it, is a classic recursion example because the definition is naturally recursive: fib(n) = fib(n-1) + fib(n-2). A naive recursive implementation is elegant but recomputes the same values many times, which is why it's often used to introduce memoization afterward.
Example: Fibonacci Series
public class Main {
static int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
for (int i = 0; i < 6; i++) {
System.out.print(fib(i) + " ");
}
}
}Login to try C/C++/Java/PHP code in the editor
Recursive Logic Controls
Poorly designed recursion can blow the call stack or never terminate, so always verify that every recursive call passes arguments that genuinely shrink toward the base case. Tracing a few calls by hand (or drawing the call tree) is the fastest way to catch a recursion that doesn't actually converge.
Example: Recursive Logic Controls
public class Main {
static int sumDown(int n) {
if (n <= 0) {
return 0;
}
return n + sumDown(n - 1); // n shrinks toward the base case each call
}
public static void main(String[] args) {
System.out.println(sumDown(4));
}
}Login to try C/C++/Java/PHP code in the editor
Iteration vs Recursion
Any recursive algorithm can be rewritten as a loop using an explicit stack or accumulator variables, and iteration is usually faster and uses constant stack space instead of growing one stack frame per call. Recursion is still preferred when it makes the code dramatically clearer, such as tree traversal or divide-and-conquer algorithms.
Example: Iteration vs Recursion
public class Main {
static int factorialRecursive(int n) {
return n == 0 ? 1 : n * factorialRecursive(n - 1);
}
static int factorialIterative(int n) {
int result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
public static void main(String[] args) {
System.out.println(factorialRecursive(5));
System.out.println(factorialIterative(5));
}
}Login to try C/C++/Java/PHP code in the editor
Chapter Quiz — Complete all 10 topics to unlock
0/10 topics done
Complete these topics first: