Question

In: Computer Science

Implement a recursive algorithm to compute the product of two integers (in java). Your algorithm can...

Implement a recursive algorithm to compute the product of two integers (in java). Your algorithm can only perform addition and subtraction; no multiplication. Analyze the running time and space complexity of your solution.

Expert Solution

please find below java program for multiplication using recursion

public class Main
{
        public static void main(String[] args) {
                System.out.println("Product: "+multiplication(2,3,0));
        }
        public static int multiplication(int n,int m,int result){
            
            if(n==0)
            {
                return result;
            }
            else
            {
                return multiplication(n-1,m,result+m);
            }
            
        }
}

Time Analysis

multiplication(0,m,result) is only comparison

multiplication(n,m,result)=is 1 comparison,1 subtraction,1 addition

so T(n)=T(n-1)+3

T(0)=1

T(n) = T(n-1) + 3

= T(n-2) + 6

= T(n-3) + 9

= T(n-4) + 12

= ...

= T(n-k) + 3k

as we know T(0) = 1

we need to find the value of k for which n - k = 0, k = n

T(n) = T(0) + 3n , k = n

= 1 + 3n

that gives us a time complexity of O(n)

Space complexity

For every call to the recursive function, the state is saved onto the call stack, till the value is computed and returned to the called function.

The space complexity of recursive multiplication implementation is O(n)

venereology answered 1 hour ago

Implement and complement the recursive code to compute the product of two positive integers, x and...

Implement and complement the recursive code to compute the product of two positive integers, x and y, using only addition and/or subtraction. The function will take as its arguments two integers to multiply together ( x x y ) and will return the product. Hint: consider the following: 6 x 1 = 6 6 x 2 = 6 + (6 x 1) 6 x 3 = 6 + (6 x 2) = 6 + [6 + (6 x 1)] =...

2. Give a recursive algorithm to compute the product of two positive integers, m and n,...

2. Give a recursive algorithm to compute the product of two positive integers, m and n, using only addition and subtraction. Java Language...

1) You must implement a recursive Quicksort algorithm that will read integers from the attached MyList.txt...

1) You must implement a recursive Quicksort algorithm that will read integers from the attached MyList.txt file. Your algorithm must sort the list(integers)in ascending order. 2)You must implement a recursive Mergesort algorithm that will read integers from the attached MyList.txt file. Your algorithm must sort the list(integers)in ascending order. My List.txt Values 7 3 4 1 4 4 9 9 4 8 4 5 3 9 2 3 7 0 6 4 4 5 0 1 9 2 1 7...

in code c++ describe a recursive algorithm for multiplying two nonnegative integers x and y based...

in code c++ describe a recursive algorithm for multiplying two nonnegative integers x and y based on the fact that xy = 2(x · (y/2)) when y is even and xy = 2(x · ⌊y/2⌋) + x when y is odd, together with the initial condition xy = 0 when y = 0.

Now we need to develop a recursive algorithm for multiplication operation with two positive integers without...

Now we need to develop a recursive algorithm for multiplication operation with two positive integers without using the multiplication operator. Your answer should be in pseudocode or Java code format. Then use the Three-Question Approach to verify your recursive algorithm. No coding is required for this assignment 1. The Base-Case Question Is there a nonrecursive way out of the algorithm, and does the algorithm work correctly for this base case? 2. The Smaller-Caller Question Does each recursive call to the ...

IN JAVA PLEASE Implement a recursive approach to showing all the teams that can be created...

IN JAVA PLEASE Implement a recursive approach to showing all the teams that can be created from a group (n things taken k at a time). Write the recursive showTeams()method and a main() method to prompt the user for the group size and the team size to provide arguments for showTeam(), which then displays all the possible combinations.

Please use java language Thanks! Implement a recursive method called "pow" that takes 2 integers, x...

Please use java language Thanks! Implement a recursive method called "pow" that takes 2 integers, x and y, as parameters and returns the value xy (x raised to the power y). The exponent must be non-negative. If a negative argument is given for the exponent, then an exception should be thrown. Implement a recursive method called "fib" that takes a positive integer, n, as a parameter and returns the nth Fibonacci value. Assume that the first 2 values in the...

Programming language: JAVA First, implement a recursive, Divide&Conquer-based algorithm to identify both the Minimum and Maximum...

Programming language: JAVA First, implement a recursive, Divide&Conquer-based algorithm to identify both the Minimum and Maximum element in an unsorted list. Second, convert your recursive algorithm to a non-recursive (or iterative) implementation. For your input, populate an "unsorted list" with random elements between 1 and 1,000,000.

Use Recursive Algorithm to compute 5^23 Mod 8

1. Implement the recursive LU factorization algorithm in Python. Use plenty of comments to explain your...

1. Implement the recursive LU factorization algorithm in Python. Use plenty of comments to explain your code. While you are coding, it is helpful to break up your code into sub-functions and test the sub-functions as you go along.