Recursion in Java: ISC Class 12 Computer Science

What Recursion is about

Weightage: CISCE publishes no chapter or unit weightage for ISC Computer Science. Recursion is part of Section B, 11 of the 2027 syllabus and can be asked anywhere in the 70-mark Paper 1 (Part I compulsory: ten 1-mark items and a 10-mark short-answer question; Part II: two of three 10-mark questions in each of Sections A and B, and two of three 5-mark questions in Section C).Source: CISCE ISC Computer Science (868) syllabus, examination year 2027; latest Paper 1 specimen (2025) and the 2025 board paper

Key concepts

What recursion is: base case and recursive case

A recursive method solves a problem by calling itself on a smaller instance and combining the result.

Two essential parts:
1. Base case: the simplest input, answered directly without a further call (n <= 1 for factorial, b == 0 for GCD). Without it the calls never stop, and Java eventually throws StackOverflowError.
2. Recursive case: expresses the answer in terms of the same method on a smaller input, and each call must move closer to the base case (n - 1, n / 10, a shorter substring, a narrower range).

Recursive definitions translate directly into code:
factorial: n! = 1 if n ≤ 1; n × (n - 1)! otherwise.
GCD (Euclid): gcd(a, b) = a if b = 0; gcd(b, a mod b) otherwise.
power: x^0 = 1; x^n = x × x^(n - 1).
sum of digits: S(0) = 0; S(n) = n mod 10 + S(n div 10).

// Simple recursive methods: each has a base case and a recursive case that moves towards it.
public class RecDemo
{
    static long fact(int n)
    {
        if (n <= 1)                        // base case
            return 1;
        return n * fact(n - 1);            // recursive case
    }

    static int gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    static int power(int x, int n)
    {
        if (n == 0)
            return 1;
        return x * power(x, n - 1);
    }

    static int digitSum(int n)
    {
        if (n == 0)
            return 0;
        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);
    }

    static int binSearch(int[] a, int key, int lo, int hi)
    {
        if (lo > hi)
            return -1;
        int mid = (lo + hi) / 2;
        if (a[mid] == key)
            return mid;
        if (a[mid] < key)
            return binSearch(a, key, mid + 1, hi);
        return binSearch(a, key, lo, mid - 1);
    }

    static int fib(int n)                  // 1, 1, 2, 3, 5, ...
    {
        if (n <= 2)
            return 1;
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args)
    {
        System.out.println("5! = " + fact(5));
        System.out.println("gcd(84, 36) = " + gcd(84, 36));
        System.out.println("2^10 = " + power(2, 10));
        System.out.println("digitSum(4075) = " + digitSum(4075));
        System.out.println("reverse(\"STACK\") = " + reverse("STACK"));
        int[] a = {5, 12, 19, 23, 31, 44, 56, 70};
        System.out.println("binSearch(44) = " + binSearch(a, 44, 0, a.length - 1));
        System.out.println("fib(10) = " + fib(10));
    }
}

Output:

5! = 120
gcd(84, 36) = 12
2^10 = 1024
digitSum(4075) = 16
reverse("STACK") = KCATS
binSearch(44) = 5
fib(10) = 55

Recursion versus iteration: recursion is often shorter and closer to the mathematical definition (and much simpler for problems such as the Tower of Hanoi or tree traversal), but each call uses stack memory and adds call overhead, so it usually uses more memory and can be slower; naive recursion can also repeat work (fib(n) recomputes the same values many times).

Worked example

[2] State the two essential parts of a recursive method and what happens if the first is missing. (Understand)

Try it first, then show the solutionSolution

1. Base case (stops the recursion) and recursive case (calls the method on a smaller input moving towards the base case) - 1 mark.
2. Without a base case the calls never end; memory for the call stack runs out and a StackOverflowError occurs - 1 mark.

Answer: Every recursive method needs a base case, which returns directly, and a recursive case, which calls the method on a smaller problem. With no base case the method calls itself forever until the stack overflows (StackOverflowError).

The call stack and tracing recursive methods

Each call creates a new activation record (its own parameters and local variables) pushed onto the call stack. When a call returns, its record is popped and control goes back to the caller, which continues from where it left off. Because the last call made is the first to finish, recursion follows the stack's LIFO (last in, first out) principle.

Tracing method (winding and unwinding):
1. Write each call on a new line with its arguments (winding), until the base case.
2. Then return upwards, substituting each returned value into the waiting expression (unwinding).
3. State the final value and, if asked, what the method does in general.

Trace of fact(4): fact(4) = 4 × fact(3) = 4 × 3 × fact(2) = 4 × 3 × 2 × fact(1) = 4 × 3 × 2 × 1 = 24.

Tracing exercises (program output below):

• what(n): returns n if n <= 1, else what(n / 2) + n % 2. what(13) = what(6) + 1 = (what(3) + 0) + 1 = ((what(1) + 1) + 0) + 1 = 3. It counts the 1s in the binary form of n (13 = 1101).
• calc(a, b): 0 if b = 0, else a + calc(a, b - 1): repeated addition, so calc(7, 4) = 28 (multiplication).
• show(n): prints n, recurses with n - 2, then prints n again on the way back: show(5) prints 5 3 1 1 3 5, showing that statements after the recursive call run in reverse order.
• evens(x, n): counts the even elements of x[0..n], checking x[n] and then the shorter range x[0..n - 1], until the empty range n < 0 returns 0.

// Tracing exercises used on the page.
public class Mystery
{
    static int what(int n)
    {
        if (n <= 1)
            return n;
        return what(n / 2) + n % 2;
    }

    static int calc(int a, int b)
    {
        if (b == 0)
            return 0;
        return a + calc(a, b - 1);
    }

    static void show(int n)
    {
        if (n > 0)
        {
            System.out.print(n + " ");
            show(n - 2);
            System.out.print(n + " ");
        }
    }

    static int evens(int[] x, int n)            // number of even elements in x[0..n]
    {
        if (n < 0)
            return 0;
        return (x[n] % 2 == 0 ? 1 : 0) + evens(x, n - 1);
    }

    public static void main(String[] args)
    {
        System.out.println("what(13) = " + what(13) + ", what(16) = " + what(16));
        System.out.println("calc(7, 4) = " + calc(7, 4));
        show(5);
        System.out.println();
        int[] x = {4, 9, 2, 6};
        System.out.println("evens = " + evens(x, 3));
    }
}

Output:

what(13) = 3, what(16) = 1
calc(7, 4) = 28
5 3 1 1 3 5 
evens = 3

Worked example

[3] For the method what( ) above, find what(13) with working and state what the method computes. (Analyse)

Try it first, then show the solutionSolution

1. what(13) = what(6) + 13 % 2 = what(6) + 1; what(6) = what(3) + 0; what(3) = what(1) + 1; what(1) = 1 (base case) - 1 mark.
2. Unwinding: what(3) = 2, what(6) = 2, what(13) = 2 + 1 = 3 - 1 mark.
3. It counts the number of 1s in the binary representation of n (13 = 1101 has three) - 1 mark.

Answer: what(13) = 3; the method counts the 1 bits in the binary form of n.

Recursive binary search and base conversion

Binary search fits recursion naturally: search a sorted range [lo, hi]; base cases are lo > hi (not found, return -1) and a[mid] == key (found); otherwise recurse on the left or right half. The range halves every call.

Base conversion: to write n in base b, first write n / b in base b (the higher digits), then append the digit n % b. The base case is n == 0. Because the digit is appended after the recursive call, digits come out most significant first, so no reversing is needed. For bases above 10, digits 10 to 15 are written A to F: (char) ('A' + d - 10).

import java.util.Scanner;

// Converts a positive decimal integer to any base from 2 to 16 using a recursive method.
public class BaseConv
{
    int num, base;
    String res;

    BaseConv()
    {
        num = 0;
        base = 2;
        res = "";
    }

    void accept()
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter a positive integer and a base (2-16):");
        num = sc.nextInt();
        base = sc.nextInt();
    }

    // builds the digits of n in the given base into res, most significant digit first
    void convert(int n)
    {
        if (n == 0)
            return;                                    // base case
        convert(n / base);                             // first convert the higher digits
        int d = n % base;
        char digit = (d < 10) ? (char) ('0' + d) : (char) ('A' + d - 10);
        res = res + digit;                             // then append this digit
    }

    void display()
    {
        res = "";
        if (num == 0)
            res = "0";
        else
            convert(num);
        System.out.println(num + " in base " + base + " = " + res);
    }

    public static void main(String[] args)
    {
        BaseConv ob = new BaseConv();
        ob.accept();
        ob.display();
    }
}

Input: 2027 16

Enter a positive integer and a base (2-16):
2027 in base 16 = 7EB

Check: 2027 = 7 × 256 + 14 × 16 + 11 → 7, E, B. Other runs: 45 in base 2 = 101101; 64 in base 8 = 100; 255 in base 16 = FF; 0 is handled separately as "0".

The reverse direction (digits of a number in base b to decimal) is also recursive: value(n) = value(n / 10) × b + n % 10, for a number stored with decimal digits such as 101101.

Worked example

[2] Trace convert(45) for base 2 in the BaseConv class and give the result. (Apply)

Try it first, then show the solutionSolution

1. Calls: convert(45) → convert(22) → convert(11) → convert(5) → convert(2) → convert(1) → convert(0) returns - 1 mark.
2. Digits appended while unwinding: 1 % 2 = 1, 2 % 2 = 0, 5 % 2 = 1, 11 % 2 = 1, 22 % 2 = 0, 45 % 2 = 1 → 101101 - 1 mark.

Answer: 101101

Tower of Hanoi

Problem: move n discs of different sizes from peg A to peg C using peg B, moving one disc at a time and never placing a larger disc on a smaller one.

Recursive idea:
1. Move the top n - 1 discs from A to B (using C).
2. Move the largest disc from A to C.
3. Move the n - 1 discs from B to C (using A).
Base case: n = 0 (nothing to move).

Number of moves: T(n) = 2T(n - 1) + 1 with T(0) = 0, giving T(n) = 2^n - 1 (7 for 3 discs, 1023 for 10 discs). A non-recursive solution is much harder to write; the recursive one is three lines.

// Tower of Hanoi: move n discs from peg A to peg C using B, one disc at a time,
// never placing a larger disc on a smaller one.
public class Hanoi
{
    static int moves = 0;

    static void move(int n, char from, char via, char to)
    {
        if (n == 0)
            return;                        // base case: nothing to move
        move(n - 1, from, to, via);        // park n - 1 discs on the spare peg
        moves++;
        System.out.println("Move disc " + n + " from " + from + " to " + to);
        move(n - 1, via, from, to);        // bring them onto the largest disc
    }

    public static void main(String[] args)
    {
        move(3, 'A', 'B', 'C');
        System.out.println("Total moves: " + moves);
    }
}

Output:

Move disc 1 from A to C
Move disc 2 from A to B
Move disc 1 from C to B
Move disc 3 from A to C
Move disc 1 from B to A
Move disc 2 from B to C
Move disc 1 from A to C
Total moves: 7

Worked example

[2] How many moves does the Tower of Hanoi need for 4 discs and for 6 discs? Justify. (Apply)

Try it first, then show the solutionSolution

1. T(n) = 2T(n - 1) + 1 with T(0) = 0 gives T(n) = 2^n - 1 - 1 mark.
2. 4 discs: 16 - 1 = 15; 6 discs: 64 - 1 = 63 - 1 mark.

Answer: 15 moves for 4 discs and 63 for 6 discs (2^n - 1).

Writing recursive methods in Section B programs

When a question says 'using recursive technique':
1. The method must call itself; no loops in that method (examiners deduct for loops or a mix).
2. Match the specified signature exactly (for example void convert(int n) or int countOne(int k)).
3. Choose the base case from the smallest input: n == 0 for digit problems; empty or one-character strings for string problems; lo > hi for searches.
4. Make the recursive call on a smaller value: n / 10 (decimal digits), n / 16 (hexadecimal), k / 10 (counting digits of a binary number stored as an int).
5. For a void method that builds a result, store it in the data member (res = res + digit) after the recursive call if the order must be most significant first.
6. The calling method (display or check) must invoke the recursive method before using its result.

Typical recursive tasks: count digits, sum or product of digits, reverse a number or string, check palindrome, count vowels, power, GCD, factorial, Fibonacci term, base conversion, count 1s in a binary number, largest element of an array.

Worked example

[2] Write a recursive method int countEven(int n) that returns the number of even digits in a positive integer n (for example 40712 → 3). (Create)

Try it first, then show the solutionSolution

1. Base case: if (n == 0) return 0; - 1 mark.
2. Recursive case: return (n % 10 % 2 == 0 ? 1 : 0) + countEven(n / 10); (test the last digit, then the rest) - 1 mark.

Answer: int countEven(int n) { if (n == 0) return 0; return (n % 10 % 2 == 0 ? 1 : 0) + countEven(n / 10); } countEven(40712) = 3 (digits 4, 0 and 2), checked by running the code.

Recursion in real life

Each concept, met in an everyday situation. Read the situation, answer the question in your own words, then compare with the model answer. The one-line hook is what to remember.

Topics in this chapter

• Recursive Methods, Tracing and the Tower of Hanoi

Recursion: syntax and key facts

Factorial

fact(n) = 1 if n ≤ 1; n × fact(n - 1)

fact(5) = 120.

GCD

gcd(a, b) = a if b = 0; gcd(b, a % b)

gcd(84, 36) = 12.

Digit recursion

f(n) = base value if n = 0; combine(n % 10, f(n / 10))

Sum, count, reverse.

Base conversion

convert(n): if n > 0 { convert(n / b); append n % b }

Digits 10-15 → A-F.

Tower of Hanoi

T(n) = 2T(n - 1) + 1 = 2^n - 1

3 discs → 7 moves.

How the board asks Recursion

The question patterns to expect, and the method that works for each.

Tricks to remember Recursion

Short memory aids. Say each one aloud once, then use it on a question the same day.

• Stop, Shrink, Combine

  Every recursive method: Stop (base case), Shrink (smaller call), Combine (use the result).

  Use it when: Writing recursion.

• Before the call goes forward, after the call comes back

  Statements before the recursive call run in calling order; after it, in reverse order.

  Use it when: Tracing outputs like 5 3 1 1 3 5.

• Hanoi 2^n - 1

  Discs 1, 2, 3, 4 → moves 1, 3, 7, 15.

  Use it when: Move counts.

Recursion: board-level solved questions

Ordered from board level to HOTS. Cover the solution, write your own, then compare step by step.

Case-study practice (Section D style)

Read the situation, then answer every part. In the board paper this is a 6-mark question split into 2 + 1 + 2 + 1 marks.

Where the marks are

How a typical answer is split into step marks. Show every step: a right final answer alone rarely earns full marks.

Where students lose marks in Recursion

The slips examiners see most often, and what to write instead.

• ✗Mistake: Wrong parameters in the recursive call while tracing

  CISCE examiners' comments, 2024 and 2025: candidates 'Changed function parameters incorrectly in the recursive call', were 'Unclear on stack concept for recursion', and 'Did the working but did not state the final output'; in 2025 some 'returned wrong final value after correct dry run'.

  ✓Do this: Copy the call exactly as written (watch --n versus n - 1, and which argument changes); write the pending expression on each line; state the final value clearly.

  Usually costs: 1-3 marks.

• ✗Mistake: Loops instead of recursion, wrong recursive call

  CISCE examiners' comments, 2024: in the decimal-to-hexadecimal program candidates 'Used a loop instead of recursion, or a mix of both', made a 'Wrong recursive call such as convert(n/2) or convert(n%16)', and 'Did not handle digits A-F properly'.

  ✓Do this: Call convert(n / 16) for hexadecimal; append the digit after the call; map 10-15 to A-F with (char) ('A' + d - 10).

  Usually costs: Most of the method's marks.

• ✗Mistake: Missing or wrong base case

  CISCE examiners' comments, 2025: candidates had a 'Missing or wrong base case and badly structured recursive case' and 'Misunderstood parameter of countOne( )'.

  ✓Do this: Decide the smallest input first (k == 0 for digit problems) and what it returns; make sure every call moves towards it.

  Usually costs: 2-3 marks.

• ✗Mistake: Relating recursion to a queue

  CISCE examiners' comments, 2024: on an assertion-reason item, candidates 'could not relate stack to recursion'; examiners advised reading each statement independently.

  ✓Do this: Recursion uses the call stack (LIFO), never a queue.

  Usually costs: 1 mark.

Practice questions on Recursion

Write each answer on paper first. Open the hint only if you are stuck, and the answer only when you have finished.

1. Q1 · 1 mark · Very short answerBoard level

   What is a base case?

   Hint

   Stops recursion.

   Answer

   The condition in a recursive method for which the answer is returned directly, without a further recursive call.

2. Q2 · 1 mark · Very short answerBoard level

   Which error occurs if a recursive method has no reachable base case?

   Hint

   Stack.

   Answer

   StackOverflowError.

3. Q3 · 1 mark · Very short answerBoard level

   Find gcd(48, 18) using gcd(a, b) = gcd(b, a % b).

   Hint

   48 % 18 = 12.

   Answer

   6 (gcd(18, 12) → gcd(12, 6) → gcd(6, 0)).

4. Q4 · 1 mark · Very short answerHarder board level

   What is printed by the recursive reverse("STACK") method above?

   Hint

   First letter goes last.

   Answer

   KCATS

5. Q5 · 2 marks · Short answerHarder board level

   [2] Write a recursive method int countDigits(int n) for n ≥ 1.

   Hint

   Base: one digit.

   Answer

   int countDigits(int n) { if (n < 10) return 1; return 1 + countDigits(n / 10); } countDigits(4075) = 4.

6. Q6 · 3 marks · Short answerHarder board level

   [3] Trace int f(int n) { if (n == 0) return 0; return (n % 10) * (n % 10) + f(n / 10); } for n = 123 and state its purpose.

   Hint

   Squares of digits.

   Answer

   f(123) = 9 + f(12) = 9 + 4 + f(1) = 9 + 4 + 1 + f(0) = 14. It returns the sum of the squares of the digits.

7. Q7 · 5 marks · Long answerHOTS / competency

   [5] Write a recursive method int binToDec(int n) that converts a binary number stored as an int (such as 101101) to decimal, and give binToDec(101101).

   Hint

   value = value(n / 10) × 2 + n % 10.

   Answer

   int binToDec(int n) { if (n == 0) return 0; return binToDec(n / 10) * 2 + n % 10; } binToDec(101101) = 45 (checked by running the code).

8. Q8 · 10 marks · Long answerHOTS / competency

   [10] Design a class Palin with data member num; a constructor; void accept( ); int reverse(int n, int r) that returns the reverse of n using recursion (r carries the reversed part, initially 0); and void check( ) that invokes reverse( ) to print whether num is a palindrome. Write main( ).

   Hint

   reverse(n / 10, r * 10 + n % 10).

   Answer

   Constructor sets num = 0; accept( ) reads num; int reverse(int n, int r) { if (n == 0) return r; return reverse(n / 10, r * 10 + n % 10); } check( ): if reverse(num, 0) == num print 'Palindrome' else 'Not a palindrome'; main( ) calls accept( ) and check( ). 12321 → Palindrome; 2027 → Not a palindrome (reverse 7202), checked by running the code.

Test your recall

Answer in your head or on paper first, then open the card. Pulling an answer out of memory makes it stick far better than re-reading.

1. 1.Two parts of every recursive method?Show answer

   Base case and recursive case.

2. 2.Moves for 3 discs in Hanoi?Show answer

   7.

3. 3.2027 in hexadecimal?Show answer

   7EB.

4. 4.What does what(n) = what(n / 2) + n % 2 count?Show answer

   The 1 bits in n's binary form.

5. 5.Data structure behind recursion?Show answer

   The call stack (LIFO).

Quick revision checklist

The night before the exam: can you do each of these without looking?

• ☐Recursion: method calls itself on a smaller input; needs a base case.
• ☐No base case → StackOverflowError.
• ☐Calls pile up on the stack (LIFO) and return in reverse order.
• ☐fact, gcd, power, digit sum, reverse, binary search: learn the two-line forms.
• ☐Base conversion: convert(n / b) then append n % b; 10-15 → A-F.
• ☐Hanoi: move n - 1, move largest, move n - 1; 2^n - 1 moves.
• ☐Recursion: elegant but more memory than iteration.

Recursion: frequently asked questions