Java Recursion
In this page:
static returnType methodName(dataType n) {
if (baseCondition) {
return baseValue;
}
return methodName(smallerN);
}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
// Define the class Main
public class Main {
static void countDown(int n) {
// Check whether n == 0
if (n == 0) {
// Print a line to the console
System.out.println("Done");
return;
}
// Print a line to the console
System.out.println(n);
countDown(n - 1);
}
// Program entry point: the JVM starts running here
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
// Define the class Main
public class Main {
static int fib(int n) {
// Check whether n <= 1
if (n <= 1) {
// Send n back to the caller
return n;
}
// Send fib(n - 1) + fib(n - 2) back to the caller
return fib(n - 1) + fib(n - 2);
}
// Program entry point: the JVM starts running here
public static void main(String[] args) {
// Loop: repeat while the condition holds
for (int i = 0; i < 6; i++) {
// Print to the console without a newline
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
// Define the class Main
public class Main {
static int factorialRecursive(int n) {
return n == 0 ? 1 : n * factorialRecursive(n - 1);
}
static int factorialIterative(int n) {
// Declare result and set it to 1
int result = 1;
// Loop: repeat while the condition holds
for (int i = 2; i <= n; i++) {
result *= i;
}
// Send result back to the caller
return result;
}
// Program entry point: the JVM starts running here
public static void main(String[] args) {
// Print a line to the console
System.out.println(factorialRecursive(5));
// Print a line to the console
System.out.println(factorialIterative(5));
}
}Login to try C/C++/Java/PHP code in the editor
- Forgetting the base case, which causes
StackOverflowError. - Not moving toward the base case, so the recursion never ends.
- Using recursion for large inputs where a loop would be faster and safer.
Chapter Quiz — Complete all 10 topics to unlock
0/10 topics done
Complete these topics first: