Computer Science > QUESTIONS & ANSWERS > HW3 Assignment 3 – Recursion Solutions - Johns Hopkins University CS 605.202 (All)

HW3 Assignment 3 – Recursion Solutions - Johns Hopkins University CS 605.202

Document Content and Description Below

Assignment 3 – Recursion Write pseudo-code not Java for problems requiring code. You are responsible for the appropriate level of detail. Q1 and Q2 are intended to help you get comfortable with r ... ecursion by thinking about something familiar in a recursive manner. Q3 – Q6 are practice in working with nontrivial recursive functions. Q7 and Q8 deal with the idea of conversion between iteration and recursion. 1. Write a recursive algorithm to compute a+b, where a and b are nonnegative integers. public int add(int a, int b) { if (b == 0) return a; else return 1 + add(a, b - 1); } 2. Let A be an array of integers. Write a recursive algorithm to compute the average of the elements of the array. Solutions calculating the sum recursively, instead of the average, are worth fewer points. public double average(int y[], int i) { double result; result = (double)y[i] / (double)y.length; if (i == 0) return result; else return result + average(y, i-1); } 3. If an array contains n elements, what is the maximum number of recursive calls made by the binary search algorithm? The binary search algorithm recursively searches half of the array. n = 1: 0 recursive calls n = 2: 1 recursive call n = 4: 2 recursive calls n = 8: 3 recursive calls n = 16: 4 recursive calls ... This pattern shows that the maximum number of recursive calls is generally ceiling(lg (n)). However, for the beginning cases of n = 1 and n = 2, an additional step could be required if the value is not in the list. Therefore, ceiling(lg(n)) + 1 is also acceptable. 4. The expression m % n yields the remainder of m upon (integer) division by n. Define the greatest common divisor (GCD) of two integers x and y by: [Show More]

Last updated: 2 years ago

Preview 1 out of 4 pages

Buy Now

Instant download

We Accept: