code :

/***************************************************************** * Program: multiply.C * * Purpose: implements/illustrates a recursive version of the russian * peasant's algorithm for multiplication * * Authors: * *****************************************************************/ #include #include /***************************************************************** * multiply - multiplies two non-negative numbers * * calling sequence: * result = multiply(num1, num2) * * parameters - * num1 and num2 - the numbers to be multiplied * * result - * The product of the two numbers is returned. * * restrictions - * Overflow is not properly handled * * example - * Multiply(23, 20) yields the result 460. * * method - * This is essentially a recursive version of the "russian peasant's algorithm". * If the num1 is zero, zero is returned. Otherwise, if the number is even, the * the product of num1/2 and num2*2 is returned. Otherwise (the number is odd) * the produce of (num1/2) and (num2*2) is computed, but num2 is added to the result * to compensate for the fact that the division drops the remainder. * *****************************************************************/ int multiply(int num1, int num2) { /* BASE CASE: num1 == 0 */ if(num1 == 0) { return 0; /*multiplying by 0 results in 0*/ } /* RECURSIVE CASE: for negative valued input */ if (num1 0) { return -multiply(-num1, num2); /* negate result */ } /* RECURSIVE CASE: num1 is positive and num2 is negative */ if (num1 > 0 && num2 Part 3: Multiplication (multiply.c) - Fix the recursive case (switch driver) 1. Examine the multiply function in multiply.c, which is intended to perform multiplication using the Russian Peasant's Algorithm. This algorithm multiplies two integers as follows: Base case: (already done) if the first integer is zero, then the result is zero Base case: (already done) If one or both are negative numbers, then recursively call multiply on the negated values. Recursive case: (which you need to do) If the first integer is even, the result is the result of recursively multiplying half of the first number by twice the second. For example, you can multiply 24 times 7 by multiplying 12 (half of 24) by 14 (twice 7); this results in the value 168. If the first integer is odd, the result is the result of recursively multiplying half of the first number (rounded down) by twice the second, and then adding the second number to compensate for the rounding down. For example, you can multiply 25 times 7 by multiplying 12 (half of 25) by 14 (twice 7), and then adding 7; this results in the value 175 2. To see this algorithm in action, consider multiplying 13 times 20: 13*20 is 6*40 + 20 o 6*40 is 3*80 3*80 is 1*160 + 80 . 1*160 is 0*320 160 0*320 - 0 (base case) . so 1*160 is 0160- 160 so 3*80 is 160+ 80- 240 . o So 6*40240 . so 13*30 is 240 +20 260 Explain why this function will always terminate