Question

Description:

For this assignment, you are required to write 3 recursive methods described below. Create a class named HW06 and implement the following 3 methods . The implementation MUST use recursive calls.

- static int multiplyPositiveIntegers(int a, int b)

//multiplies two positive integers using recursion (no use of * allowed). Returns the result of multiplication. (30 points)

- static void recursiveBubbleSort(int[] arr)

//Sorts an array using bubble sort in a recursive manner. Hint: do one pass(which puts the biggest element at the end) then recur. (35 points)

- static String reverseString(String input)

//reverses a string in a recursive manner. returns the reversed string. You can use charAt() and substring() methods. (35 points)

Do not rename methods or change method signatures. You may add other methods or overload methods if you want. But, I should be able to call methods as described above.

Here is the skeleton:

public class HW06 {

    static void recursiveBubbleSort(int[] arr) {

     

    }

    static String reverseString(String input) {

       

    }

    static int multiplyPositiveIntegers(int a, int b)    {

       

    }

}

Answer 1

NOTE:If you are stuck somewhere feel free to ask in the comments...but do not give negative rating to the question as it affects my answering rights........I will try to help you out.....

import java.io.*;
import java.util.*;
public class HW06{
     static void helper(int[] arr,int n) {
         //the recursive function corrsponds to the outer for loop
         if (n == 1)
            return;//base case, if only one element means it is already sorted
      
       //the for loop below corresponds to one single pass of the bubble sort
       //After the first pass the largest element is placed in the end
        for (int i=0; i<n-1; i++)
            if (arr[i] > arr[i+1])
            {
                // swap the elements arr[i], arr[i+1]
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
      
        // Largest element is fixed, now recur for the next 
        helper(arr, n-1);
    }
    static void recursiveBubbleSort(int[] arr) {
        int n=arr.length;
       helper(arr,n);//since we need an extra variable to keep trak upto which element we have
       //sorted hence a helper function is needed....which is a recursive function
    }

    static String reverseString(String input) {
        if (input.isEmpty())
            return input;//base case, if string is empty it means already reversed
        //here we recursively call for the substring starting from the next index 
        //after adding the character at the current index to the output string
        //since this a recursive function the string is added in the end after finishing the recursive call
        return reverseString(input.substring(1)) + input.charAt(0);
    }


//the idea of multiplication is simple eg it says 2*3
//the it adding 2 three times.....meaning the smaller no is added larger number of times
    static int multiplyPositiveIntegers(int a, int b)    {
        // if a is less than  b then swap
        if (a < b) 
            return multiplyPositiveIntegers(b, a); 
      
        // iteratively calculate  a times sum of b
        else if (b != 0) 
            return (a + multiplyPositiveIntegers(a, b - 1)); 
      
        // if any of the two numbers is  
        // zero return zero 
        else
            return 0;
    }
    public static void main(String args[]) {
      int arr[] = {10, 2, 5, 12, 21, 11, 9};
        System.out.println("Initial array : ");
        System.out.println(Arrays.toString(arr));
        recursiveBubbleSort(arr);
        System.out.println("Sorted array : ");
        System.out.println(Arrays.toString(arr));
        String str="Welcome to java";
        System.out.println("Original String: "+str);
        System.out.println("Reversed String: "+reverseString(str));
        System.out.println("Product 23*45 equals: "+multiplyPositiveIntegers(23, 45));
    }
}

Output:-->