CS 1704 Fall 2002 Homework 5 Answers Q A Reason ------------------------------------------------------------------------------------ 1 2 1 specifies a recursive call. 3 is just irrelevant to the question. 2 1 3 2 The base case terminates the recursion. 4 1 The recursive case continues the recursion. 5 2 If x < 0 then the condition in the if will be false initially, and each recursive call will just move x farther from 0, so the recursion will not terminate (logically). 6 3 Func(2) == 2 * Func(3) == 2 * 2 * Func(4) == 2 * 2 * 2 * Func(5) == 2 * 2 * 2 * 5 == 40 7 3 Consider the recursive case; the statement computes Low + Sum(Low + 1, Limit). So, to stop the recursion at the right point, the test here must compare Low to Limit. 8 5 Tracing the recursion: P(arr, 0, 5) no output output: arr[0] | ^ V | P(arr, 1, 5) no output output: arr[1] | ^ V | P(arr, 2, 5) no output output: arr[2] | ^ V | P(arr, 3, 5) no output output: arr[3] | ^ V | P(arr, 4, 5) no output output: arr[4] | ^ V | P(arr, 5, 5) no output output: arr[5] | ^ V | P(arr, 6, 5) recursion ends, and output: Done Note that the output is produced in bottom-to-top order, so the array elements are printed in reverse order, after "Done" is printed. 9 5 Sum(5) == 5 + Sum(5) == 5 + 5 + Sum(5) == . . . The problem is that the parameter isn't being changed, so there's no way for the recursion to end. 10 5 Quiz(2) -----------------------------------------------------------> 0 then calls Quiz(1) ---------------------------------------------> 0 then calls Quiz(0), which prints nothing returns to Quiz(1) ------------------------------------------> 1 then calls Quiz(0), which prints nothing returns to Quiz(1), which just returns to Quiz(2) -------> 1 then calls Quiz(1) again, which repeats the logic above -------> 0 -------> 1 11 3 Note that the comparison in the next line looks at Array[Size - 1], and that the specification says that Size is the number of elements actually stored in the array. So, the recursion should stop when Size is 0. 12 1 Clearly, whatever we're looking for, it won't be found in an array that holds no elements. 13 1 This is the test for a match. 14 2 Well, what would you do if a match was found? 15 4 This is the only choice that makes sense, given the logic to terminate the recursion that was identified in 3. 16 2 Well, when is there nothing to print? When the list is empty. 17 3 1 would retrieve the tail element to be printed, but it wouldn't make the recursion work; the function would just print the last element over and over. 2 would just walk off the end of the list. 18 4 1 is out because the recursive case must call RevPrint(). 2 is syntactically invalid, since the function is void. 3 is also syntactically invalid. 4 will do the job; LL has been shortened by having its tail element removed, so the list is heading towards becoming empty, which will stop the recursion. The internal logic will guarantee that the tail element is always the one that is removed and printed. 19 2 The list is passed by reference, so the calls to Delete() will gradually remove all the list contents. 20 4 Passing by value wouldn't alter the logic of the printing; the function would still work. BUT, each call, including the first would result in a copy being made of the list (or rather, what's left of it). Technically, the entire original list is only copied one time, and then shorter and shorter sublists are copied. 21 3 Tracing the recursion: findFactor(4, 48) == 1 + findFactor(4, 12) // That's one... == 1 + 1 + findFactor(4, 3) // ... and two ... == 1 + 1 + 0 22 2 Consider how Knapsack() works. It first tries a recursive call that treats the element at index Start as if it were part of a solution; if that works, we're done. If not, it makes another recursive call that excludes the element at index Start from the solution. 23 1 Initially, nothing has been considered. 24 3 If the current call is considering {3, 5, 13} as a possible solution, then the call was made from a previous call in which Start was 4. Since this also results in a negative Goal (-11), when the current call returns, another recursive call will be made that excludes 13, and considers whether there is a solution based on {3, 5}. You could also just trace the execution of the function; let's indicate the first recursive call by K1 and the second by K2: current possible solution Knap(ray, 10, 0, 4) {} K1(ray, 7, 1, 4) {3} K1(ray, 2, 2, 4) {3, 5} K1(ray, -5, 3, 4) {3, 5, 7} // reject K2(ray, 2, 3, 4) {3, 5} K1(ray, -9, 4, 4) {3, 5, 11} // reject K2(ray, 2, 4, 4) {3, 5} K1(ray, -11, 5, 4) {3, 5, 13} // reject K2(ray, 2, 5, 4) {3, 5} // reject K2(ray, 7, 2, 4) {3} K1(ray, 0, 3, 4) {3, 7) // success! 25 4 This doesn't alter the original logic. If the first call returns true, then the OR is true and the second call is not made (because of boolean short- circuiting). If the first call returns false, then the second call is made, and the return value will equal the value returned by the second call (since false || X equals X.