Java Recursion
Methods that call themselves
🔄 What is Recursion?
Recursion occurs when a method calls itself to solve smaller versions of the same problem. It's a powerful technique for breaking complex problems into simpler, manageable pieces.
// Simple recursive method
public static int countdown(int n) {
if (n <= 0) return 0; // Base case
System.out.println(n);
return countdown(n - 1); // Recursive call
}
Output for countdown(3):
3
2
1
Key Recursion Concepts
Base Case
Condition that stops the recursion
if (n <= 0) return 0;Recursive Call
Method calling itself with modified input
return method(n - 1);Problem Reduction
Each call works on a smaller problem
factorial(5) → factorial(4)
factorial(4) → factorial(3)Call Stack
Methods stack up until base case
method(3)
method(2)
method(1)🔹 Simple Recursion Example
A basic recursive method to understand the concept:
public class RecursionBasics {
// Recursive method to print numbers from n down to 1
public static void printNumbers(int n) {
// Base case: stop when n is 0 or less
if (n <= 0) {
System.out.println("Done!");
return;
}
// Print current number
System.out.println("Number: " + n);
// Recursive call with smaller value
printNumbers(n - 1);
}
public static void main(String[] args) {
System.out.println("Counting down from 5:");
printNumbers(5);
}
}Output:
Counting down from 5:
Number: 5
Number: 4
Number: 3
Number: 2
Number: 1
Done!
🔹 Factorial Example
Classic recursion example - calculating factorial (n!):
public class FactorialExample {
// Recursive factorial calculation
// factorial(5) = 5 * 4 * 3 * 2 * 1 = 120
public static int factorial(int n) {
// Base case: factorial of 0 or 1 is 1
if (n <= 1) {
return 1;
}
// Recursive case: n * factorial(n-1)
return n * factorial(n - 1);
}
public static void main(String[] args) {
int number = 5;
int result = factorial(number);
System.out.println("Factorial of " + number + " is: " + result);
// Show step by step
System.out.println("\nStep by step:");
System.out.println("5! = 5 * 4 * 3 * 2 * 1 = " + factorial(5));
System.out.println("4! = 4 * 3 * 2 * 1 = " + factorial(4));
System.out.println("3! = 3 * 2 * 1 = " + factorial(3));
}
}Output:
Factorial of 5 is: 120
Step by step:
5! = 5 * 4 * 3 * 2 * 1 = 120
4! = 4 * 3 * 2 * 1 = 24
3! = 3 * 2 * 1 = 6
🔹 Sum of Numbers
Using recursion to calculate the sum of numbers from 1 to n:
public class SumExample {
// Recursive method to calculate sum from 1 to n
// sum(5) = 5 + 4 + 3 + 2 + 1 = 15
public static int sum(int n) {
// Base case: sum of 0 is 0
if (n <= 0) {
return 0;
}
// Recursive case: n + sum(n-1)
return n + sum(n - 1);
}
// Method to show the calculation process
public static void showCalculation(int n) {
System.out.println("Calculating sum from 1 to " + n + ":");
int result = sum(n);
System.out.println("Result: " + result);
}
public static void main(String[] args) {
showCalculation(5);
showCalculation(3);
showCalculation(10);
}
}Output:
Calculating sum from 1 to 5:
Result: 15
Calculating sum from 1 to 3:
Result: 6
Calculating sum from 1 to 10:
Result: 55
🔹 Recursion Rules
Important guidelines for writing recursive methods:
Recursion Requirements:
- Base Case: Must have a condition that stops the recursion
- Progress: Each recursive call must move closer to the base case
- Self-Call: Method must call itself with modified parameters
- Stack Limit: Too many recursive calls can cause stack overflow
// Template for recursive methods
public static returnType recursiveMethod(parameters) {
// Base case - when to stop
if (baseCondition) {
return baseValue;
}
// Recursive case - call itself with smaller problem
return recursiveMethod(modifiedParameters);
}