On this page
Recursion questions in ISC computer science usually say "trace the method" or "what is the output", and they are hard only if you try to hold every call in your head. On paper they become mechanical. This post explains how a recursive call works, gives a tracing method, works through examples whose outputs we ran in Java, and lists the bugs that turn a neat method into a crash.
What does the ISC syllabus expect on recursion?
The ISC 2027 Computer Science syllabus includes recursion in both Class XI and Class XII. The Class XII unit lists the "concept of recursion, simple recursive methods (e.g. factorial, GCD, binary search, conversion of representations of numbers between different bases)". Its notes say many problems "can be solved very elegantly" by building a solution from smaller versions of the same problem, and: "Emphasize that any recursion must have a base case. Otherwise, the computation can go into an infinite loop."
What happens when a method calls itself?
Each call gets its own copy of its parameters and local variables, stored on the call stack. A call that reaches the recursive line pauses there until the call it made returns. So the calls pile up going down, and then finish one by one coming back up, last in, first out.
Take this method:
int sumDigits(int n) {
if (n == 0) return 0; // base case
return n % 10 + sumDigits(n / 10);
}Trace sumDigits(4096):
sumDigits(4096) waits for 6 + sumDigits(409)
sumDigits(409) waits for 9 + sumDigits(40)
sumDigits(40) waits for 0 + sumDigits(4)
sumDigits(4) waits for 4 + sumDigits(0)
sumDigits(0) returns 0
Now unwind: 4 + 0 = 4, then 0 + 4 = 4, then 9 + 4 = 13, then 6 + 13 = 19. The answer is 19.
Why does output order change with where you print?
Printing before the recursive call shows values on the way down; printing after shows them on the way up. This method does both:
void show(int n) {
if (n == 0) return;
System.out.print(n + " ");
show(n - 1);
System.out.print(n + " ");
}show(3) prints 3 2 1 1 2 3. The first half comes from the calls going down, the second half from the same calls finishing in reverse. Base conversion uses the same idea: to print 13 in binary, recurse on 13 / 2 first and print 13 % 2 after, which gives 1101 in the right order.
Worked examples from the syllabus list
We ran each of these in Java 21 to confirm the outputs.
Factorial: fact(n) returns 1 if n is at most 1, else n × fact(n − 1). fact(5) = 5 × 4 × 3 × 2 × 1 = 120.
GCD by Euclid: gcd(a, b) returns a if b is 0, else gcd(b, a % b). gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) = 6.
Binary search: search the sorted array {3, 8, 15, 21, 34, 42, 57} for 34. With low = 0 and high = 6, mid = 3 holds 21; 34 is larger, so recurse on 4 to 6. mid = 5 holds 42; 34 is smaller, so recurse on 4 to 4. mid = 4 holds 34, so return index 4. The base case for "not found" is low > high, returning −1.
Base conversion: converting 45 to base 2 gives 101101, and 255 to base 16 gives FF.
What causes StackOverflowError?
Java's documentation says StackOverflowError is "thrown when a stack overflow occurs because an application recurses too deeply". In ISC programs that almost always means the base case is never reached. Three common causes, all of which crashed when we ran them:
No base case at all.
A base case the input skips. count(n) with base case n == 0 and a call on n − 2 never stops for an odd n, since 5, 3, 1, −1 jumps past 0. Use n <= 0.
Post-decrement in the call. return n * fact(n--) passes the same n again, because n-- gives the old value. Write fact(n - 1).
Common mistakes in tracing questions
Writing the return values in the order the calls were made, rather than unwinding from the base case.
Forgetting that each call has its own n, so a change to n in one call does not affect the caller.
Missing a return in a non-void method, or ignoring the value a recursive call returns.
Counting the base-case call when a question asks how many times the method is called. Count it: sumDigits(4096) makes five calls.
A practice routine for recursion
Each day for a week, trace two methods on paper before running them: one returning a value, one printing. Write the stack down the page, then unwind. Then write one method from the syllabus list from scratch and test it with an edge case, such as 0, 1 or a negative number. Our guide to ISC computer science and Java shows where recursion fits in the theory and practical papers.
If you trace a method and still cannot see why the output comes out that way, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer.
Try it now: trace show(4) on paper, then check that it prints 4 3 2 1 1 2 3 4.
