DAY 7 : Tackling Recursion One Problem at a Time | My DSA Journey (Recursion)

---

Introduction

Welcome to Day 7 of my DSA Journey!
For the past few days, I’ve been focusing on one of the most fundamental and important concepts in DSA — Recursion.
Solved some easy level question on recursion which helps me to grasp the concept how recursion is working behind the scenes.

I’m documenting my journey in public to stay consistent and to help others who are also learning DSA from scratch.

Here’s what I learnt in last 3 days:

• Day 4:
  → Reverse a number
  → Count the number of zeroes in a number
  → Number of steps to reduce a number to zero

• Day 5:
  → Check string is palindrome or not
  → Check array is sorted or not
  → Reverse array

• Day 6:
  → Pow(x, n)
  -> Count Good Numbers

Let’s break down each of these topics below 👇

---

Q 1. Reverse a number:

Given a positive integer n, task is to reverse its digits using recursion.
Examples:

• Input: 1234 → Output: 4321
• Input: 5020 → Output: 205

Approach: Recursive Method with Digit Position Tracking

This solution uses recursion along with mathematical operations to reverse the digits by placing each digit in its correct reversed position.

Steps:

1. Calculate the number of digits in the input number using log10(n) + 1.
2. Use a helper recursive function that:
   • Takes the number n and the number of digits left.
   • Base case: If n has only one digit, return it directly.
   • Extract the last digit using n % 10.
   • Place the digit in the reversed position using digit * 10^(digits - 1).
   • Recursively call the function with the remaining number (n / 10) and decrease the digit count by 1.

Example:

Let’s say n = 1234
Digits = 4
Recursive breakdown:

• 4 * 10^3 + reverse(123, 3)
• 3 * 10^2 + reverse(12, 2)
• 2 * 10^1 + reverse(1, 1)
• Base case reached → return 1

Final Result:
4000 + 300 + 20 + 1 = 4321

Code:

static int reverse(int n) {
    int digits = (int)(Math.log10(n)) + 1;
    return helper(n, digits);
}

private static int helper(int n, int digits) {
    if (n % 10 == n) {
        return n;
    }

    int rem = n % 10;
    return rem * (int)Math.pow(10, digits - 1) + helper(n / 10, digits - 1);
}

---

Q 2. Count the number of zeroes in a number:

Given an integer number, and we need to find how many zero digits are present in that number.
For example, if the input is 10204, the output should be 2 because there are two zero digits.

Approach:

To count the number of zero digits in a given number using recursion:

• Start with the given number and an initial count of zero.
• Extract the last digit (rem) of the number using n % 10.
• If the digit is zero, increment the count.
• Remove the last digit from the number by doing integer division n / 10.
• Recursively call the helper function with the updated number and count.
• The base case is when the number becomes zero — at this point, return the accumulated count.

This approach uses an accumulator (count) to keep track of the zero digits found so far.

Example:

Input n: 10204
Initial count: 0

Steps:

• rem = 4 → not zero → count = 0
• rem = 0 → count = 1
• rem = 2 → count = 1
• rem = 0 → count = 2
• rem = 1 → count = 2

Final Output: 2

Code:

static int zeroes(int n){
    return helper(n, 0);
}

private static int helper(int n, int count){
    if(n == 0){
        return count;
    }
    int rem = n % 10;

    if(rem == 0){
        return helper(n / 10, count + 1);
    }
    return helper(n / 10, count);
}

---

Q 3. Number of steps to reduce a number to zero

Given a non-negative integer n. We need to reduce it to zero using the following steps:

• If the current number is even, divide it by 2.
• If the current number is odd, subtract 1 from it.

Each operation counts as one step. Return the total number of steps required to reduce the number to zero.

Approach:

To solve this problem using recursion:

• Use a helper function that takes the current number n and a step counter count.
• If n is 0, return the current count (base case).
• If n is even, divide it by 2 and increment the step count.
• If n is odd, subtract 1 and increment the step count.
• Recursively call the function with the new value of n and the updated step count.

This continues until n becomes zero.

Example:

Input: n = 14

Steps:

• 14 is even → 14 / 2 = 7 → steps = 1
• 7 is odd → 7 - 1 = 6 → steps = 2
• 6 is even → 6 / 2 = 3 → steps = 3
• 3 is odd → 3 - 1 = 2 → steps = 4
• 2 is even → 2 / 2 = 1 → steps = 5
• 1 is odd → 1 - 1 = 0 → steps = 6

Output: 6

Code:

static int numberOfSteps(int n){
    return helper(n, 0);
}

private static int helper(int n, int count){
    if(n == 0){
        return count;
    }

    if(n % 2 == 0){
        return helper(n / 2, count + 1);
    }
    return helper(n - 1, count + 1);
}

---

Q 4. Check string is palindrome or not:

Given a string, and We need to check whether it is a palindrome or not.
A string is considered a palindrome if it reads the same backward as forward.
For example, "madam" and "racecar" are palindromes.

Approach:

To solve this using recursion:

• Create a helper function that takes the string, a start index, and an end index.
• If start >= end, it means we've compared all characters — return true.
• If characters at start and end are not the same, return false.
• Otherwise, move inward by calling the function with start + 1 and end - 1.
• This process continues until either a mismatch is found or all characters match.

Example:

Input: "madam"

Steps:

• Compare 'm' and 'm' → match
• Compare 'a' and 'a' → match
• Compare 'd' and 'd' (center) → match

Since all characters match from both ends, the string is a palindrome.

Output: true

Code:

static boolean isPalindrome(String str) {
    return helper(str, 0, str.length() - 1);
}

private static boolean helper(String str, int start, int end) {
    if (start >= end) {
        return true;
    }

    if (str.charAt(start) != str.charAt(end)) {
        return false;
    }

    return helper(str, start + 1, end - 1);
}

---

Q 5. Check array is sorted or not:

Given an array of integers. You need to determine whether the array is sorted in ascending order.
An array is considered sorted if for every index i, arr[i] <= arr[i+1].

Approach:

To solve this using recursion:

• Start from index 0 and check if the current element is less than or equal to the next element.
• If at any index arr[i] > arr[i+1], return false — array is not sorted.
• If you reach the second last index without returning false, return true.
• Recursively check the array from index i to i+1.

Example:

Input: [1, 2, 3, 4, 5]

Steps:

• Compare 1 and 2 → ok
• Compare 2 and 3 → ok
• Compare 3 and 4 → ok
• Compare 4 and 5 → ok

Since all elements are in increasing order, the array is sorted.

Output: true

Code:

static boolean isSorted(int[] arr) {
    return helper(arr, 0);
}

private static boolean helper(int[] arr, int index) {
    if (index == arr.length - 1) {
        return true; // Reached end of array
    }

    if (arr[index] > arr[index + 1]) {
        return false; // Not in order
    }

    return helper(arr, index + 1); // Check next pair
}

---

Q 6. Reverse an array:

Given an array of integers.
We need to reverse the array using recursion — that means the first element should become the last, the second should become the second last, and so on.

Approach:

To reverse the array recursively:

• Use two pointers — one starting from the beginning (start) and the other from the end (end).
• Swap the elements at start and end.
• Move the pointers closer: increase start by 1 and decrease end by 1.
• Stop when start >= end.

Example:

Input: [1, 2, 3, 4, 5]

Steps:

• Swap 1 and 5 → [5, 2, 3, 4, 1]
• Swap 2 and 4 → [5, 4, 3, 2, 1]
• Pointers meet at center → Done

Output: [5, 4, 3, 2, 1]

Code:

static void reverseArray(int[] arr) {
    helper(arr, 0, arr.length - 1);
}

private static void helper(int[] arr, int start, int end) {
    // Base Case
    if (start >= end) {
        return;
    }

    // Swap elements
    int temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;

    // Recursive call
    helper(arr, start + 1, end - 1);
}

---

Q 7. Pow(x, n):

Given two values:

• x → a double representing the base
• n → an integer representing the exponent

Our task is to calculate xⁿ using recursion, and handle both positive and negative values of n.

Approach:

We use the Exponential Squaring method to calculate xⁿ efficiently in logarithmic time.

What is Exponential Squaring?

Exponential squaring is a divide-and-conquer technique used to compute powers in O(log n) time instead of O(n).
The key idea is:

• If n is even:
  xⁿ = (x^(n/2)) * (x^(n/2))
• If n is odd:
  xⁿ = x * (x^(n/2)) * (x^(n/2))

We recursively compute the smaller power x^(n/2) and square it to build up the result. If n is negative, we convert the problem to 1 / x⁻ⁿ.

Steps:

• Base Case: If n == 0, return 1.
• If n < 0, calculate 1 / x⁻ⁿ.
• Recursively compute half = power(x, n / 2).
• Return half * half if n is even, else return x * half * half.

Example:

Input: x = 2.0, n = 5

Steps:

power(2, 5)

• 2 x power(2, 2) x power(2, 2)
• 2 x power(2, 1) x power(2, 1)
• 2 x (2 x 2) = 8
• Final result = 2 * 8 = 16

Output: 32.0

Code:

static double myPow(double x, int n) {
    long N = n;

    if (N < 0) {
        return 1 / power(x, -N);
    }
    return power(x, N);
}

private static double power(double x, long n) {
    if (n == 0) {
        return 1;
    }

    double half = power(x, n / 2);

    if (n % 2 == 0) {
        return half * half;
    }
    return x * (half * half);
}

---

Q 8. Count Good Numbers:

Given a number n, We need to count the number of "good" digit strings of length n.
A digit string is good if:

• The digits at even indices (0, 2, 4,...) are even digits (0, 2, 4, 6, 8) → 5 choices.
• The digits at odd indices (1, 3, 5,...) are prime digits (2, 3, 5, 7) → 4 choices.

Since the number of such combinations can be very large, return the count modulo 10⁹ + 7.

Approach:

To solve this using recursion:

• First, divide the length n into two parts:
  • evenCount = (n + 1) / 2 → number of even positions (0-based index).
  • oddCount = n / 2 → number of odd positions.
• At each even index, we have 5 choices → so total combinations from even positions = 5^evenCount.
• At each odd index, we have 4 choices → total combinations from odd positions = 4^oddCount.
• The final result is the product of both, under modulo 1_000_000_007.

Exponential Squaring (for efficient power calculation):

We use binary exponentiation (exponential squaring) to compute powers in O(log n) time.
This is crucial to avoid Time Limit Exceeded (TLE) on large n.

Example:

Input: n = 4

Steps:

• Even positions: 2 (index 0 and 2) → 5^2 = 25
• Odd positions: 2 (index 1 and 3) → 4^2 = 16
• Total good numbers: 25 * 16 = 400

Output: 400

Code:

static int countGoodNumbers(long n){
    long mod = 1_000_000_007;
    long evenCount = (n+1) / 2;
    long oddCount = n / 2;

    long evenPart = power(5, evenCount, mod);
    long oddPart = power(4, oddCount, mod);

    return (int) ((evenPart * oddPart) % mod);
}

static long power(long base, long exponent, long mod){
    if (exponent== 0) {
        return 1;
    }

    long half = power(base, exponent / 2, mod);
    long result = (half * half) % mod;

    if (time % 2 == 1) {
        return (base * result) % mod;
    }
    return result;
}

---

What's next:

I’m continuing this journey and will be:

• Posting blogs every 3 days.
• Also learning Web Development — check out my Web Dev Journey Blog.
• You can follow my journey on X (Twitter) where I post regular updates.

---

Conclusion:

Today was all about understanding the core of recursion — base cases, recursive calls, and trusting the function. Some problems felt tricky at first, but breaking them down step-by-step made them easier.

✅ 8 problems solved
📚 Concepts reinforced
🚀 Confidence boosted

Let’s keep the momentum going!

If you're also starting your DSA journey, I hope this blog helps you understand recursion better. Keep learning and keep coding!

If you're on a similar journey, feel free to reach out or follow along — we’re all in this together.