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: