Recursion and the call stack

1 The story

Folders inside folders inside folders

Riya's college drive has a folder Projects. Inside it are files and more folders, and some of those have folders too. She wants the total size, but every time she writes another nested loop, someone adds a deeper folder.

Riya

Sir, I wrote three nested loops for three levels. Then Kabir made a fourth level and my code missed it.

Arjun Sir

Look at the rule on the board. The size of a folder is its files plus the size of each sub-folder. And how do you find a sub-folder's size?

Riya

…the same way? Files plus its sub-folders. So the method needs to use itself!

Arjun Sir

Exactly: that's recursion. One short method handles any depth. You only need to say when to stop: a folder with no sub-folders. That's the base case. Forget it, and the calls never end.

2 Definition

What is recursion?

Formal definition (write this in exams)

Recursion is a technique in which a method calls itself, directly or indirectly, to solve a problem by reducing it to smaller instances of the same problem. A correct recursive method has at least one base case, which returns a result without a recursive call, and a recursive case, which calls the method on a smaller input that moves towards the base case. Each call gets its own stack frame with its own parameters and local variables; frames are removed in reverse order as calls return.

In simple words

Solve a big problem by solving a slightly smaller copy of it, again and again, until the problem is so small the answer is obvious. Then combine the answers on the way back.

Words you'll meet in this lesson

Base caseThe input that is answered directly, with no further call. It stops the recursion.

Recursive caseThe part that calls the method again on a smaller input.

Call stackThe pile of frames of the methods that have started but not yet returned.

UnwindingFrames being popped one by one as each call returns its result.

DepthHow many frames of the method are on the stack at the same time.

StackOverflowErrorThrown when the stack has no room for another frame.

The two parts every recursive method needs

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

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

120

	Recursion	Loop (iteration)
How it repeats	The method calls itself	The body runs again
How it stops	Base case	Loop condition becomes false
Memory	One stack frame per active call	Same variables reused
Risk	StackOverflowError if too deep or no base case	Infinite loop if the condition never fails
Best for	Trees, nested data, divide and conquer	Simple counting and lists

Exam tip: always state the base case and show how the input gets smaller each time. A common viva question: “What happens without a base case?” Answer: the method keeps calling itself, frames pile up, and the JVM throws java.lang.StackOverflowError (an Error, not an Exception).

3 Types and ways to use it

Shapes of recursion

Linear (one call each time)

Each call makes one smaller call: factorial, sum of digits, power, counting down. Depth = size of the input.

factorial(n − 1)

Tree (several calls each time)

Each call can branch: folders with many sub-folders, Fibonacci, merge sort. Work can grow very fast.

size(each child)

Divide and conquer

Cut the problem in half and recurse on one or both halves: binary search, merge sort. Depth only grows like log₂(n).

search(lo, mid − 1)

Direct, indirect and tail recursion

Kind	Meaning	Example
Direct	The method calls itself	`factorial` calls `factorial`
Indirect (mutual)	A calls B, B calls A	`isEven(n)` → `isOdd(n − 1)` → `isEven(n − 2)`
Tail	The recursive call is the very last action	`return sumTo(n − 1, acc + n);`
Head / non-tail	Work remains after the call returns	`return n * factorial(n − 1);` (multiply after)

Java does not optimise tail calls. Some languages turn tail recursion into a loop automatically. The JVM does not, so even tail-recursive Java methods use one frame per call and can overflow. For very deep problems, write a loop.

Same problem, recursive and iterative

public class Main {
    static int sumDigitsRec(int n) {
        if (n == 0) return 0;
        return n % 10 + sumDigitsRec(n / 10);
    }

    static int sumDigitsLoop(int n) {
        int sum = 0;
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(sumDigitsRec(4721) + " " + sumDigitsLoop(4721));
    }
}

14 14

Both give 4 + 7 + 2 + 1 = 14. The recursive version mirrors the definition (“last digit plus the digit sum of the rest”); the loop uses less memory. For digits, either is fine; for nested folders, recursion is far simpler.

4 Step by step

Writing a recursive method in four steps

Describe the problem in terms of a smaller copy of itself
“The power base^exp is base × base^{exp − 1}.” If you can't write a sentence like this, recursion is probably not the right tool.
Write the base case first
```
static long power(int base, int exp) {
    if (exp == 0) return 1;      // anything to the power 0 is 1
```
The base case must be reachable from every valid input. Here every positive exp eventually becomes 0.
Write the recursive case with a smaller input
```
    return base * power(base, exp - 1);
}
```
Each call pushes a new frame with its own exp: 3, then 2, 1, 0. The multiplications wait in their frames until the inner call returns.
Trust the smaller call, then trace one small case
```
power(2,3) = 2 * power(2,2)
           = 2 * (2 * power(2,1))
           = 2 * (2 * (2 * power(2,0)))
           = 2 * (2 * (2 * 1))  = 8
```
Four frames were on the stack at the deepest point. Then they unwind: 1 → 2 → 4 → 8, each frame finishing its multiplication as it is popped.
Check the limits
```
Exception in thread "main" java.lang.StackOverflowError
	at Main.power(Main.java:4)
	at Main.power(Main.java:4)
	at Main.power(Main.java:4)
	...
```
Call power(2, -1) and exp goes −2, −3… and never reaches 0. After many thousands of frames the thread's stack (often around 1 MB by default, set with -Xss) is full. Guard bad input with a check, such as throwing IllegalArgumentException for a negative exponent.

5 See it happen

factorial(3): down to the base case and back up

Left: the calls as you would write them on paper. Right: the real call stack, with one frame per call, each holding its own n.

Winding and unwinding the stack 7 steps

What you see

Behind the screen

6 Real-world use

Where recursion is the natural tool

Recursion shines when the data itself is nested: things that contain smaller things of the same kind.

Watch it with an example: adding up a folder tree

The run-the-code program below, as a picture. size() visits each folder, asks each sub-folder the same question, and adds up the answers on the way back.

size(Projects) = 40 + size(Java) + size(Python) 7 steps

Animated example

1. File systems and cloud drives

Computing folder sizes, searching for a file, copying or deleting a whole folder tree. Java's own Files.walk visits nested folders for you.

Folder→size(sub-folder) for each→Total size

2. Org charts, categories and comment threads

An e-commerce category “Electronics → Mobiles → Accessories”, a company's reporting tree, or replies to replies on a post. Counting or printing them is a recursive walk.

Category→count(child) recursively→Products in the whole tree

3. Searching and sorting fast

Binary search and merge sort split the work in halves. Arrays.sort for objects uses a merge-based algorithm, and parsers for JSON and HTML are often recursive because the documents are nested.

Sorted prices→search(half)→Found in ~log₂(n) steps

4. A real production risk

A recursive JSON or XML parser fed a document nested thousands of levels deep can crash a server with StackOverflowError. Libraries set a maximum nesting depth to prevent this.

Deeply nested input→depth limit check→Clear error instead of a crash

Examples are simplified. Real libraries often replace recursion with an explicit stack data structure when inputs can be very deep.

7 Run the code

Folder size, recursively

Real folders need file APIs (Module 13), so this program models a folder tree with arrays: files[i] is the size of folder i's own files, and children[i] lists its sub-folders.

public class Main {
    static String[] names = {"Projects", "Java", "Week1", "Python"};
    static int[] files = {40, 10, 3, 25};          // KB of files directly inside
    static int[][] children = {{1, 3}, {2}, {}, {}};

    static int size(int folder) {
        int total = files[folder];
        for (int child : children[folder]) {
            total += size(child);                  // same question, smaller folder
        }
        return total;                              // no children: loop doesn't run
    }

    public static void main(String[] args) {
        for (int f = 0; f < names.length; f++) {
            System.out.println(names[f] + ": " + size(f) + " KB");
        }
    }
}

Projects: 78 KB Java: 13 KB Week1: 3 KB Python: 25 KB

int total = files[folder];Start with the files directly inside this folder.
total += size(child);The recursive call: each sub-folder's size is found the same way.
Base caseA folder with no children: the loop runs zero times and the method returns straight away.
size(0)40 + size(Java) + size(Python) = 40 + (10 + 3) + 25 = 78.

8 Line by line

power(2, 3) on the real JVM

Recorded with a debugger attached to a real JVM: watch three power frames appear above main, each with its own exp, and then disappear in reverse order.

Worked examples: real problems, solved and traced in memory

Three problems where each step is a smaller copy of the whole problem. Step through each one and watch the frames of the same method pile up and unwind.

Example 1Banking · checksums

Digit sum of an account number

Problem statement

A simple check used by some ID schemes adds up all digits of a number. Write a recursive digitSum(long n): the last digit (n % 10) plus the digit sum of the rest (n / 10). Print it for 4721.

Input

n = 4721

Expected output

Digit sum of 4721 = 14

Approach

Base case: n == 0 → 0.
Recursive case: n % 10 + digitSum(n / 10).
Each call removes one digit, so the depth equals the number of digits.

Solution: run it live

What happens in memory, step by step

Recorded from the real JVM: press Next to execute one line at a time. Watch method calls push and pop frames on the stack, and objects (numbered #1, #2 …) appear on the heap.

Example 2Retail · price search

Binary search in sorted prices

Problem statement

A shopping app keeps product prices sorted: 99, 149, 249, 399, 599, 799, 999. Find the position of 599 with a recursive binary search that looks at the middle and throws away half each time.

Input

prices = {99, 149, 249, 399, 599, 799, 999}, target = 599

Expected output

599 found at index 4

Approach

Look at the middle index (lo + hi) / 2.
If it's the target, return the index; if the target is bigger, search the right half, else the left half.
Base case: lo > hi means not found (−1).

Solution: run it live

What happens in memory, step by step

Recorded from the real JVM: press Next to execute one line at a time. Watch method calls push and pop frames on the stack, and objects (numbered #1, #2 …) appear on the heap.

Example 3HR · org chart

Count everyone under a manager

Problem statement

An org chart: the CEO (0) manages 1 and 2; 1 manages 3 and 4; 4 manages 5. Write teamSize(person) that returns how many people report to that person, directly or indirectly.

Input

reports = {{1, 2}, {3, 4}, {}, {}, {5}, {}}, person = 1

Expected output

Person 1 leads 3 people

Approach

Each direct report counts as 1, plus everyone under them.
teamSize(p) = sum over each report r of (1 + teamSize(r)).
Base case: someone with no reports returns 0 (the loop doesn't run).

Solution: run it live

What happens in memory, step by step

Recorded from the real JVM: press Next to execute one line at a time. Watch method calls push and pop frames on the stack, and objects (numbered #1, #2 …) appear on the heap.

9 Quiz and revision

Check yourself

Quick revision

Lesson 5.5 in one screen

Recursion = a method that calls itself on a smaller input.
Every recursive method needs a base case (no call) and a recursive case that moves towards it.
Each call gets its own stack frame; frames pile up going down and are popped going up (unwinding).
Work written after the call (like n * …) happens on the way back up.
Too deep or no base case → StackOverflowError. Java has no tail-call optimisation.
Use recursion for nested data (trees, folders) and divide and conquer; use loops for simple repetition.
A method with a return type must return on every path, including the base case.

Interview and viva questions

What is recursion? What are its two essential parts?

A method that solves a problem by calling itself on a smaller version of the same problem. It needs a base case, which is answered directly, and a recursive case, which makes the input smaller so that the base case is eventually reached.

How does the call stack work during recursion?

Each call pushes a new frame holding that call's parameters, local variables and return address. The deepest call returns first; its frame is popped and the frame below continues from where it paused. The frames are removed in the reverse order of their creation.

What causes StackOverflowError and how do you fix it?

Too many frames on one thread's stack: usually a missing or unreachable base case, sometimes legitimately deep input. Fix the base case, validate input, convert the algorithm to a loop or an explicit stack, or (as a last resort) give the thread a bigger stack with -Xss.

Recursion or iteration: which is better?

Iteration uses constant stack space and is usually a little faster in Java. Recursion is clearer for tree-shaped and divide-and-conquer problems. Choose by clarity first, then switch to iteration if the depth can be large.

Why is naive recursive Fibonacci slow?

fib(n) = fib(n-1) + fib(n-2) recomputes the same values again and again, so the number of calls grows exponentially (around 1.6ⁿ). Storing results already computed (memoization) or using a loop makes it linear.

Practice problems

Practise finding the base case and the smaller problem. Check each answer by tracing a small input by hand before you run it. The last three are business problems.

P1Easy

Sum from 1 to n

Write a recursive sumTo(int n) that returns 1 + 2 + … + n. Print it for n = 10.

Input

n = 10

Expected output

Show solution and explanation

public class Main {
    static int sumTo(int n) {
        if (n == 0) return 0;
        return n + sumTo(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(sumTo(10));
    }
}

55

How it works: base case n = 0 gives 0; otherwise n plus the sum of the smaller range. Depth is n + 1 frames.

P2Easy

Reverse a word

Write a recursive reverse(String s): the last character followed by the reverse of the rest.

Input

"JAVA", "chai"

Expected output

AVAJ
iahc

Show solution and explanation

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

    public static void main(String[] args) {
        System.out.println(reverse("JAVA"));
        System.out.println(reverse("chai"));
    }
}

AVAJ iahc

How it works: a string of length 0 or 1 is its own reverse (base case). Each call removes one character, so the input gets smaller every time. (For real code, new StringBuilder(s).reverse() is simpler.)

P3Easy

Count down and up

Write countDownUp(int n) that prints n down to 1 and then 1 back up to n, using one recursive call and two print statements.

Input

n = 3

Expected output

3 2 1 1 2 3

Show solution and explanation

public class Main {
    static void countDownUp(int n) {
        if (n == 0) return;
        System.out.print(n + " ");
        countDownUp(n - 1);
        System.out.print(n + " ");
    }

    public static void main(String[] args) {
        countDownUp(3);
        System.out.println();
    }
}

3 2 1 1 2 3

How it works: the first print runs on the way down; the second waits in each frame and runs on the way back up, in reverse order. This is the clearest demonstration of the call stack.

P4Medium

Power in fewer steps

Compute base^exp with “fast power”: if exp is even, power(b, e) = half × half where half = power(b, e/2); if odd, multiply by b once more. Count the calls for 2³⁰.

Input

power(2, 10), power(3, 5), power(2, 30)

Expected output

1024
243
1073741824 in 6 calls

Show solution and explanation

public class Main {
    static int calls = 0;

    static long power(long base, int exp) {
        calls++;
        if (exp == 0) return 1;
        long half = power(base, exp / 2);
        if (exp % 2 == 0) return half * half;
        return half * half * base;
    }

    public static void main(String[] args) {
        System.out.println(power(2, 10));
        System.out.println(power(3, 5));
        calls = 0;
        System.out.println(power(2, 30) + " in " + calls + " calls");
    }
}

1024 243 1073741824 in 6 calls

How it works: halving the exponent each time means only about log₂(exp) + 1 calls: 6 calls for 2³⁰ instead of 31. This divide-and-conquer idea is used in cryptography for huge powers.

P5Medium

Palindrome check

Write a recursive isPal(String s, int i, int j) that compares the outer characters and moves inwards.

Input

"MALAYALAM", "KERALA"

Expected output

true
false

Show solution and explanation

public class Main {
    static boolean isPal(String s, int i, int j) {
        if (i >= j) return true;
        if (s.charAt(i) != s.charAt(j)) return false;
        return isPal(s, i + 1, j - 1);
    }

    public static void main(String[] args) {
        System.out.println(isPal("MALAYALAM", 0, 8));
        System.out.println(isPal("KERALA", 0, 5));
    }
}

true false

How it works: two base cases: the indexes meet (everything matched → true), or a mismatch is found (→ false, and no further calls are made).

P6Medium

Fibonacci: slow vs remembered

Compute fib(35) with the naive recursion and with a memo array, and count the calls each one makes.

Input

n = 35

Expected output

naive: 9227465 in 29860703 calls
memo:  9227465 in 69 calls

Show solution and explanation

public class Main {
    static long naiveCalls = 0, memoCalls = 0;
    static long[] memo = new long[100];

    static long fib(int n) {
        naiveCalls++;
        if (n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }

    static long fibMemo(int n) {
        memoCalls++;
        if (n < 2) return n;
        if (memo[n] != 0) return memo[n];
        memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
        return memo[n];
    }

    public static void main(String[] args) {
        System.out.println("naive: " + fib(35) + " in " + naiveCalls + " calls");
        System.out.println("memo:  " + fibMemo(35) + " in " + memoCalls + " calls");
    }
}

naive: 9227465 in 29860703 calls memo: 9227465 in 69 calls

How it works: the naive version recomputes the same values again and again: almost 3 crore calls. Storing each answer the first time cuts it to 69 calls. This idea (memoization) is the start of dynamic programming.

P7Business problem

Total value of a nested cart

A combo pack can contain items and other combo packs. Using arrays, price[i] is the item's own price and contains[i] lists the packs inside it. Find the full price of pack 0.

Input

Festival box (0) = Rs 50 + snacks pack (1) + sweets pack (2); snacks = Rs 120 + chips (3); sweets = Rs 300; chips = Rs 40

Expected output

Festival box: Rs 510
Snacks pack: Rs 160
Sweets pack: Rs 300
Chips: Rs 40

Show solution and explanation

public class Main {
    static String[] name = {"Festival box", "Snacks pack", "Sweets pack", "Chips"};
    static int[] price = {50, 120, 300, 40};
    static int[][] contains = {{1, 2}, {3}, {}, {}};

    static int fullPrice(int i) {
        int total = price[i];
        for (int inner : contains[i]) {
            total += fullPrice(inner);
        }
        return total;
    }

    public static void main(String[] args) {
        for (int i = 0; i < name.length; i++) {
            System.out.println(name[i] + ": Rs " + fullPrice(i));
        }
    }
}

Festival box: Rs 510 Snacks pack: Rs 160 Sweets pack: Rs 300 Chips: Rs 40

How it works: exactly the folder-size pattern. Any “thing made of smaller things of the same kind” (bill of materials, combo offers, nested menus) is a natural fit for recursion.

P8Business problem

EMI-free savings goal: months needed

Riya saves Rs 3,000 a month and her savings earn 1% per month. Write a recursive months(double saved, double goal) that returns how many months until she reaches Rs 20,000.

Input

start Rs 0, monthly Rs 3000, 1% per month, goal Rs 20000

Expected output

Months to Rs 20000: 7

Show solution and explanation

public class Main {
    static int months(double saved, double goal) {
        if (saved >= goal) return 0;
        double next = saved * 1.01 + 3000;
        return 1 + months(next, goal);
    }

    public static void main(String[] args) {
        System.out.println("Months to Rs 20000: " + months(0, 20000));
    }
}

Months to Rs 20000: 7

How it works: base case: the goal is reached, 0 more months needed. Otherwise one month passes (interest, then the new deposit) and we ask the same question with the new balance. Because the depth is only a few months, recursion is safe here; for a 30-year plan, a loop would be the safer choice.

Real-world scenario questions (asked in company interviews)

Recursion questions in interviews are rarely about factorial. They test whether you can reason about depth, memory and when not to recurse.

SaaS · production incident1–3 years

The comment thread that crashed the server

A forum renders comment replies with a recursive method render(comment) that calls itself for each reply. A spammer posted a reply chain 50,000 levels deep and the page request died with StackOverflowError. What do you do?

The interviewer is checking: do you understand recursion depth as a resource and how to make it safe?

Show a strong answer

Each nesting level is one frame; 50,000 frames exceed the thread's stack, so the error is expected, not random.
Short term: cap the depth (e.g. render 10 levels, then “Continue this thread”), and validate depth when replies are saved.
If deep trees are legitimate, rewrite the walk with an explicit Deque as a stack, which lives on the heap.

Avoid: “just increase -Xss”. It moves the limit but every thread pays for the larger stack.

E-commerce · categoriesFresher

Count products in a category tree

Categories form a tree: Electronics → Mobiles → Accessories, and so on, to any depth. Each category has some products directly and a list of sub-categories. Describe a method to count all products under a category.

The interviewer is checking: can you state the base case and recursive case clearly?

Show a strong answer

count(c) = c.products.size() + sum of count(child) for each child.
Base case: a category with no children; the loop simply doesn't run and we return its own product count.
Each category is visited once, so the time is proportional to the number of categories. Depth is the tree's height, which is small for real menus.

Avoid: writing a fixed number of nested loops for “three levels”.

Fintech · performance1–3 years

A recursive calculation that takes minutes

A colleague's recursive ways(n) counts how many ways a customer can split a repayment of n instalments into steps of 1 or 2. It's correct, but ways(45) takes very long. Why, and what's the fix?

The interviewer is checking: do you recognise overlapping subproblems?

Show a strong answer

ways(n) = ways(n−1) + ways(n−2) is the Fibonacci pattern; it recomputes the same values exponentially many times.
Memoize: store each ways(k) in an array the first time it's computed, or loop from 1 up to n keeping the last two values.
Either fix makes it linear: microseconds instead of minutes.

Avoid: blaming Java or the hardware.

Code reviewFresher

Recursion for a simple sum?

A pull request computes the total of a 1,00,000-item order list with sum(list, index) that calls sum(list, index + 1). Tests with 10 items pass. Would you approve it?

The interviewer is checking: can you spot depth problems that small tests hide?

Show a strong answer

No. Depth equals the list size: 1,00,000 frames will very likely throw StackOverflowError in production.
A simple loop (or stream().mapToInt(...).sum()) does the same with constant stack space.
Ask for a test with a realistic size.

Avoid: approving because “it's elegant”. Linear recursion over big lists is a known trap in Java.

Recursion and the call stack

Folders inside folders inside folders

What is recursion?

Words you'll meet in this lesson

The two parts every recursive method needs

Shapes of recursion

Linear (one call each time)

Tree (several calls each time)

Divide and conquer

Direct, indirect and tail recursion

Same problem, recursive and iterative

Writing a recursive method in four steps

Describe the problem in terms of a smaller copy of itself

Write the base case first

Write the recursive case with a smaller input

Trust the smaller call, then trace one small case

Check the limits

factorial(3): down to the base case and back up

Where recursion is the natural tool

Watch it with an example: adding up a folder tree

1. File systems and cloud drives

2. Org charts, categories and comment threads

3. Searching and sorting fast

4. A real production risk

Folder size, recursively

power(2, 3) on the real JVM

Worked examples: real problems, solved and traced in memory

Digit sum of an account number

Binary search in sorted prices

Count everyone under a manager

Check yourself

Quick revision

Lesson 5.5 in one screen

Interview and viva questions

Practice problems

Sum from 1 to n

Reverse a word

Count down and up

Power in fewer steps

Palindrome check

Fibonacci: slow vs remembered

Total value of a nested cart

EMI-free savings goal: months needed

Real-world scenario questions (asked in company interviews)

The comment thread that crashed the server

Count products in a category tree

A recursive calculation that takes minutes

Recursion for a simple sum?