Skip to content
Laviyx Learn

Try

Java course menu

Java Recursion: Base Cases, Recursive Calls and Examples

Learn recursion in Java: methods that call themselves, base cases and recursive cases, factorial, power, digit sum, string reversal, binary search, the call stack and StackOverflowError, and when to use a loop instead.

Beginner11 min readUpdated
On this page

A recursive method calls itself. Recursion solves a problem by reducing it to a smaller version of the same problem, until it becomes so small that the answer is obvious.

The two parts of every recursive method#

  1. A base case that is answered directly, without recursion.
  2. A recursive case that calls the method with a smaller input, moving towards the base case.

Factorial#

5! = 5 × 4 × 3 × 2 × 1, and 5! = 5 × 4!:

Java
public class Main {
    static long factorial(int n) {
        if (n <= 1) {
            return 1;                    // base case
        }
        return n * factorial(n - 1);     // recursive case
    }

    public static void main(String[] args) {
        System.out.println(factorial(5));
        System.out.println(factorial(20));
    }
}
Output
120
2432902008176640000

long is needed because factorials grow very quickly; 13! already overflows an int.

How it runs: the call stack#

Each call gets its own copy of n in a stack frame. The calls pile up until the base case, then the results flow back:

Java
public class Main {
    static void countdown(int n) {
        if (n == 0) {
            System.out.println("Lift off!");
            return;
        }
        System.out.println("going down " + n);
        countdown(n - 1);
        System.out.println("coming back " + n);
    }

    public static void main(String[] args) {
        countdown(3);
    }
}
Output
going down 3
going down 2
going down 1
Lift off!
coming back 1
coming back 2
coming back 3

More examples#

Java
public class Main {
    static double power(double base, int exp) {
        if (exp == 0) return 1;
        return base * power(base, exp - 1);
    }

    static int digitSum(int n) {
        if (n < 10) return n;
        return n % 10 + digitSum(n / 10);
    }

    static String reverse(String s) {
        if (s.length() <= 1) return s;
        return reverse(s.substring(1)) + s.charAt(0);
    }

    public static void main(String[] args) {
        System.out.println(power(2, 10) + " " + power(1.5, 3));
        System.out.println(digitSum(4096));
        System.out.println(reverse("recursion"));
    }
}
Output
1024.0 3.375
19
noisrucer

Problems that split in half are natural for recursion. Binary search checks the middle of a sorted range and continues in one half:

Java
public class Main {
    static int binarySearch(int[] a, int target, int low, int high) {
        if (low > high) return -1;
        int mid = low + (high - low) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) return binarySearch(a, target, mid + 1, high);
        return binarySearch(a, target, low, mid - 1);
    }

    public static void main(String[] args) {
        int[] nums = {3, 8, 15, 23, 42, 57, 91};
        System.out.println(binarySearch(nums, 42, 0, nums.length - 1));
        System.out.println(binarySearch(nums, 5, 0, nums.length - 1));
    }
}
Output
4
-1

low + (high - low) / 2 avoids the overflow that (low + high) / 2 can cause for very large arrays.

Fibonacci and repeated work#

A direct translation of fib(n) = fib(n−1) + fib(n−2) recomputes the same values over and over. Remembering results (memoization) or using a loop fixes that:

Java
import java.util.HashMap;
import java.util.Map;

public class Main {
    static long fibSlow(int n) {
        if (n < 2) return n;
        return fibSlow(n - 1) + fibSlow(n - 2);
    }

    static final Map<Integer, Long> memo = new HashMap<>();

    static long fibMemo(int n) {
        if (n < 2) return n;
        Long cached = memo.get(n);
        if (cached != null) return cached;
        long result = fibMemo(n - 1) + fibMemo(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(fibSlow(20) + " " + fibMemo(20));
        System.out.println(fibMemo(80));
    }
}
Output
6765 6765
23416728348467685

fibSlow(40) makes hundreds of millions of calls; fibMemo(80) computes each value once.

StackOverflowError#

Every call uses stack memory. Recursion that goes too deep, or never reaches its base case, ends with a StackOverflowError:

Java
public class Main {
    static int depth = 0;

    static void forever() {
        depth++;
        forever();   // no base case
    }

    public static void main(String[] args) {
        try {
            forever();
        } catch (StackOverflowError e) {
            System.out.println("Stack overflow after many calls");
        }
    }
}
Output
Stack overflow after many calls

The exact depth depends on the JVM and its stack size (often several thousand calls). Java does not optimize tail calls, so prefer loops for long, simple sequences.

Recursion or a loop?#

Prefer recursion whenPrefer a loop when
The data is naturally recursive (trees, nested folders)You are counting or walking a sequence
The problem splits into halves (binary search, merge sort)The depth could be large
The recursive version is much clearerSub-problems repeat and performance matters

Common mistakes#

Practice#

Practice exercise

Write a recursive int gcd(int a, int b) using Euclid's algorithm (gcd(a, 0) = a, otherwise gcd(b, a % b)) and print gcd(84, 36).

Show solution
Java
public class Gcd {
    static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        System.out.println(gcd(84, 36));
    }
}
Output
12

Practice exercise

Write a recursive int countChar(String s, char c, int index) that counts how many times c appears in s from index onwards, and print the count of 's' in "mississippi".

Show solution
Java
public class CountChar {
    static int countChar(String s, char c, int index) {
        if (index == s.length()) return 0;
        int here = s.charAt(index) == c ? 1 : 0;
        return here + countChar(s, c, index + 1);
    }

    public static void main(String[] args) {
        System.out.println(countChar("mississippi", 's', 0));
    }
}
Output
4

Passing an index avoids creating a new substring at every step.

Key takeaway#

Finished this lesson?

Related lessons

JavaJava Methods: Defining, Calling, Parameters and Return ValuesLearn Java methods: defining static methods, calling them, parameters and arguments, return types and void, returning early, boolean methods, the method signature, and how to write small single-purpose methods.Beginner9 min readJavaJava Scope and static: Local Variables, Fields and Class MembersUnderstand variable scope in Java: block scope, local variables, why Java forbids shadowing locals, fields vs local variables, static fields and methods shared by the whole class, and instance members.Beginner8 min readJavaJava Arrays: Creating, Looping, Sorting and the Arrays ClassLearn Java arrays: declaring and creating arrays, default values, indexing and length, ArrayIndexOutOfBoundsException, looping, printing with Arrays.toString, sorting, searching, copying and comparing arrays, and when to use ArrayList instead.Beginner11 min read