Chapter 9

Recursion in Java
Java Data Structures & Algorithms Series

Recursion is a function that calls itself to solve a smaller version of the same problem. Every
recursive solution has two parts: a base case (stop condition) and a recursive case (smaller
subproblem). It is the foundation for Backtracking, Divide & Conquer, Trees, and DP.

1 The Recursion Mental Model

solve(problem):
if problem is trivial → return answer directly ← BASE CASE
else → solve(smaller problem) + combine result ← RECURSIVE CASE

Key: TRUST that solve(smaller) works correctly.

Your job is only to define the base case and the combination step.

⭐ Recursion Hypothesis: Assume the recursive call for a smaller input works perfectly.
You only need to define:
1. Base Case — when do we stop?
2. Combination — how do we use the smaller answer to build the full answer?

How the Call Stack Works

factorial(4)
└─ 4 × factorial(3)
└─ 3 × factorial(2)
└─ 2 × factorial(1)
└─ return 1 ← base case
└─ return 2×1 = 2
└─ return 3×2 = 6
└─ return 4×6 = 24

2 Pattern 1 — Classic Recursion Problems

Factorial

public static int factorial(int n) {

if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
// Time: O(n) | Space: O(n) stack frames
Fibonacci

public static int fib(int n) {

if (n <= 1) return n; // fib(0)=0, fib(1)=1
return fib(n-1) + fib(n-2);
}
// Time: O(2^n) — exponential without memoization!
// fib(5): fib(4)+fib(3) → fib(3)+fib(2)+fib(2)+fib(1) → many repeated calls

⚠️ Naive Fibonacci is O(2^n). Always add memoization (Day 13 — DP) for large n.
With memoization it drops to O(n) time and O(n) space.

Sum of Digits

public static int sumOfDigits(int n) {

if (n == 0) return 0;
return (n % 10) + sumOfDigits(n / 10);
}
// sumOfDigits(1234) = 4 + sumOfDigits(123)
// = 4 + 3 + sumOfDigits(12)
// = 4 + 3 + 2 + sumOfDigits(1)
// = 4 + 3 + 2 + 1 = 10 ✅

Fast Exponentiation — Power(x, n)

public static double power(double base, int exp) {

if (exp == 0) return 1;
if (exp < 0) return 1.0 / power(base, -exp);

double half = power(base, exp / 2); // compute half once

if (exp % 2 == 0) return half * half;
else return base * half * half;
}
// Time: O(log n) | Space: O(log n)
// Half the exponent each call — far better than O(n) repeated multiplication

3 Pattern 2 — Array Recursion

Reverse an Array

public static void reverseArray(int[] arr, int left, int right) {

if (left >= right) return; // base case
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
reverseArray(arr, left + 1, right - 1); // recurse on inner elements
}

Check if Array is Sorted

public static boolean isSorted(int[] arr, int i) {

if (i == [Link] - 1) return true; // single element → sorted
 if (arr[i] > arr[i+1]) return false; // violation found
return isSorted(arr, i + 1);
}

Linear Search — Return All Matching Indices

public static List<Integer> linearSearch(int[] arr, int target,

int i, List<Integer> result) {
if (i == [Link]) return result;
if (arr[i] == target) [Link](i);
return linearSearch(arr, target, i + 1, result);
}

4 Pattern 3 — String Recursion

Reverse a String

public static String reverse(String s) {

if ([Link]() <= 1) return s;
return reverse([Link](1)) + [Link](0);
}
// reverse("hello") = reverse("ello") + 'h'
// = reverse("llo") + 'e' + 'h'
// = ... = "olleh" ✅

Check Palindrome

public static boolean isPalindrome(String s, int left, int right) {

if (left >= right) return true; // base case
if ([Link](left) != [Link](right)) return false; // mismatch
return isPalindrome(s, left + 1, right - 1);
}

All Subsequences of a String

// "abc" → "", "a", "b", "c", "ab", "ac", "bc", "abc" (2^n total)
public static void subsequences(String s, int i, String current) {
if (i == [Link]()) {
[Link]([Link]() ? """" : current);
return;
}
subsequences(s, i + 1, current + [Link](i)); // include s[i]
subsequences(s, i + 1, current); // exclude s[i]
}
// Time: O(2^n) | Space: O(n) stack depth

5 Pattern 4 — Divide & Conquer

Merge Sort

public static void mergeSort(int[] arr, int left, int right) {

 if (left >= right) return; // base case: single element

int mid = left + (right - left) / 2;

mergeSort(arr, left, mid); // sort left half
mergeSort(arr, mid + 1, right); // sort right half
merge(arr, left, mid, right); // combine
}

private static void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;

while (i <= mid && j <= right)

temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];

[Link](temp, 0, arr, left, [Link]);

}
// Time: O(n log n) | Space: O(n)

Quick Sort

public static void quickSort(int[] arr, int low, int high) {

if (low >= high) return;
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}

private static int partition(int[] arr, int low, int high) {

int pivot = arr[high], i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}
}
int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp;
return i + 1;
}
// Time: O(n log n) avg, O(n²) worst | Space: O(log n)

6 Pattern 5 — Tower of Hanoi

Problem: Move N disks from source to destination using one auxiliary peg. Never place a larger disk
on a smaller one.

N=3 requires 2^3 - 1 = 7 moves minimum.

Observation: to move disk N, you must first move disks 1..N-1 to auxiliary.

public static void hanoi(int n, char src, char aux, char dest) {
if (n == 1) {
[Link]("Move disk 1: " + src + " → " + dest);
return;
}
 hanoi(n - 1, src, dest, aux); // move top n-1 disks to aux
[Link]("Move disk " + n + ": " + src + " → " + dest);
hanoi(n - 1, aux, src, dest); // move n-1 disks from aux to dest
}
// Time: O(2^n) | Space: O(n) | Minimum moves = 2^n - 1

// hanoi(3, 'A', 'B', 'C') output:

// Move disk 1: A → C
// Move disk 2: A → B
// Move disk 1: C → B
// Move disk 3: A → C
// Move disk 1: B → A
// Move disk 2: B → C
// Move disk 1: A → C

7 Pattern 6 — Flood Fill (Recursion on Grid)

Problem: Given a 2D image, paint all connected pixels of the same colour starting from (sr, sc).

image: After floodFill(1,1, newColor=2):

1 1 1 2 2 2
1 1 0 → 2 2 0
1 0 1 2 0 1

public static int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int oldColor = image[sr][sc];
if (oldColor != newColor)
fill(image, sr, sc, oldColor, newColor);
return image;
}

private static void fill(int[][] img, int r, int c, int old, int newC) {
if (r < 0 || r >= [Link]) return; // out of bounds
if (c < 0 || c >= img[0].length) return; // out of bounds
if (img[r][c] != old) return; // different colour

img[r][c] = newC;
fill(img, r+1, c, old, newC); // down
fill(img, r-1, c, old, newC); // up
fill(img, r, c+1, old, newC); // right
fill(img, r, c-1, old, newC); // left
}
// Time: O(m×n) | Space: O(m×n) recursion depth

8 Pattern 7 — Generate All Subsets (Power Set)

public static List<List<Integer>> subsets(int[] nums) {

List<List<Integer>> result = new ArrayList<>();
generateSubsets(nums, 0, new ArrayList<>(), result);
return result;
}

// Approach A — loop-based (adds snapshot at every recursive node)

private static void generateSubsets(int[] nums, int i,
List<Integer> current,
List<List<Integer>> result) {
 [Link](new ArrayList<>(current)); // snapshot here = valid subset
for (int j = i; j < [Link]; j++) {
[Link](nums[j]);
generateSubsets(nums, j + 1, current, result);
[Link]([Link]() - 1); // backtrack
}
}

// Approach B — include/exclude pattern

private static void subsets2(int[] nums, int i,
List<Integer> cur, List<List<Integer>> res) {
if (i == [Link]) { [Link](new ArrayList<>(cur)); return; }
[Link](nums[i]);
subsets2(nums, i+1, cur, res); // include nums[i]
[Link]([Link]()-1);
subsets2(nums, i+1, cur, res); // exclude nums[i]
}
// Time: O(2^n × n) | Space: O(n)

9 Pattern 8 — Generate All Permutations

public static List<List<Integer>> permute(int[] nums) {

List<List<Integer>> result = new ArrayList<>();
permuteHelper(nums, new ArrayList<>(), new boolean[[Link]], result);
return result;
}

// Approach A — used[] array

private static void permuteHelper(int[] nums, List<Integer> current,
boolean[] used, List<List<Integer>> result) {
if ([Link]() == [Link]) {
[Link](new ArrayList<>(current));
return;
}
for (int i = 0; i < [Link]; i++) {
if (used[i]) continue;
used[i] = true;
[Link](nums[i]);
permuteHelper(nums, current, used, result);
[Link]([Link]() - 1);
used[i] = false;
}
}

// Approach B — swap-based (in-place, more efficient)

public static void permuteSwap(int[] nums, int start, List<List<Integer>> result) {
if (start == [Link]) {
List<Integer> perm = new ArrayList<>();
for (int n : nums) [Link](n);
[Link](perm);
return;
}
for (int i = start; i < [Link]; i++) {
swap(nums, start, i);
permuteSwap(nums, start + 1, result);
swap(nums, start, i); // backtrack: restore
}
}
// Time: O(n! × n) | Space: O(n)
 10 Pattern 9 — Recursion with Return Values

Count All Subsequences with Sum = Target

public static int countSubsequences(int[] arr, int i, int target) {

if (target == 0) return 1; // found a valid subsequence
if (i == [Link] || target < 0) return 0; // exhausted / overshot

int include = countSubsequences(arr, i+1, target - arr[i]);

int exclude = countSubsequences(arr, i+1, target);
return include + exclude;
}

Find Any One Subsequence with Sum = Target

public static boolean findSubsequence(int[] arr, int i, int target,

List<Integer> result) {
if (target == 0) return true; // found — stop searching
if (i == [Link] || target < 0) return false;

[Link](arr[i]);
if (findSubsequence(arr, i+1, target - arr[i], result)) return true;
[Link]([Link]() - 1); // backtrack if not found
return findSubsequence(arr, i+1, target, result);
}
// Key: return true short-circuits — stops as soon as any answer is found

11 Recursion Tree Visualization

subsets([1,2,3]) — include/exclude tree:

[]
/ \
[1] []
/ \ / \
[1,2] [1] [2] []
/ \ / \ / \ / \
[1,2,3][1,2][1,3][1] [2,3][2][3] []

Total nodes = 2^n = 8 — each leaf is a valid subset ✅

permute([1,2]) — swap tree:

[1,2] [2,1]
start=0: swap(0,0) swap(0,1)
→ recurse start=1 each

12 Recursion vs Iteration

Factor Recursion Iteration

Readability ✅ Cleaner for tree / graph Verbose for deeply nested logic
problems
Stack space ❌ O(n) call stack frames ✅ O(1)
Stack overflow ❌ Risk for very deep n ✅ No risk
Tail recursion JVM does NOT optimize tail calls N/A
Best for Trees, graphs, divide & conquer Simple loops, array scans

13 Full Runnable Java Program

import [Link].*;

public class Chapter9Recursion {

public static void main(String[] args) {

[Link]("Factorial(5): " + factorial(5)); // 120
[Link]("Fib(7): " + fib(7)); // 13
[Link]("SumDigits(1234): " + sumOfDigits(1234)); // 10
[Link]("Power(2,10): " + power(2, 10)); // 1024.0

int[] arr = {1,2,3,4,5};

reverseArray(arr, 0, [Link]-1);
[Link]("Reversed: " + [Link](arr)); //
[5,4,3,2,1]
[Link]("Sorted check: " + isSorted(new int[]{1,2,3,4,5}, 0));
// true

[Link]("Reverse 'hello': " + reverse("hello")); // olleh

[Link]("Palindrome 'racecar': " +
isPalindrome("racecar", 0, 6)); // true

[Link]("Subsequences 'ab': ");

subsequences("ab", 0, ""); [Link]();

int[] arr2 = {5,2,8,1,9,3};

mergeSort(arr2, 0, [Link]-1);
[Link]("Merge Sorted: " + [Link](arr2)); //
[1,2,3,5,8,9]

int[] arr3 = {5,2,8,1,9,3};

quickSort(arr3, 0, [Link]-1);
[Link]("Quick Sorted: " + [Link](arr3)); //
[1,2,3,5,8,9]

[Link]("Hanoi(3):");
hanoi(3, 'A', 'B', 'C');

[Link]("Subsets [1,2,3]: " + subsets(new int[]{1,2,3}));

[Link]("Permutations [1,2,3]: " + permute(new int[]{1,2,3}));

[Link]("Count subseq sum=3: " +

countSubsequences(new int[]{1,2,1}, 0, 3)); // 2
}

static int factorial(int n) { return n<=1?1:n*factorial(n-1); }

static int fib(int n) { return n<=1?n:fib(n-1)+fib(n-2); }
static int sumOfDigits(int n){ return n==0?0:(n%10)+sumOfDigits(n/10); }
static double power(double b,int e){ if(e==0)return 1;if(e<0)return
1.0/power(b,-e);double h=power(b,e/2);return e%2==0?h*h:b*h*h; }

static void reverseArray(int[] a,int l,int r){ if(l>=r)return;int

t=a[l];a[l]=a[r];a[r]=t;reverseArray(a,l+1,r-1); }
static boolean isSorted(int[] a,int i){ if(i==[Link]-1)return
true;if(a[i]>a[i+1])return false;return isSorted(a,i+1); }

static String reverse(String s){ return [Link]()<=1?s:reverse([Link](1))

+[Link](0); }
static boolean isPalindrome(String s,int l,int r){ if(l>=r)return
true;if([Link](l)!=[Link](r))return false;return isPalindrome(s,l+1,r-1); }
static void subsequences(String s,int i,String cur){
if(i==[Link]()){[Link]("["+cur+"] ");return;}
subsequences(s,i+1,cur+[Link](i)); subsequences(s,i+1,cur);
}

static void mergeSort(int[] a,int l,int r){

if(l>=r)return; int mid=l+(r-l)/2; mergeSort(a,l,mid); mergeSort(a,mid+1,r);
int[] t=new int[r-l+1]; int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r) t[k++]=a[i]<=a[j]?a[i++]:a[j++];
while(i<=mid) t[k++]=a[i++]; while(j<=r) t[k++]=a[j++];
[Link](t,0,a,l,[Link]);
}
static void quickSort(int[] a,int lo,int hi){
if(lo>=hi)return; int p=partition(a,lo,hi); quickSort(a,lo,p-1);
quickSort(a,p+1,hi);
}
static int partition(int[] a,int lo,int hi){
int piv=a[hi],i=lo-1;
for(int j=lo;j<hi;j++) if(a[j]<=piv){i++;int t=a[i];a[i]=a[j];a[j]=t;}
int t=a[i+1];a[i+1]=a[hi];a[hi]=t; return i+1;
}

static void hanoi(int n,char s,char a,char d){

if(n==1){[Link]("Move disk 1: "+s+"→"+d);return;}
hanoi(n-1,s,d,a); [Link]("Move disk "+n+": "+s+"→"+d); hanoi(n-
1,a,s,d);
}

static List<List<Integer>> subsets(int[] nums){

List<List<Integer>> res=new ArrayList<>(); generateSubsets(nums,0,new
ArrayList<>(),res); return res;
}
static void generateSubsets(int[] nums,int i,List<Integer>
cur,List<List<Integer>> res){
[Link](new ArrayList<>(cur));
for(int j=i;j<[Link];j++)
{[Link](nums[j]);generateSubsets(nums,j+1,cur,res);[Link]([Link]()-1);}
}

static List<List<Integer>> permute(int[] nums){

List<List<Integer>> res=new ArrayList<>(); permuteSwap(nums,0,res); return
res;
}
static void permuteSwap(int[] nums,int start,List<List<Integer>> res){
if(start==[Link]){List<Integer> p=new ArrayList<>();for(int
n:nums)[Link](n);[Link](p);return;}
for(int i=start;i<[Link];i++)
{swap(nums,start,i);permuteSwap(nums,start+1,res);swap(nums,start,i);}
}
static void swap(int[] a,int i,int j){ int t=a[i];a[i]=a[j];a[j]=t; }

static int countSubsequences(int[] a,int i,int t){

if(t==0)return 1; if(i==[Link]||t<0)return 0;
return countSubsequences(a,i+1,t-a[i])+countSubsequences(a,i+1,t);
}
}

14 Practice Problems for Chapter 9

Solve in this order:

Difficulty Problem
Easy Fibonacci Number (LeetCode #509)
Easy Power of Two using Recursion (LeetCode #231)
Easy Reverse String (LeetCode #344)
Easy Flood Fill (LeetCode #733)
Medium Subsets (LeetCode #78)
Medium Permutations (LeetCode #46)
Medium Sort an Array — Merge Sort (LeetCode #912)
Medium Pow(x, n) — Fast Exponentiation (LeetCode #50)
Medium Generate All Subsequences with Sum K (GFG)
Hard Tower of Hanoi (GFG)

💡 Key Insight: The most common recursion mistake is not trusting the recursive call.

Don't trace through the entire recursion tree in your head.

Instead, apply the Recursion Hypothesis:
1. Define the base case — when is the answer trivially known?
2. Assume recursion(smaller) returns the correct answer.
3. Use that answer to build the full solution.

This leap of faith is the key mental shift that makes complex recursion feel simple.

Next up is Chapter 10 — Backtracking! 🚀