Recursion is a programming technique in which a function solves a problem by calling itself on a smaller version of the same problem.
It is one of the most important ideas in algorithms because many problems naturally break into smaller subproblems. Sorting, tree traversal, divide and conquer, backtracking, and dynamic programming all rely heavily on recursive thinking.
Every recursive solution must contain two essential parts:
n can be solved using the answer for size n - 1, n / 2, or some other smaller input, recursion may be a natural fit.
When a recursive function is called:
int recursiveFunction(int n) {
if (base condition) {
return base value;
}
return recursiveFunction(smaller input);
}A correct recursive solution must always move toward the base case. If it does not, the recursion will never stop.
The factorial of a number is defined as:
n! = n * (n - 1)!, with 0! = 1 and 1! = 1.
public class Factorial {
static long factorial(int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
public static void main(String[] args) {
System.out.println(factorial(5));
}
}This works because the problem size decreases from n to n - 1 until the base case is reached.
The Fibonacci sequence is defined as:
F(n) = F(n - 1) + F(n - 2), with F(0) = 0 and F(1) = 1.
public class Fibonacci {
static long fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
System.out.println(fib(8));
}
}Although this definition is simple, naive recursive Fibonacci is inefficient because it recomputes the same subproblems many times.
This is a classic recursive problem where we move n disks from one rod to another using an auxiliary rod.
public class TowerOfHanoi {
static void solve(int n, char source, char destination, char auxiliary) {
if (n == 1) {
System.out.println("Move disk 1 from " + source + " to " + destination);
return;
}
solve(n - 1, source, auxiliary, destination);
System.out.println("Move disk " + n + " from " + source + " to " + destination);
solve(n - 1, auxiliary, destination, source);
}
}Every recursive call creates a new stack frame on the call stack. That frame stores local variables, parameters, and the return address.
| Step | Current Call | What Happens |
|---|---|---|
| 1 | factorial(4) | Needs factorial(3) |
| 2 | factorial(3) | Needs factorial(2) |
| 3 | factorial(2) | Needs factorial(1) |
| 4 | factorial(1) | Base case returns 1 |
| 5 | factorial(2) | Returns 2 * 1 = 2 |
| 6 | factorial(3) | Returns 3 * 2 = 6 |
| 7 | factorial(4) | Returns 4 * 6 = 24 |
This is why recursion uses extra memory. Deep recursion may cause a stack overflow if the call depth becomes too large.
A recurrence relation expresses the running time of a recursive algorithm in terms of smaller inputs.
| Algorithm | Recurrence | Time Complexity |
|---|---|---|
| Factorial | T(n) = T(n - 1) + O(1) | O(n) |
| Binary Search | T(n) = T(n / 2) + O(1) | O(log n) |
| Merge Sort | T(n) = 2T(n / 2) + O(n) | O(n log n) |
| Naive Fibonacci | T(n) = T(n - 1) + T(n - 2) + O(1) | O(2^n) roughly |
| Tower of Hanoi | T(n) = 2T(n - 1) + O(1) | O(2^n) |
Recursion can be classified based on how functions call each other.
| Type | Meaning | Example |
|---|---|---|
| Direct recursion | A function calls itself directly | factorial(n) calling factorial(n - 1) |
| Indirect recursion | Function A calls B, and B calls A | isEven() and isOdd() |
public class IndirectRecursion {
static boolean isEven(int n) {
if (n == 0) {
return true;
}
return isOdd(n - 1);
}
static boolean isOdd(int n) {
if (n == 0) {
return false;
}
return isEven(n - 1);
}
}A recursive function is called tail recursive when the recursive call is the last operation in the function. No extra work remains after the recursive call returns.
public class TailRecursion {
static long factorialTail(int n, long acc) {
if (n <= 1) {
return acc;
}
return factorialTail(n - 1, n * acc);
}
}Some languages or compilers can optimize tail recursion into iteration, but you should not assume that every language always does this.
| Aspect | Recursion | Iteration |
|---|---|---|
| Readability | Often cleaner for recursive structures | Often clearer for simple loops |
| Memory | Uses call stack | Usually uses constant stack space |
| Performance | May have function call overhead | Often slightly faster |
| Best for | Trees, divide and conquer, backtracking | Simple counting and traversal |
Explore 500+ free tutorials across 20+ languages and frameworks.