Chapter 16 : Recursion(Part 2)

Recursion is one of the most powerful problem-solving techniques in computer science. It allows us to break down complex tasks into smaller, manageable subproblems. In Chapter 15: Recursion (Part 1), we laid the foundation for understanding how recursion works, including base cases and recursive cases. Now, in Chapter 16: Recursion (Part 2), we are going to explore more advanced recursive problems that will deepen our understanding and showcase how elegant recursive solutions can be.

We’ll be tackling real-world scenarios where recursion simplifies problem-solving, from tiling and string manipulation to pairing friends and working with binary strings. By the end of this chapter, you’ll not only be more confident in applying recursion but also ready to tackle more advanced algorithmic challenges like Divide and Conquer.

The key topics covered in this chapter include:

---

i)Tiling Problem

The tiling problem is a classic combinatorial problem in the domain of dynamic programming and recursion. It involves placing 2x1 tiles on a 2xn board in different configurations and finding the total number of ways to tile the board.

This problem is fundamental for understanding how recursive relationships can be used to break down complex problems into manageable, smaller subproblems. Let's dive into the theory and step-by-step explanation.

---

Problem Restatement:

We are given a board of size 2 * n (2 rows and n columns) and tiles of size *2 \ 1** (2 rows and 1 column). The goal is to determine how many different ways we can fill the board using the tiles. The tiles can be placed:

• Vertically (covering exactly one column),

• Horizontally (covering two adjacent cells in two rows and one column).

Our task is to find the number of ways we can fill the entire board for any given n.

---

Visualizing the Board and Tiles:

Understanding the Board and Tile Dimensions:

• Board: The board is represented as a grid with two rows and n columns. For example, if n = 3, we have a board that looks like:

    [_ _ _]  -> 2 rows and 3 columns (2x3)
    [_ _ _]
  

• Tile: The tiles we are using are of size 2x1, meaning they can either:

  • Stand vertically, occupying one column and both rows, or

  • Lay horizontally, occupying one row but covering two adjacent columns.

Example: n = 3

Consider a board of size 2x3. Here’s how the tiles can be placed:

1. All tiles placed vertically:

    [|] [|] [|]
    [|] [|] [|]
   

2. Two tiles placed horizontally and one tile vertically:

    [— —] [|]
    [— —] [|]
   

3. One tile placed vertically and two tiles horizontally:

    [|] [— —]
    [|] [— —]
   

In this case, for n = 3, there are exactly 3 ways to fill the board using the tiles.

---

Breaking Down the Problem: Recursive Approach

Key Concept:

To solve this problem recursively, we can think about how we place the tiles one at a time. For every placement of a tile, we reduce the size of the problem.

We have two options at each step:

1. Placing a tile vertically: This will occupy a single column, reducing the size of the board from 2xn to 2(n-1)*.

2. Placing two tiles horizontally: These two tiles will cover two adjacent columns, reducing the size of the board from 2xn to 2(n-2)*.

Base Cases:

1. n = 0: There is exactly 1 way to tile a board of size 2x0, which is to not place any tiles at all (an empty board is a valid solution).

2. n = 1: For a board of size 2x1, the only option is to place 1 tile vertically, so there is 1 way to tile the board.

Recursive Relation:

For larger values of n, we build the solution based on the choices we made at previous steps. The total number of ways to tile a board of size 2*n can be expressed as:

F(n) = F(n-1) + F(n-2)

Here’s how this works:

1. F(n-1): Represents the number of ways to tile the board after placing 1 vertical tile (which reduces the size of the board to 2(n-1)*).

2. F(n-2): Represents the number of ways to tile the board after placing 2 horizontal tiles (which reduces the size of the board to 2(n-2)*).

Thus, the total number of ways to tile a 2*n board is the sum of these two recursive steps: the number of ways to tile a 2(n-1)* board and the number of ways to tile a 2(n-2)* board.

---

Understanding Through an Example: n = 4

Consider n = 4:

Board size = 2x4
[_ _ _ _]
[_ _ _ _]

Here’s how the recursion works:

• F(4): The number of ways to tile a 2x4 board.

  • If we place 1 tile vertically: We reduce the problem to tiling a 2x3 board, which can be solved by F(3).

  • If we place 2 tiles horizontally: We reduce the problem to tiling a 2x2 board, which can be solved by F(2).

Thus, the number of ways to tile a 2x4 board is:

F(4) = F(3) + F(2)

From previous results:

• F(3) = 3

• F(2) = 2

So,

F(4) = 3 + 2 = 5

This means there are 5 ways to tile a 2x4 board.

---

Conclusion:

The tiling problem can be solved efficiently using recursion by breaking the problem down into smaller subproblems. The recursive relation F(n) = F(n-1) + F(n-2) is similar to the Fibonacci sequence, where each state depends on the sum of two previous states.

Theoretical Points to Remember:

1. Base cases:

   • n = 0: There's 1 way to tile a 2x0 board (by doing nothing).

   • n = 1: There's 1 way to tile a 2x1 board (by placing 1 vertical tile).

2. Recursive relation:

   • For larger n, the total number of ways is the sum of two cases:

     • Placing a vertical tile, which reduces the board size to n-1.

     • Placing two horizontal tiles, which reduces the board size to n-2.

---

ii) Tiling Problem Code

Code Walkthrough:

public class Q11 {
    // Function to count the number of ways to tile a 2*n board
    public static int tilingProblem(int n){
        // Base case: If n is 0 or 1, there's only 1 way to tile the board
        if (n == 0 || n == 1) {
            return 1;
        }
        // Vertical choice: Place a vertical tile, reducing the problem size to n-1
        int fnm1 = tilingProblem(n - 1);

        // Horizontal choice: Place two horizontal tiles, reducing the problem size to n-2
        int fnm2 = tilingProblem(n - 2);

        // Total number of ways is the sum of the two choices
        int totalWay = fnm1 + fnm2;
        return totalWay;
    }

    public static void main(String[] args) {
        // Example: Finding the number of ways to tile a 2x4 board
        int n = 4;
        System.out.println(tilingProblem(n));  // Output: 5
    }
}

Detailed Explanation of the Code:

1. Base Case:

    if (n == 0 || n == 1) {
        return 1;
    }
   

   • If n == 0, it means the board is of size 2x0, which is an empty board. There's exactly 1 way to tile an empty board (by doing nothing).

   • If n == 1, the board size is 2x1, and the only way to tile it is by placing a single tile vertically. Therefore, there is 1 way to tile the board.

2. Recursive Case:

    int fnm1 = tilingProblem(n - 1);
    int fnm2 = tilingProblem(n - 2);
   

   • Vertical Choice: We place a 2x1 tile vertically, which covers one column of the board. This leaves a 2(n-1)* board to be tiled. Hence, we make a recursive call to tilingProblem(n-1).

   • Horizontal Choice: We place two 2x1 tiles horizontally, which covers two adjacent columns of the board. This leaves a 2(n-2)* board to be tiled. Hence, we make a recursive call to tilingProblem(n-2).

3. Total Number of Ways:

    int totalWay = fnm1 + fnm2;
    return totalWay;
   

   • The total number of ways to tile the 2xn board is the sum of the two choices: tiling the 2(n-1)* board (by placing one tile vertically) and tiling the 2(n-2)* board (by placing two tiles horizontally).

4. Main Method:

    public static void main(String[] args) {
        int n = 4;
        System.out.println(tilingProblem(n));  // Output: 5
    }
   

   • This is the entry point of the program where we test the tilingProblem function with n = 4 (i.e., a 2x4 board).

   • The expected output for n = 4 is 5, which means there are 5 distinct ways to tile a 2x4 board using 2x1 tiles.

---

Detailed Explanation of the Recursive Approach:

1. Recursive Breakdown: When you call tilingProblem(4), the recursion proceeds as follows:

   • tilingProblem(4) tries two possibilities:

     • Place a tile vertically, leaving a 2x3 board.

     • Place two tiles horizontally, leaving a 2x2 board.

   • For the 2x3 board (tilingProblem(3)):

     • Place a tile vertically, leaving a 2x2 board.

     • Place two tiles horizontally, leaving a 2x1 board.

   • For the 2x2 board (tilingProblem(2)):

     • Place a tile vertically, leaving a 2x1 board.

     • Place two tiles horizontally, leaving an empty board (2x0).

   • For the 2x1 board (tilingProblem(1)), there's only 1 way to place a tile (vertically).

   • For the 2x0 board (tilingProblem(0)), there's 1 way to tile the board (do nothing).

2. Recursive Tree for tilingProblem(4):

   • The recursive tree expands as:

       tilingProblem(4) = tilingProblem(3) + tilingProblem(2)
                       = (tilingProblem(2) + tilingProblem(1)) + (tilingProblem(1) + tilingProblem(0))
                       = ((tilingProblem(1) + tilingProblem(0)) + 1) + (1 + 1)
                       = ((1 + 1) + 1) + (1 + 1)
                       = 5
     

Visualization of Tile Placements for n = 4:

Here are the 5 different ways to tile a 2x4 board:

1. All tiles placed vertically:

    [|] [|] [|] [|]
    [|] [|] [|] [|]
   

2. Two horizontal tiles followed by two vertical tiles:

    [— —] [|] [|]
    [— —] [|] [|]
   

3. Two vertical tiles followed by two horizontal tiles:

    [|] [|] [— —]
    [|] [|] [— —]
   

4. One vertical tile, two horizontal tiles, and one vertical tile:

    [|] [— —] [|]
    [|] [— —] [|]
   

5. Two horizontal tiles followed by one vertical tile:

    [— —] [|] [— —]
    [— —] [|] [— —]
   

---

iii) Remove Duplicates in a String

Removing duplicate characters from a string can be done using a simple recursive approach. In this section, we’ll walk through a recursive solution that ensures the order of the original string is maintained while removing duplicates, showcasing the elegance of recursion in string manipulation.

Problem Explanation:

In the problem "Remove Duplicates in a String," we are tasked with removing duplicate characters from a string that contains only lowercase English letters (from 'a' to 'z'). This means that if any character appears more than once in the string, we want to keep only its first occurrence and remove all subsequent duplicates.

For example, given the string:

"rohitgaawandde"

The expected output should be:

"rohitgawnde"

This means we are left with only unique characters in the order they first appeared.

Approach:

To efficiently solve this problem, we can use a Boolean array that tracks which characters have already been added to the result string. The size of the Boolean array will be 26, corresponding to the 26 lowercase English letters ('a' to 'z').

1. Traversal: We'll traverse the input string from left to right, checking each character as we go.

2. Character Tracking:

   • For each character, we calculate its index in the Boolean array by subtracting 'a' from the character. This allows us to determine the position in the array that corresponds to the character.

   • If the character has not been encountered before, we mark it as seen in the Boolean array and add it to our result.

   • If the character has already been encountered (its corresponding position in the Boolean array is true), we skip adding it again.

Type Conversion in Character Indexing:

We use a simple technique to convert characters to their corresponding index in the Boolean array. Since all the characters in the string are lowercase English letters ('a' to 'z'), we can subtract the character 'a' from the current character to get an index between 0 and 25. This is based on the ASCII values of characters:

• 'a' - 'a' = 0

• 'b' - 'a' = 1

• 'z' - 'a' = 25

Base Case and Recursive Approach:

We can approach this problem using recursion. Recursion allows us to process the string character by character, from the first character to the last. The recursive function can take an index that starts at 0 and processes the string one character at a time.

• Base Case: When we reach the end of the string (i.e., the index is equal to the length of the string), the function stops and returns the resulting string.

• Work Done at Each Step:

  • For each character, we check whether it has already been added to the result using the Boolean array.

  • If it hasn’t been added, we mark it as added and include it in the result.

  • Then, we move to the next character.

Detailed Steps:

1. Boolean Array (map): We initialize a Boolean array of size 26, where each position corresponds to a letter of the alphabet:

   • map[0] corresponds to 'a',

   • map[1] corresponds to 'b',

   • map[25] corresponds to 'z'. Each entry in this array starts as false, indicating that none of the characters have been added yet.

2. Iterate through the String: We iterate over each character in the string:

   • Calculate the index of the character in the Boolean array using the formula charIndex = currentChar - 'a'.

   • Check if the character at charIndex in the Boolean array is false. If it is, this means the character hasn’t been added yet, so we add it to the result string and set map[charIndex] to true.

   • If the character is already present in the Boolean array (i.e., map[charIndex] is true), we skip adding it to the result string.

3. Final Output: Once all characters are processed, the result will be a string that contains each character only once, in the order in which they first appeared in the input string.

Example Walkthrough:

Consider the string:

"rohitgaawandde"

• Start with the first character 'r'. It's not yet added, so we add 'r' and mark map['r' - 'a'] = true.

• Move to 'o'. It's not yet added, so we add 'o' and mark map['o' - 'a'] = true.

• Move to 'h'. It's not yet added, so we add 'h' and mark map['h' - 'a'] = true.

• Continue this process for each character.

• When we encounter a duplicate, such as the second 'a', we see that map['a' - 'a'] = true, so we skip adding this duplicate.

• Similarly, we skip other duplicates like the second 'd'.

At the end of this process, the final string will be:

"rohitgawnde"

public class Q12 {
    /*In the problem "Remove Duplicates in a String,
    " we are tasked with removing duplicate characters from a string that contains only
     lowercase English letters (from 'a' to 'z'). */
    public static void removeDuplicates(String str,int idx,StringBuilder newStr,boolean map[]){
        if (idx==str.length()) {
            System.out.println(newStr);
            return;
        }
        char curChar=str.charAt(idx);
        if (map[curChar-'a']==true) {
            removeDuplicates(str, idx+1, newStr, map);
        }else{
            map[curChar-'a']=true;
            removeDuplicates(str, idx+1, newStr.append(curChar), map);
        }
    }
     public static void main(String[] args) {
        String str="rohitttgaawande";
        removeDuplicates(str, 0, new StringBuilder(""), new boolean[26]);
    }
}

Explanation of the Code:

1. Function Definition:

    public static void removeDuplicates(String str, int idx, StringBuilder newStr, boolean[] map)
   

   • str: The input string from which we want to remove duplicates.

   • idx: The current index of the string that is being processed.

   • newStr: A StringBuilder object that is used to build the resulting string without duplicates.

   • map[]: A boolean array of size 26 used to keep track of whether a particular character (from 'a' to 'z') has already been added to newStr.

2. Base Case (End of Recursion):

    if (idx == str.length()) {
        System.out.println(newStr);
        return;
    }
   

   • This is the base case for recursion. When the idx reaches the length of the string (str.length()), the function has processed all characters, and we print the result (newStr). The function then returns to end the recursion.

3. Current Character Processing:

    char curChar = str.charAt(idx);
   

   • We extract the current character from the string using str.charAt(idx).

4. Check if the Character has Already Been Added:

    if (map[curChar - 'a'] == true) {
        removeDuplicates(str, idx + 1, newStr, map);
    }
   

   • The map[] array helps track which characters have already been added to newStr. For example, if curChar = 'a', then curChar - 'a' evaluates to 0, so map[0] represents whether 'a' has already been added to the result string.

   • If the current character has already been added (i.e., map[curChar - 'a'] == true), we skip adding it again and recursively call the function for the next index (idx + 1).

5. If the Character is New (Not Added Yet):

    else {
        map[curChar - 'a'] = true;
        removeDuplicates(str, idx + 1, newStr.append(curChar), map);
    }
   

   • If the character is encountered for the first time (map[curChar - 'a'] == false), we mark it as added by setting map[curChar - 'a'] = true.

   • We then append the current character to newStr using newStr.append(curChar) and recursively call the function for the next index.

6. Main Function:

    public static void main(String[] args) {
        String str = "rohitttgaawande";
        removeDuplicates(str, 0, new StringBuilder(""), new boolean[26]);
    }
   

   • The main function initializes the input string (str = "rohitttgaawande").

   • The removeDuplicates() function is called with the following parameters:

     • str: The input string.

     • 0: The starting index.

     • new StringBuilder(""): An empty StringBuilder to store the result.

     • new boolean[26]: A boolean array of size 26 (all initialized to false) to track the occurrence of each character.

Recursive Flow:

1. Initially, the function starts at index 0 (idx = 0) and processes the first character 'r'. Since 'r' is not yet in newStr, it gets added, and map['r' - 'a'] is set to true.

2. The function then moves to the next index and processes 'o'. The same logic is applied: 'o' is not in newStr, so it is added, and map['o' - 'a'] is set to true.

3. This process continues until the function encounters repeated characters like 't' and 'a'. When a duplicate is found, the function skips adding it and moves on to the next character.

4. Once all characters are processed, the result is printed: "rohitgawnde".

This approach ensures that we process each character in the string only once, making it efficient with a time complexity of O(n), where n is the length of the string. The space complexity is O(1) because the Boolean array has a fixed size of 26, regardless of the size of the input. By using this strategy, we ensure that the solution is both simple and optimal.

---

iv) Friends Pairing Problem

The friends pairing problem challenges us to determine how friends can either pair up or stay single in a group. With recursion, we’ll explore how this problem evolves by recursively deciding whether each friend should pair up or remain single, leading to a solution that explores all possible states of pairing.

---

v) Binary Strings Problem

In this problem, we’ll generate all binary strings of length n that do not have consecutive ones. This problem can be effectively solved by breaking it down recursively, and we’ll explore how backtracking helps in achieving the solution efficiently.

---

vi) Binary Strings Problem Code

We will provide a recursive solution for the binary strings problem. By combining recursion with backtracking, we can generate valid binary strings without consecutive ones, demonstrating how recursion handles combinatorial challenges elegantly.

---

vii) Stack Analysis of Binary Strings and Solved Assignments

To wrap up, we’ll analyze the recursion depth and stack behavior of the binary strings problem. Understanding how the call stack behaves is crucial for optimizing recursive solutions. We’ll also walk through some solved assignments to reinforce the concepts learned in this chapter.

---

Conclusion

Recursion is not just a technique; it’s a mindset. By breaking problems into smaller, more manageable subproblems, recursion allows us to tackle complex challenges efficiently. In this chapter, we explored tiling, string manipulation, friend pairing, and combinatorial problems like binary strings, all of which highlight the power of recursion.

As you practice these problems, you’ll develop a deeper understanding of recursive thinking, which will prepare you for more advanced topics like Chapter 17: Divide and Conquer. Don’t forget to review Chapter 15: Recursion (Part 1) if you need a refresher on the basics, and continue exploring this exciting world of algorithms.

---

Check Out My Related DSA Series Posts:

1. Chapter 15: Recursion (Part 1)
   In this chapter, we introduced the fundamental concepts of recursion, including how recursive functions work and the importance of base cases. We explored basic problems such as factorial calculation, Fibonacci sequence which are essential to mastering recursion. Make sure to revisit this chapter if you want to strengthen your understanding of how recursion forms the foundation of many algorithmic solutions.

2. Chapter 17: Divide and Conquer
   After mastering recursion, we will delve into the Divide and Conquer algorithmic paradigm. This method involves breaking a problem into smaller, independent subproblems, solving them recursively, and combining their solutions to form the final answer. It is widely used in efficient algorithms such as Merge Sort, Quick Sort, and Binary Search. Stay tuned for this chapter, as it builds directly on the concepts from recursion.

3. Object Oriented Programming (OOP)
   In this post, we discuss the principles of Object-Oriented Programming (OOP), which is a fundamental paradigm in software development. We cover key concepts such as classes, objects, inheritance, polymorphism, encapsulation, and abstraction. Understanding OOP is crucial for structuring complex programs, especially in languages like Java, where recursion is often paired with OOP to solve problems in a modular and scalable way.

---

Explore My Other Series:

1. Full Stack Java Development
   In this series, I cover everything you need to know about full-stack development using Java. From building the backend with Java, Spring Boot, and databases to designing frontend applications using HTML, CSS, and JavaScript, this series is a comprehensive guide for anyone looking to become proficient in Java-based full-stack development. Each post is packed with hands-on projects and real-world examples.

2. Full Stack JavaScript Development
   This series is dedicated to mastering full-stack development using JavaScript, the most versatile programming language for both front-end and back-end development. We cover frameworks such as Node.js, Express, and MongoDB for backend development, along with React, Angular, and Vue.js for building interactive frontend applications. Whether you're a beginner or an experienced developer, this series will guide you through the entire process of building full-stack applications using JavaScript.

---

Connect with Me:

• GitHub
  Follow my GitHub profile to explore my projects, repositories, and code examples. Here, I upload all the code implementations related to the DSA series and full-stack development projects. You can also find open-source contributions and personal projects that I've worked on.

• LinkedIn
  Connect with me on LinkedIn to stay updated with my latest blog posts, coding challenges, and career-related updates. I frequently share insights on Full Stack Development, Data Structures & Algorithms, and career growth strategies. Feel free to reach out to me for networking or collaboration opportunities.

• LeetCode
  Check out my LeetCode profile where I regularly solve coding challenges, especially those related to algorithms and data structures. I participate in weekly contests and solve problems ranging from easy to hard, covering topics like recursion, dynamic programming, backtracking, and more.

Rohit Gawande
Full Stack Java Developer | Blogger | Coding Enthusiast