Recursion

➤ Java Bean with Examples
➤ How to Code a Game
➤ Array Programs in Java
➤ Java Inline Thread Creation
➤ Java Custom Exception
➤ Hibernate vs JDBC
➤ Object Relational Mapping
➤ Check Oracle DB Size
➤ Check Oracle DB Version
➤ Generation of Computers
➤ XML Pros & Cons
➤ Git Analytics & Its Uses
➤ Top Skills for Cloud Professional
➤ How to Hire Best Candidates
➤ Scrum Master Roles & Work
➤ CyberSecurity in Python
➤ Protect from Cyber-Attack
➤ Solve App Development Challenges
➤ Top Chrome Extensions for Twitch Users
➤ Mistakes That Can Ruin Your Test Metric Program

Deep Dive Into Recursion | Let us see some common and popular data structures and algorithms related to recursion. We will also discuss the following problems:- Tower of Hanoi. Also see:- Basic Math DSA, Bit DSA, Array DSA, String DSA.

Table of Contents

A function that calls itself directly or indirectly is called a recursive method/function. Example:-

// direct
void fun1() {
   // code
   fun1();
}
// indirect
void fun1() {
   // code
   fun2();
}
void fun2() {
   // code
   fun1();
}

Indirect recursion is not very common. We will mainly focus on direct recursion. Recursive method should contain a base case else JVM will through StackOverflowError due to infinite stack.

class Test {
    static void fun1(int n) {
        // base case
        if (n == 0) {
            return;
        }
        System.out.println("Hi");
        fun1(n - 1);
    }

    public static void main(String[] args) {
        fun1(5);
    }
}

Applications of Recursion:-

  • Many algorithm techniques are based on recursion like:- Dynamic programming, Backtracking, Divide and conquer (Binary search, Quick sort, and merge sort)
  • Many problems are inherently recursive like Tower of Hanoi, and DFS-based traversals (DFS of graph and in-order/pre-order/post-order traversal of tree).
  • Searching for a file in the computer.
public class Test {
    public static void main(String[] args) {
        binaryEquivalent(10); // 1010
    }

    private static void binaryEquivalent(int n) {
        if (n == 0) {
            return;
        }
        binaryEquivalent(n / 2);
        System.out.print(n % 2);
    }
}
public class Test {
    public static void main(String[] args) {
        System.out.println(log2N(10)); // 3
    }

    private static int log2N(int n) {
        if (n == 1) {
            return 0;
        }
        return 1 + log2N(n / 2);
    }
}
public class Test {
    public static void main(String[] args) {
        System.out.println(log3N(10)); // 3
    }

    private static int log3N(int n) {
        if (n < 3) {
            return 0;
        }
        return 1 + log3N(n / 3);
    }
}

N = 5 => 5 4 3 2 1
N = 2 => 2 1

public class Test {
    public static void main(String[] args) {
        System.out.println(printNto1(9)); 
        // 9 8 7 6 5 4 3 2 1
    }

    private static int printNto1(int n) {
        if (n == 1) {
            return 1;
        }
        System.out.print(n + " ");
        return printNto1(n - 1);
    }
}
public class Test {
    public static void main(String[] args) {
        print1toN(9); // 1 2 3 4 5 6 7 8 9 
    }

    private static void print1toN(int n) {
        if (n == 0) {
            return;
        }
        print1toN(n - 1);
        System.out.print(n + " ");
    }
}

Tail Recursion

Tail recursion is a type of recursion where the recursive call is the last operation in the function. This means that there’s nothing left to do after the function calls itself. Because of this, the compiler or interpreter can optimize the recursive calls to avoid using up too much memory. It’s like handing off a task and immediately being done with it—no extra steps!

Assume for a given problem we have 2 solutions:- one with tail recursive and another one without tail recursive. Then we prefer the tail recursive because it will give better performance.

The previous print1toN() method is not a tail recursive. Can we make it tail-recursive? Here is the equivalent tail recursive method call.

public class Test {
    public static void main(String[] args) {
        print1toN(9, 1); // 1 2 3 4 5 6 7 8 9
    }

    // initially pass k=1
    private static void print1toN(int n, int k) {
        if (n == 0) {
            return;
        }
        System.out.print(k + " ");
        print1toN(n - 1, k + 1);
    }
}

Can we convert every non-tail recursive method to a tail recursive method? No, we can’t. For example merge sort and quick sort. Quick sort is tail recursive and Merge sort is non-tail recursive. This is one of the reasons why quick sort is faster than merge sort.

In tree, pre-order traversal, and in-order traversal are tail-recursive whereas post-order traversal is non-tail recursive. Therefore pre-order traversal and in-order traversal are preferred over post-order traversal.

Whether the below-given program is tail-recursive or not?

private static long factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

No. It is not a tail recursive because a recursive call is not the last thing. Here method has to multiply the results of all call stacks.

public class Test {
    public static void main(String[] args) {
        System.out.println(factorial(5, 1));
    }

    // initially pass k=1
    private static long factorial(int n, long k) {
        if (n == 0 || n == 1) {
            return k;
        }
        return factorial(n - 1, k * n);
    }
}

The sum of Natural Using Recursion

Find the sum of the first N natural numbers using recursion.

N = 2; O/P: 3
N = 4; O/P: 10
N = 5; O/P: 15

public class Test {
    public static void main(String[] args) {
        System.out.println(sumOfNaturalNums(5, 1)); // 15
    }

    private static long sumOfNaturalNums(int n, long k) {
        if (n == 1) {
            return k;
        }
        return sumOfNaturalNums(n - 1, k + n);
    }
}

Time complexity O(n) and space complexity O(n).

Factorial

Find the factorial of a number N where n >= 0.

public class Test {
    public static void main(String[] args) {
        System.out.println(factorial(5, 1)); // 15
    }

    private static long factorial(int n, long k) {
        if (n == 0 || n == 1) {
            return k;
        }
        return factorial(n - 1, k * n);
    }
}

Fibonacci Number

Find nth Fibonacci number where n >= 0.

public class Test {
    public static void main(String[] args) {
        System.out.println(fib(4)); // 3
    }

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

The time complexity of the Fibonacci function provided is exponential, specifically O(2n). This is because each call to fib(n) results in two recursive calls: fib(n - 1) and fib(n - 2). As n increases, the number of calls grows exponentially, leading to the exponential time complexity.

Efficient algorithms like dynamic programming or matrix exponentiation can solve the Fibonacci sequence in O(n) or even O(log n) time. See More:- Fibonacci Number Using Matrix Exponentiation

Palindrome Check

For a given string, check whether it is a palindrome string or not.

public class Test {
    public static void main(String[] args) {
        String string = "abbcbba";
        System.out.println(isPalindrome(string, 0, string.length() - 1)); // true
    }

    private static boolean isPalindrome(String str, int start, int end) {
        if (start >= end) {
            return true;
        }
        return (str.charAt(start) == str.charAt(end)) && 
                isPalindrome(str, start + 1, end - 1);
    }
}

Time complexity O(n) and space complexity O(n).

The sum of Digits Using Recursion

N = 253; O/P: 10
N = 9987; O/P: 33
N = 10; O/P: 1

public class Test {
    public static void main(String[] args) {
        System.out.println(sumOfDigits(251, 0)); // 8
    }

    private static int sumOfDigits(int n, int count) {
        if (n == 0) {
            return count;
        }
        return sumOfDigits(n / 10, count + (n % 10));
    }
}

Time complexity O(d) and auxiliary space O(d).

Rope Cutting

Given a rope of length N, you need to find the maximum number of pieces you can make such that the length of every piece is in set {a, b, c} for given three values a, b, and c. The length of every piece (often cuts) should be in set {a, b, c}.

I/P: n = 5, a = 2, b = 5, c = 1
O/P: 5; We can make 5 pieces of length 1 each.

I/P: n = 23, a = 12, b = 9, c = 11
O/P: 2; We can make 2 pieces of length 11 and 12

I/P: n = 5, a = 4, b = 2, c = 6
O/P: -1; Not Possible

Corner case:- n = 9, a = 2, b = 2, c = 2
O/P: -1; Not Possible

Base Case:

  • If N is 0, return 0 because no further pieces can be made.
  • If N is negative, return a minimum value (e.g., Integer.MIN_VALUE) to indicate it’s not a valid cut.

Recursive Case:

  • For each possible cut length in {a, b, c}, recursively reduce the length of the rope by that cut length.
  • Return the maximum number of pieces obtained by making each cut.

Combine Results: Take the maximum of the three results (for cuts of length a, b, and c) and add 1 (for the current cut) to get the total number of pieces.

public class Test {
    public static void main(String[] args) {
        int n = 23, a = 11, b = 9, c = 12;
        System.out.println(maxPieces(n, a, b, c)); 
        // 2 as (11, 12) and (12, 11)
    }

    private static int maxPieces(int n, int a, int b, int c) {
        if (n == 0)
            return 0; // base case
        if (n < 0)
            return -1;

        int res = Math.max(maxPieces(n - a, a, b, c), 
                           Math.max(maxPieces(n - b, a, b, c), 
                                   maxPieces(n - c, a, b, c)
                            )
                   );
        if (res == -1) {
            return -1;
        }
        return 1 + res;
    }
}

Time complexity O(3^n)

This problem has a better solution using Dynamic programming, which we will discuss in the dynamic programming section.

Tower of Hanoi

There are 3 points A, B, and C. Point A has N discs. We have to move all disc from A to C with following rules:-

  1. Only one disc moves at a time.
  2. Larger disc can not be placed above smaller disc.
  3. Only the top disc of a tower can be moved (Working as a Stack).

Example-1: n=1 then move disc 1 from A to C.

Example-2: N=2 Then
Move disc 1 from A to B
Move disc 2 from A to C
Move disc 1 from B to C

public class Test {
    public static void main(String[] args) {
        toh(3, 'A', 'B', 'C');
    }

    // n, a=initial, b=intermediate, c=destination
    private static void toh(int n, char a, char b, char c) {
        if (n == 1) {
            System.out.println("Move 1 from " + a + " to " + c);
            return;
        }
        toh(n - 1, a, c, b);
        System.out.println("Move " + n + " from " + a + " to " + c);
        toh(n - 1, b, a, c);
    }
}

Number of movements for a given N.
T(1) = 1
T(n) = 2T(n-1) + 1 = 1 + 2 + 4 + … + 2^(n-1) = (1 * 2^n -1)/ 2-1 = 2^n -1

If we also want to count the number of moves, then it can be done as:-

class Hanoi {
    // Function to print the moves and return the total number of moves
    public long toh(int n, int from, int to, int aux) {
        if (n == 0) {
            return 0;
        }
        long moves = 0;

        // Move n-1 disks from source to auxiliary, so they are out of the way
        moves += toh(n - 1, from, aux, to);

        // Move the nth disk from source to destination
        System.out.println("move disk " + n + " from rod " + from + " to rod " + to);
        moves++;

        // Move the n-1 disks that we left on auxiliary to destination
        moves += toh(n - 1, aux, to, from);

        return moves;
    }

    public static void main(String[] args) {
        Hanoi hanoi = new Hanoi();
        int n = 3; // Number of disks
        long totalMoves = hanoi.toh(n, 1, 3, 2); 
        // 1: Source rod, 3: Destination rod, 2: Auxiliary rod
        System.out.println("Total moves: " + totalMoves);
    }
}

Generate Subsets

A string of length N is given, the task is to generate all subsets of the string. All the characters in the input string are distinct. This problem also can be seen as generating a sub-sequence of the string.

I/P: s = “AB”
O/P: “”, “A”, “B”, “AB”

I/P: s = “ABC”
O/P: “”, “A”, “B”, “C”, “AB”, “AC”, “BC”, “ABC”

For a string of length N, there are going to be 2^n subsets.

We can generate all subsets for length N string using subsets for length N-1 string. We can solve this problem either using Bitwise (link) or recursion.

public class Test {
    public static void main(String[] args) {
        subset("ABC", "", 0);
    }

    private static void subset(String string, String current, int i) {
        if (i == string.length()) {
            System.out.print(current + " ");
            return;
        }
        subset(string, current, i + 1);
        subset(string, current + string.charAt(i), i + 1);
    }
}

Time Complexity: O(n * 2^n), and Space Complexity: O(n).

The iterative approach is more memory-efficient because it avoids the overhead associated with function calls and the additional stack space required for recursion. The iterative approach has time complexity is O(n * 2^n) and Space Complexity: as O(1).

Josephus Problem

The Josephus Problem is a classic theoretical problem in mathematics and computer science, named after Flavius Josephus, a Jewish historian. The problem can be defined as follows:

Problem Statement:

  • N people are standing in a circle, numbered from 1 to n.
  • Starting from a given position, you count k people around the circle and remove the kth person.
  • The counting begins again from the next person, and you keep going around the circle, removing every kth person.
  • The process continues until only one person remains.
  • The task is to determine the position of the last person remaining.

I/P: n=7, k=3
O/P: 4

  • Starting with: 1, 2, 3, 4, 5, 6, 7
  • Remove the 3rd person (3): 1, 2, 4, 5, 6, 7
  • Starting from the next person (4), remove the 3rd person (6): 1, 2, 4, 5, 7
  • Starting from the next person (7), remove the 3rd person (2): 1, 4, 5, 7
  • Starting from the next person (4), remove the 3rd person (7): 1, 4, 5
  • Starting from the next person (1), remove the 3rd person (5): 1, 4
  • Starting from the next person (1), remove the 3rd person (1): 4
  • The final remaining person is at position 4.
public class Test {
    public static void main(String[] args) {
        int n = 7;
        int k = 3;
        int result = josephus(n, k);
        // Adjust result for 1-based indexing
        System.out.println("The position of the " + 
                    "last person standing is: " + (result + 1));
    }

    private static int josephus(int n, int k) {
        // base case: only one person remains
        if (n == 1) {
            return 0;
        }
        // recursive case: find the position in smaller circle
        // and adjust the result
        return (josephus(n - 1, k) + k) % n;
    }
}

Subset Sum Problem

Given a set of integers and a target sum, return the count of subsets whose sum is equal to the target sum.

Array = {10, 5, 2, 3, 6}; Sum = 8
O/P: 2 [Because of subset (5, 3) and (2, 6)]

Array = {1, 2, 3}; Sum = 4
O/P: 1 [Because of subset (1, 3)]

Array = {10, 20, 15}; Sum = 37
O/P: 0

Subset of {1, 2, 3} are {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}. The empty and whole array are also subsets. For an array of length n, the number of subsets will be 2^n.

Array = {10, 20, 15}; Sum = 0
O/P: 1 [Because of empty set {} ]

public class Test {
    public static void main(String[] args) {
        int[] array = { 10, 20, 15, 5 };
        int sum = 25;
        System.out.println(countOfSubsetSum(array, array.length, sum));
    }

    private static int countOfSubsetSum(int[] array, int n, int sum) {
        if (n == 0) {
            return sum == 0 ? 1 : 0;
        }
        return countOfSubsetSum(array, n - 1, sum) + 
                countOfSubsetSum(array, n - 1, sum - array[n - 1]);
    }
}

Time complexity O(2^n). This program can be optimized through backtracking or dynamic programming. In dynamic programming, it will have the time complexity of O(n * sum).

For a given string, find all the permutations of the given string. For a string of length n, there are n! permutations.

String = “ABC”
O/P: ABC ACB BAC BCA CAB CBA

String = “AB”
O/P: AB BA

String = “”
O/P: Nothing to be printed

public class Test {
    public static void main(String[] args) {
        String str = "ABD";
        List<String> result = new ArrayList<>();
        permute(str, "", result);
        System.out.println(result);
    }

    private static void permute(String str, String prefix, List<String> result) {
        if (str.length() == 0) {
            result.add(prefix);
        } else {
            for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                String remaining = str.substring(0, i) + str.substring(i + 1);
                permute(remaining, prefix + ch, result);
            }
        }
    }
}

For each character, generate all permutations of the remaining characters and add the current character to the prefix.

Reverse a Stack

You are given a stack. You have to reverse the stack using recursion. Problem Link:- Reverse a Stack

import java.util.Stack;

public class Test {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.add(10);
        stack.add(20);
        stack.add(30);
        stack.add(40);
        reverse(stack);
        System.out.println(stack);
    }

    static void reverse(Stack<Integer> s) {
        if (s.isEmpty()) {
            return;
        }
        int temp = s.pop();
        reverse(s);
        insertAtBottom(s, temp);
    }

    private static void insertAtBottom(Stack<Integer> s, int x) {
        if (s.isEmpty()) {
            s.push(x);
            return;
        }
        int temp = s.pop();
        insertAtBottom(s, x);
        s.push(temp);
    }
}

Sort a Stack

Given a stack, the task is to sort it such that the top of the stack has the greatest element. Problem Link:- Sort a Stack

import java.util.Stack;

public class Test {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.add(10);
        stack.add(30);
        stack.add(40);
        stack.add(20);
        sort(stack);
        System.out.println(stack);
    }

    public static Stack<Integer> sort(Stack<Integer> s) {
        if (s.isEmpty()) {
            return s;
        }
        int temp = s.pop();
        sort(s);
        insertInDescendingOrder(s, temp);
        return s;
    }

    private static void insertInDescendingOrder(Stack<Integer> s, int element) {
        if (s.isEmpty() || s.peek() >= element) {
            s.push(element);
        } else {
            int temp = s.pop();
            insertInDescendingOrder(s, element);
            s.push(temp);
        }
    }
}

Count Good Numbers

Problem Link:- Count Good Numbers. Solution

Total even numbers from 0 to 9 are [0, 2, 4, 6, 8] = 5. Total prime numbers from 0 to 9 are [2, 3, 5, 7] = 4.

public class Test {
    private static long MOD = 1_000_000_007;

    public static void main(String[] args) {
        int n = 4;
        System.out.println(countGoodNumbers(n));
    }

    private static int countGoodNumbers(int n) {
        long even = (n + 1) / 2;
        long odd = n / 2;
        long first = power(5, even) % MOD; // [0, 2, 4, 6, 8] = 5
        long second = power(4, odd) % MOD; // [2, 3, 5, 7] = 4
        return (int) ((first * second) % MOD);
    }

    private static long power(long x, long n) {
        if (n == 0) {
            return 1;
        }
        long half = power(x, n / 2);
        return n % 2 == 0 ? (half * half) % MOD : (half * half * x) * MOD;
    }
}

Generate Parentheses

Problem Link:- Generate Parentheses. Solution

Algorithm:

  1. Develop a recursive function with parameters (String curr, int open, int closed, int total, List<String> ans).
  2. If the length of curr is equal to 2 * total, then add curr to ans and return.
  3. Check if open < total, add '(' to curr and call this function with updated values of curr and open (open + 1).
  4. Check if closed < open, add ')' to curr and call this function with updated values of curr and closed (closed + 1).
import java.util.ArrayList;
import java.util.List;

public class Test {

    public static void main(String[] args) {
        int n = 3;
        Test test = new Test();
        System.out.println(test.generateParenthesis(n));
    }

    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        solve("", 0, 0, n, ans);
        return ans;
    }

    private void solve(String curr, int open, int closed, int total, List<String> ans) {
        if (curr.length() == 2 * total) {
            ans.add(curr);
            return;
        }
        if (open < total) {
            solve(curr + "(", open + 1, closed, total, ans);
        }
        if (closed < open) {
            solve(curr + ")", open, closed + 1, total, ans);
        }
    }
}

Subset Sum

Problem Link:- Subset Sum

public class SubsetSum {
    public static boolean isSubsetPresent(int n, int k, int[] a) {
        boolean[][] dp = new boolean[n + 1][k + 1];

        // Initialize DP table
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true; // If sum is 0, empty subset is always a solution
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                if (a[i - 1] <= j) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - a[i - 1]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n][k];
    }

    public static void main(String[] args) {
        int n = 3;
        int k = 5;
        int[] a = {1, 2, 3};
        System.out.println(isSubsetPresent(n, k, a)); // Output: true
    }
}

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Leave a Comment

Your email address will not be published. Required fields are marked *