Exploring Recursion in Java: Solving DSA Problems with Stack Building and Stack Falling Approaches

Let’s get started

Introduction:

Recursion is a powerful concept in computer programming that involves a function calling itself to solve a problem. In this blog post, we will explore recursion by solving several Data Structure and Algorithm (DSA) problems using two different approaches: stack building void and stack falling return type. We will implement these solutions in Java and examine how recursion simplifies the problem-solving process.

1. Power of a Number:

class Main{
    public static void main(String[] args) {
        System.out.println(power(2, 5));
        power(2, 5, 1);

    }

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

    static void power(int n, int p, int val) {
        if (p == 0) {
            System.out.println(val);
            return;
        }
        power(n, p - 1, n * val);
    }
}

2. Count Zero in a Given Number:

public class Main{
    // Count zero in given number
    public static void main(String[] args) {
        System.out.println(countZeros(134040));
        countZeros(134040, 0);
    }

    static int countZeros(int num) {
        if (num == 0) {
            return 0;
        }
        int count = countZeros(num / 10);
        if (num % 10 == 0) {
            return 1 + count;
        }
        return count;
    }

    static void countZeros(int num, int count) {
        if (num == 0) {
            System.out.println(count);
            return;
        }
        if (num % 10 == 0) {
            countZeros(num / 10, 1 + count);
        } else {
            countZeros(num / 10, count);
        }
    }
}

3. Sum of N Natural Numbers:

public class Main{
    public static void main(String[] args) {
        System.out.println(sumNatural(5));
        sumNatural(5, 0);
    }

    static int sumNatural(int num) {
        if (num == 0)
            return 0;
        return num + sumNatural(num - 1);
    }

    static void sumNatural(int num, int sum) {
        if (num == 0) {
            System.out.println(sum);
            return;
        }
        sumNatural(num - 1, num + sum);
    }
}

4. Sum of the fraction series :

public class Main{
    // 1/1^1 + 2 / 2 ^2 + 3 / 3^3 
    public static void main(String[] args) {
        System.out.println(sumSeries(2));
        sumNatural(2, 0);
    }

    static double sumSeries(int num) {
        if (num == 0)
            return 0;
        return eleVal(num) + sumSeries(num - 1);
    }

    static void sumNatural(int num, double sum) {
        if (num == 0) {
            System.out.println(sum);
            return;
        }
        sumNatural(num - 1, eleVal(num) + sum);
    }

    static double eleVal(int n){
        return  (n/Math.pow(n, n));
    }
}

5. Check the Given Number is Prime or Not?:

public class Main {
    // Recursive approach for checking prime number using stack building
    public static boolean checkPrimeStackBuilding(int number, int divisor) {
        if (number <= 1) {
            return false;
        }
        if (divisor == 1) {
            return true;
        }
        if (number % divisor == 0) {
            return false;
        }
        return checkPrimeStackBuilding(number, divisor - 1);
    }

    // Recursive approach for checking prime number using stack falling
    public static boolean checkPrimeStackFalling(int number) {
        int divisor = (int) Math.sqrt(number);
        return checkPrimeStackBuilding(number, divisor);
    }

    public static void main(String[] args) {
        int number = 17;
        
        boolean isPrime = checkPrimeStackBuilding(number, (int) Math.sqrt(number));
        if (isPrime) {
            System.out.println(number + " is a prime number.");
        } else {
            System.out.println(number + " is not a prime number.");
        }
        
        isPrime = checkPrimeStackFalling(number);
        if (isPrime) {
            System.out.println(number + " is a prime number.");
        } else {
            System.out.println(number + " is not a prime number.");
        }
    }
}

6. Check the Given Number is Armstrong or Not?:

public class Main {
    // Recursive approach for checking Armstrong number using stack building
    public static int power(int base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        return base * power(base, exponent - 1);
    }

    public static boolean checkArmstrongStackBuilding(int number, int digits) {
        if (number == 0) {
            return true;
        }
        
        int digit = number % 10;
        int poweredDigit = power(digit, digits);
        
        return poweredDigit + checkArmstrongStackBuilding(number / 10, digits);
    }

    // Recursive approach for checking Armstrong number using stack falling
    public static boolean checkArmstrongStackFalling(int number) {
        int digits = String.valueOf(number).length();
        return checkArmstrongStackBuilding(number, digits);
    }

    public static void main(String[] args) {
        int number = 153;
        
        boolean isArmstrong = checkArmstrongStackBuilding(number, String.valueOf(number).length());
        if (isArmstrong) {
            System.out.println(number + " is an Armstrong number.");
        } else {
            System.out.println(number + " is not an Armstrong number.");
        }
        
        isArmstrong = checkArmstrongStackFalling(number);
        if (isArmstrong) {
            System.out.println(number + " is an Armstrong number.");
        } else {
            System.out.println(number + " is not an Armstrong number.");
        }
    }
}

7. Check Palindrome String:

public class Main {
    
    public static void main(String[] args) {

        String s1 = "kushagra";
        int l1 = s1.length();

        String s2 = "wow";
        int l2 = s2.length();

        System.out.println(isPalindrome1(s1, 0, l1 - 1));
        System.out.println(isPalindrome1(s2, 0, l2 - 1));

        isPalindrome2(s1, 0, l1 - 1, true);
        isPalindrome2(s2, 0, l2 - 1, true);

    }

    static boolean isPalindrome1(String str, int lci, int uci) {

        if (str.charAt(lci) != str.charAt(uci))
            return false;

        if (lci == uci || uci < lci)
            return true;

        return isPalindrome1(str, lci + 1, uci - 1);

    }

    static void isPalindrome2(String str, int lci, int uci, Boolean b) {

        if (str.charAt(lci) != str.charAt(uci)) {
            b = false;
        }

        if (lci == uci || uci < lci) {
            System.out.println(b);
            return;
        }

        isPalindrome2(str, lci + 1, uci - 1, b);
    }
}

8. Array Search the Element From the Last (lastIndexOf):

public class Main {
    public static void main(String[] args) {
        int[] ary = { 1, 2, 3, 4, 5 };
        int li = ary.length - 1;

        int ele = 5;
        System.out.println(lastIndexElementSearch1(ary, li, ele));
        lastIndexElementSearch2(ary, li, ele);

        System.out.println();

        ele = 7;
        System.out.println(lastIndexElementSearch1(ary, li, ele));
        lastIndexElementSearch2(ary, li, ele);
    }

    static int lastIndexElementSearch1(int[] arr, int index, int ele) {

        if (index < 0)
            return -1;

        if (arr[index] == ele) {
            return index;
        }

        return lastIndexElementSearch1(arr, index - 1, ele);
    }

    static void lastIndexElementSearch2(int[] arr, int index, int ele) {

        if (index < 0) {
            System.out.println("Element " + ele + " not found :(");
            return;
        }

        if (arr[index] == ele) {
            System.out.println("Element " + ele + " found at last index " + index + " :)");
            return;
        }

        lastIndexElementSearch2(arr, index - 1, ele);
    }
}

9. Count all Occurrences of Search Element:

public class Main {
    public static void main(String[] args) {
        int[] ary = { 5, 2, 4, 5, 5, 2, 1, 9, 0, 3, 5, 7, 6, 1 };
        int li = ary.length - 1;

        int ele = 5;
        System.out.println(ele + " ---> " + countAllOccurrences(ary, li, ele));
        countAllOccurrences(ary, li, ele, 0); // Initial count should be 0

        System.out.println();

        ele = 19;
        System.out.println(ele + " ---> " + countAllOccurrences(ary, li, ele));
        countAllOccurrences(ary, li, ele, 0); // Initial count should be 0
    }

    static int countAllOccurrences(int[] arr, int index, int ele) {

        if (index < 0)
            return 0;

        if (arr[index] == ele) {
            return 1 + countAllOccurrences(arr, index - 1, ele);
        }

        return countAllOccurrences(arr, index - 1, ele);
    }

    static void countAllOccurrences(int[] arr, int index, int ele, int count) {

        if (index < 0) {
            System.out.println(count);
            return;
        }

        if (arr[index] == ele) {
            count++;
        }

        countAllOccurrences(arr, index - 1, ele, count);
    }
}

10. Get all found element index (Search Element), store the result in an array:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
   public static void main(String[] args) {

        ArrayList<Integer> list = new ArrayList<Integer>();

        int[] ary = { 5, 1, 2, 5, 4, 5, 5 };

        int ele = 5;

        allIndexElementSearch(ary, 0, ele, list);
        System.out.println(list);

        System.out.println(allIndexElementSearch(ary, 0, ele));
    }

    static ArrayList<Integer> allIndexElementSearch(int[] arr, int index, int ele) {

        ArrayList<Integer> list = new ArrayList<>();

        if (index > arr.length - 1) {
            return list;
        }

        if (arr[index] == ele) {
            list.add(index);
            list.addAll(allIndexElementSearch(arr, index + 1, ele));
            return list;
        }

        return allIndexElementSearch(arr, index + 1, ele);
    }

    static void allIndexElementSearch(int[] arr, int index, int ele, ArrayList<Integer> list) {

        if (index > arr.length - 1) {
            return;
        }

        if (arr[index] == ele) {
            list.add(index);
        }

        allIndexElementSearch(arr, index + 1, ele, list);
    }
}

11. Given an Array, find the element and replace the value with the given value, search and replace all occurrences:

import java.util.Arrays;

public class Main {
   public static void main(String[] args) {

        int[] ary = { 5, 1, 2, 5, 4, 5, 5 };

        int ele = 5;

        int rw = 0;

        replaceElement(ary, 0, ele, rw);

        for (int element : ary) {
            System.out.print(element + " ");
        }

        System.out.println();

    }

    static void replaceElement(int[] arr, int index, int ele, int rw) {

        if (index > arr.length - 1) {
            return;
        }

        if (arr[index] == ele) {
            arr[index] = rw;
        }

        replaceElement(arr, index + 1, ele, rw);
    }
}

12. Given a String, find the adjacent element if it is the same as the previous element, so replace the element with ‘#’:

public class Main {
    // Recursive approach for replacing adjacent elements using stack building
    public static String replaceAdjacentStackBuilding(String str, int index) {
        if (index >= str.length() - 1) {
            return str;
        }
        
        StringBuilder sb = new StringBuilder(str);
        if (sb.charAt(index) == sb.charAt(index + 1)) {
            sb.setCharAt(index + 1, '#');
        }
        
        return replaceAdjacentStackBuilding(sb.toString(), index + 1);
    }

    // Recursive approach for replacing adjacent elements using stack falling
    public static String replaceAdjacentStackFalling(String str, int index) {
        if (index >= str.length() - 1) {
            return str;
        }
        
        if (str.charAt(index) == str.charAt(index + 1)) {
            str = str.substring(0, index + 1) + '#' + str.substring(index + 2);
        }
        
        return replaceAdjacentStackFalling(str, index + 1);
    }

    public static void main(String[] args) {
        String str = "aabbcc";
        
        replaceAdjacentStackBuilding(str, 0);
        System.out.println("String after replacing adjacent elements (Stack Building): " + str);
        
        String result = replaceAdjacentStackFalling(str, 0);
        System.out.println("String after replacing adjacent elements (Stack Falling): " + result);
    }
}

13. Given a String, find the adjacent element if it is the same as the previous element, so add a star in between:

public class Main {
    // Recursive approach for adding stars using stack building
    public static String addStarsStackBuilding(String str, int index) {
        if (index >= str.length() - 1) {
            return str;
        }
        
        StringBuilder sb = new StringBuilder(str);
        if (sb.charAt(index) == sb.charAt(index + 1)) {
            sb.insert(index + 1, '*');
        }
        
        return addStarsStackBuilding(sb.toString(), index + 1);
    }

    // Recursive approach for adding stars using stack falling
    public static String addStarsStackFalling(String str, int index) {
        if (index >= str.length() - 1) {
            return str;
        }
        
        if (str.charAt(index) == str.charAt(index + 1)) {
            str = str.substring(0, index + 1) + '*' + str.substring(index + 1);
        }
        
        return addStarsStackFalling(str, index + 1);
    }

    public static void main(String[] args) {
        String str = "aabbcc";
        
        String result = addStarsStackBuilding(str, 0);
        System.out.println("String after adding stars (Stack Building): " + result);
        
        result = addStarsStackFalling(str, 0);
        System.out.println("String after adding stars (Stack Falling): " + result);
    }
}

Thanks for Reading ❤❤