Recursion Basics
What Is Recursion?
Recursion is a technique where a function calls itself to solve a smaller version of the same problem. The function keeps calling itself with progressively simpler inputs until it reaches a condition so simple that the answer is known directly — at which point it returns without calling itself again.
Problem: Calculate 5! (5 factorial = 5 × 4 × 3 × 2 × 1) Recursive insight: 5! = 5 × 4! 4! = 4 × 3! 3! = 3 × 2! 2! = 2 × 1! 1! = 1 × 0! 0! = 1 ← known directly — no smaller version exists Working back up: 1! = 1 × 1 = 1 2! = 2 × 1 = 2 3! = 3 × 2 = 6 4! = 4 × 6 = 24 5! = 5 × 24 = 120
The function "delegates" part of the work to a smaller version of itself and uses the result to compute its own answer.
The Two Essential Parts
Every correct recursive function has exactly two parts:
┌─────────────────────────────────────────────────────────┐ │ BASE CASE │ │ • Condition that is simple enough to answer directly │ │ • Returns without making any further recursive calls │ │ • MUST be reached eventually — prevents infinite loops │ └─────────────────────────────────────────────────────────┘ ┌─────────────────────────────────────────────────────────┐ │ RECURSIVE CASE │ │ • Calls the function again with a SMALLER input │ │ • Smaller means: closer to the base case │ │ • Uses the result of that call to build the answer │ └─────────────────────────────────────────────────────────┘
If either part is missing or wrong, the function is broken:
- ›No base case → infinite recursion → stack overflow
- ›No progress toward base case → infinite recursion → stack overflow
- ›Base case but no recursive case → the function just returns the base case value for every input (not useful)
First Recursive Function: Factorial
1public class Factorial {
2
3 // n! = n × (n-1)! with base case 0! = 1
4 public static long factorial(int n) {
5 // BASE CASE: simplest version — answer is known
6 if (n == 0) {
7 return 1;
8 }
9
10 // RECURSIVE CASE: call with a smaller input (n-1)
11 // Use the result to compute this level's answer
12 return n * factorial(n - 1);
13 }
14
15 public static void main(String[] args) {
16 System.out.println(factorial(0)); // 1
17 System.out.println(factorial(1)); // 1
18 System.out.println(factorial(5)); // 120
19 System.out.println(factorial(10)); // 3628800
20 }
21}Output:
1
1
120
3628800
How It Executes: Unwinding
When factorial(5) is called, here is what actually happens step by step:
GOING DOWN (building up pending work): factorial(5) waits for → factorial(4) factorial(4) waits for → factorial(3) factorial(3) waits for → factorial(2) factorial(2) waits for → factorial(1) factorial(1) waits for → factorial(0) factorial(0) → returns 1 ← base case reached, no more calls COMING BACK UP (resolving pending work): factorial(1) = 1 × 1 = 1 ← uses factorial(0)'s result factorial(2) = 2 × 1 = 2 ← uses factorial(1)'s result factorial(3) = 3 × 2 = 6 ← uses factorial(2)'s result factorial(4) = 4 × 6 = 24 ← uses factorial(3)'s result factorial(5) = 5 × 24 = 120 ← final answer
The function makes ALL the recursive calls first (going down), then resolves them in reverse order (coming back up). This unwinding pattern is central to understanding recursion.
Second Example: Sum of Array
1public class ArraySum {
2
3 // Sum of arr[lo..hi] recursively
4 public static int sum(int[] arr, int lo, int hi) {
5 // BASE CASE: single element
6 if (lo == hi) return arr[lo];
7
8 // RECURSIVE CASE: sum of left half + sum of right half
9 int mid = lo + (hi - lo) / 2;
10 return sum(arr, lo, mid) + sum(arr, mid + 1, hi);
11 }
12
13 // Simpler version: sum of first n elements
14 public static int sumN(int[] arr, int n) {
15 if (n == 0) return 0; // Base case
16 return arr[n - 1] + sumN(arr, n - 1); // Recursive case
17 }
18
19 public static void main(String[] args) {
20 int[] arr = {1, 2, 3, 4, 5};
21
22 System.out.println(sum(arr, 0, 4)); // 15
23 System.out.println(sumN(arr, arr.length)); // 15
24 System.out.println(sumN(arr, 0)); // 0 — empty sum
25 }
26}Output:
15
15
0
Recursion vs Iteration — Same Result, Different Structure
Most recursive problems can also be solved iteratively. Understanding both helps you choose the right one.
1public class RecursionVsIteration {
2
3 // Recursive factorial
4 public static long factRecursive(int n) {
5 if (n == 0) return 1;
6 return n * factRecursive(n - 1);
7 }
8
9 // Iterative factorial
10 public static long factIterative(int n) {
11 long result = 1;
12 for (int i = 1; i <= n; i++) {
13 result *= i;
14 }
15 return result;
16 }
17
18 // Recursive sum of 1..n
19 public static int sumRecursive(int n) {
20 if (n == 0) return 0;
21 return n + sumRecursive(n - 1);
22 }
23
24 // Iterative sum of 1..n
25 public static int sumIterative(int n) {
26 int total = 0;
27 for (int i = 1; i <= n; i++) {
28 total += i;
29 }
30 return total;
31 }
32
33 public static void main(String[] args) {
34 System.out.println(factRecursive(5) + " == " + factIterative(5)); // 120 == 120
35 System.out.println(sumRecursive(10) + " == " + sumIterative(10)); // 55 == 55
36 }
37}Output:
120 == 120
55 == 55
When to Choose Recursion vs Iteration
CHOOSE RECURSION WHEN:
✓ The problem has natural recursive structure
(trees, graphs, divide-and-conquer, nested data)
✓ The recursive solution is significantly cleaner/shorter to read
✓ You need to explore all branches (backtracking, DFS)
✓ The depth of nesting is unknown at compile time
CHOOSE ITERATION WHEN:
✓ The problem is a simple linear repetition
✓ Stack overflow is a concern (very deep recursion, n > 10,000)
✓ Performance-critical code (function call overhead matters)
✓ Tail recursion would be needed — iteration is cleaner
Both are computationally equivalent — the choice is about clarity and safety.
Prefer whichever makes the code easier to understand and maintain.
Three More Classic Examples
Power Function
2^8 = 2 × 2^7 Recursive structure is clear:
= 2 × 2 × 2^6 power(x, n) = x × power(x, n-1)
... Base case: power(x, 0) = 1
= 2^1 × 2^0 = 2 × 1 = 256
1public class Power {
2 public static double power(double x, int n) {
3 if (n == 0) return 1; // Base case: x⁰ = 1
4 return x * power(x, n - 1); // Recursive case
5 }
6
7 public static void main(String[] args) {
8 System.out.println(power(2, 8)); // 256.0
9 System.out.println(power(3, 4)); // 81.0
10 System.out.println(power(5, 0)); // 1.0
11 }
12}Fibonacci Number
fib(n) = fib(n-1) + fib(n-2) with fib(0)=0, fib(1)=1
fib(6) = fib(5) + fib(4)
= (fib(4)+fib(3)) + (fib(3)+fib(2))
...
= 8
1public class Fibonacci {
2 public static int fib(int n) {
3 if (n <= 1) return n; // Base cases: fib(0)=0, fib(1)=1
4 return fib(n - 1) + fib(n - 2); // Recursive case
5 }
6
7 public static void main(String[] args) {
8 for (int i = 0; i <= 8; i++) {
9 System.out.print(fib(i) + " ");
10 }
11 // 0 1 1 2 3 5 8 13 21
12 }
13}Reverse a String
1public class ReverseString {
2 public static String reverse(String s) {
3 if (s.isEmpty()) return s; // Base case
4 return reverse(s.substring(1)) + s.charAt(0); // Recursive case
5 }
6
7 public static void main(String[] args) {
8 System.out.println(reverse("hello")); // olleh
9 System.out.println(reverse("abcde")); // edcba
10 System.out.println(reverse("")); // ""
11 }
12}Output:
olleh
edcba
Reading Recursive Code: A Method
When you encounter a recursive function, read it in this order:
Step 1: Find the BASE CASE(s) What is the simplest input? What does the function return? This tells you the "anchor" of the solution. Step 2: Read the RECURSIVE CASE What smaller problem does it delegate to? How does it use the result of that smaller problem? Step 3: TRUST the recursive call Do not trace every nested call manually. Assume the recursive call returns the correct answer for smaller input. Focus only on how THIS level uses that answer. Step 4: VERIFY with the smallest non-trivial example Trace factorial(2): base case? No (2≠0). Recursive: 2 × factorial(1). factorial(1): base? No (1≠0). Recursive: 1 × factorial(0). factorial(0): base? YES. Return 1. Unwind: 1×1=1, 2×1=2. ✓ This "trust the recursion" technique is the key skill. Trying to trace the full call tree of factorial(10) mentally is unnecessary and confusing. Trust that factorial(n-1) returns (n-1)!.
Common Patterns in Recursive Problems
REDUCE AND CONQUER (linear recursion): Problem: compute f(n) Method: solve f(n-1), use it to compute f(n) Examples: factorial, Fibonacci, sum, reverse string DIVIDE AND CONQUER (branching recursion): Problem: compute f(arr[lo..hi]) Method: solve f(left half) and f(right half), merge results Examples: merge sort, binary search, sum of array halves TREE RECURSION: Problem: explore all paths or choices Method: branch at each decision point, recurse into each branch Examples: Fibonacci (two branches), tower of Hanoi, generate permutations ACCUMULATOR PATTERN: Problem: collect results across all recursive calls Method: pass an accumulator parameter that grows with each call Examples: sum with running total, path building in tree traversal
Interview Questions
Q: What are the two essential parts of a recursive function?
The base case and the recursive case. The base case is the condition where the problem is simple enough to answer directly without further recursion. The recursive case calls the function with a smaller or simpler input, using the result to compute the current level's answer. Without a base case, recursion is infinite. Without a recursive case that makes progress toward the base case, recursion is also infinite.
Q: How does recursion differ from iteration?
Both express repetition, but through different mechanisms. Iteration uses explicit control flow (for, while) to repeat a block of code. Recursion expresses repetition by having a function call itself with modified inputs. Recursion can be more natural for problems with inherent sub-structure (trees, divide-and-conquer), while iteration is typically more efficient for simple linear repetition since it avoids function call overhead and stack frame allocation.
Q: What causes a stack overflow in recursive code?
A stack overflow occurs when the call stack exhausts its memory. Each function call — recursive or otherwise — creates a stack frame storing local variables, parameters, and the return address. Recursive calls nest these frames. If recursion is too deep (typically more than 1,000–10,000 levels depending on the language and frame size) or if there is no base case causing infinite recursion, the stack exhausts its allocated memory and throws a StackOverflowError (Java), RecursionError (Python), or causes a segfault (C++).
FAQs
Can every iterative function be rewritten recursively and vice versa?
Yes — they are computationally equivalent (both are Turing-complete). Any iterative program can be expressed recursively, and any recursive program can be expressed iteratively (using an explicit stack if needed to simulate the call stack). The question is always which form is clearer for a given problem. Tree traversal is cleaner recursive; summing an array is cleaner iterative.
Is recursion always slower than iteration?
Not always, but usually slightly slower due to function call overhead — each recursive call allocates a stack frame (typically 100-200 bytes), pushes parameters and the return address, and pops them on return. For tight loops over millions of iterations, this overhead adds up. Modern compilers can sometimes optimise tail-recursive calls into iteration (tail call optimisation), eliminating the overhead entirely. For most problems at typical interview scale, the overhead is negligible.
What is the maximum recursion depth?
It varies by language and system:
- ›Python default: 1,000 (configurable via
sys.setrecursionlimit()) - ›Java: ~5,000–10,000 (depends on stack frame size, configurable via
-Xss) - ›C++: ~10,000–50,000 (depends on OS stack size, ~1-8 MB default)
- ›JavaScript (V8): ~10,000–15,000
For practical algorithm problems, recursion depth is typically O(log n) for divide-and-conquer or O(n) for linear recursion — usually well within limits for reasonable input sizes.
Summary
Recursion is a function calling itself to solve a smaller version of the same problem.
Every recursive function needs:
- ›Base case — the simplest input where the answer is known directly; stops the recursion
- ›Recursive case — calls the function with a smaller input, moves toward the base case
Execution pattern:
- ›Going down — each call creates a stack frame and delegates to a smaller version
- ›Coming back up — each call receives the result from the smaller version and computes its own answer
Key skill — trust the recursion: assume the recursive call returns the correct answer for the smaller input. Focus only on how the current level uses that answer. Do not trace the full call tree mentally.
Three classic examples:
- ›Factorial:
f(n) = n × f(n-1), basef(0) = 1 - ›Fibonacci:
f(n) = f(n-1) + f(n-2), basef(0) = 0, f(1) = 1 - ›Reverse string:
f(s) = f(s[1:]) + s[0], basef("") = ""
When to choose recursion over iteration: problems with natural tree/graph structure, divide-and-conquer algorithms, and problems where the depth of nesting is unknown at compile time.
In the next topic, you will explore How Recursion Works — the step-by-step execution model, stack frame creation, parameter passing, and return value propagation with detailed visual traces.
What is the minimum requirement for a function to be recursive?