Question

1. 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.
2. Then use the Three-Question Approach to verify your recursive algorithm. No coding is required for this assignment
3. 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   algorithm   involve   a  
   smaller   case   of   the   original   problem,   leading   inescapably   to   the   base   case?
   3. The General-Case Question Assuming   the   recursive   call(s)   to   the   smaller   case(s)  
   works   correctly,   does   the   algorithm   work   correctly   for   the   general   case?  
4. Recursive method header given as: int multiplication (int a, int b)

Answer 1

GIven
int multiplication(int a, int b)
The algorithm has to be written without multiplication operator
so, Let's understand the basics of multilplication
Example:
3 * 5 means adding 3 for 5 times which is 3 + 3 + 3 + 3 + 3 = 15
So a * b will be adding a for b times a + a + a +...... b times
Recursive pseudocode for given algorithm
int multiplication(int a, int b)
{
   if(b == 1)
   {
       return a;
   }
   else
   {
       return a + multiplication(a, b - 1);
   }
}
1. The Base-Case Question Is there a nonrecursive way out of the algorithm, and does the algorithm work correctly for this base case?
Yes, The algorithm has a nonrecursive solution. Iterate from 1 to b at each iteration add a to the output then finally it will produce a * b.
In recursive solution The changes in variables like increment and decrement will be called as arguments. So In this algorithm the argument b will start from b, it will be called until b = 1, So the base case is b = 1 where the recursion will end.

2. The Smaller-Caller Question Does each recursive call to the algorithm involve a smaller case of the original problem, leading inescapably to the base case?
The smaller case for the current algorithm is adding a to the previous solution at each recursive call and decrementing the argument b, so that it will reach the base case.

3.3. The General-Case Question Assuming the recursive call(s) to the smaller case(s) works correctly, does the algorithm work correctly for the general case?
Yes, Since the algorithm is working for smaller cases, at each iterataion adding previously returned output and finally at the base case it is returning a, So the algorithm will produce product of any given arguments a and b.