ISC Class 12 Recursion Programs: 8 Solved Questions for Theory and Practical

Recursion appears in the ISC Computer Science paper every single year. It shows up in output-tracing questions in Part I, in class-design questions in Section B, and in the practical exam. This post walks you through the 8 recursive methods that are asked most often.

What is Recursion?

A method that calls itself is called a recursive method. Every recursive method needs two parts:

1. Base case: the condition that stops the recursion.
2. Recursive case: the call to itself with a smaller or simpler input.

If you forget the base case, the method keeps calling itself until Java throws a StackOverflowError.

1. Factorial

int fact(int n) {
    if (n <= 1)
        return 1;              // base case
    return n * fact(n - 1);    // recursive case
}

Dry run of fact(4): 4 × fact(3) = 4 × 3 × fact(2) = 4 × 3 × 2 × fact(1) = 4 × 3 × 2 × 1 = 24

2. Power (x raised to n)

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

power(2, 5) returns 32.

3. GCD using the Euclidean Algorithm

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

Dry run of gcd(48, 18): gcd(18, 12), then gcd(12, 6), then gcd(6, 0), which returns 6.

4. Decimal to Binary

String toBinary(int n) {
    if (n == 0)
        return "";
    return toBinary(n / 2) + (n % 2);
}

toBinary(13) returns "1101". Note that this version returns an empty string for 0, so handle 0 separately in main() if needed.

5. Palindrome String Check

boolean isPalin(String s, int left, int right) {
    if (left >= right)
        return true;
    if (s.charAt(left) != s.charAt(right))
        return false;
    return isPalin(s, left + 1, right - 1);
}

Call it as isPalin("RACECAR", 0, 6), which returns true.

6. Fibonacci Term

int fib(int n) {
    if (n == 1)
        return 0;
    if (n == 2)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

The terms are 0, 1, 1, 2, 3, 5, 8, … so fib(7) returns 8.

Recursive Fibonacci is slow for large n because it recalculates the same terms many times. That is fine for the exam, and you can mention it as a limitation.

7. Reverse a String

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

reverse("JAVA") = reverse("AVA") + 'J' = (reverse("VA") + 'A') + 'J' = "AVAJ"

8. Recursive Binary Search

int binSearch(int a[], int key, int low, int high) {
    if (low > high)
        return -1;                  // not found
    int mid = (low + high) / 2;
    if (a[mid] == key)
        return mid;
    else if (key < a[mid])
        return binSearch(a, key, low, mid - 1);
    else
        return binSearch(a, key, mid + 1, high);
}

Complete ISC-Style Question: Class Binary

Design a class Binary to check whether a number has an even number of 1s in its binary form (such a number is called an Evil number).

• Data members: int num, String bin
• Binary(int n): the constructor
• String convert(int x): converts x to binary recursively
• int countOnes(String s, int i): counts the 1s recursively from index i
• void check(): prints whether num is Evil

import java.util.Scanner;

class Binary {
    int num;
    String bin;

    Binary(int n) {
        num = n;
        bin = "";
    }

    String convert(int x) {
        if (x == 0)
            return "";
        return convert(x / 2) + (x % 2);
    }

    int countOnes(String s, int i) {
        if (i == s.length())
            return 0;
        return (s.charAt(i) == '1' ? 1 : 0) + countOnes(s, i + 1);
    }

    void check() {
        bin = convert(num);
        int ones = countOnes(bin, 0);
        System.out.println("Binary: " + bin + ", Number of 1s: " + ones);
        if (ones % 2 == 0)
            System.out.println(num + " is an Evil number");
        else
            System.out.println(num + " is not an Evil number");
    }

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a positive number: ");
        Binary ob = new Binary(sc.nextInt());
        ob.check();
    }
}

Sample output: for 15 the result is "Binary: 1111, Number of 1s: 4" and "15 is an Evil number".

Tracing Output Questions: A Worked Example

What does mystery(5) print?

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

Step-by-step trace: mystery(5) calls mystery(3), which calls mystery(1), which calls mystery(−1). That call does nothing and returns. Then the prints happen as each call unwinds: 1, then 3, then 5.

Output: 1 3 5

Exam tip: when a print statement comes AFTER the recursive call, values are printed in reverse order of the calls. When it comes BEFORE the call, they are printed in the same order as the calls.

Practice Questions

1. Write a recursive method int sumDigits(int n) that returns the sum of the digits of n.
2. Write a recursive method that counts the vowels in a string.
3. Trace the output: int f(int n) { if (n == 0) return 0; return n % 10 + 10 * f(n / 10); } for f(472).
4. Write a recursive method to check whether a number is prime, using a divisor parameter.

Answer to Q3: it rebuilds the same number digit by digit, so f(472) = 472.

Practise these until you can write each one without looking. Then try the ISC practical questions from previous years in our Class 12 solved programs section.