CS 1704 Fall 2003 Homework 6 Answers Q A Reason ------------------------------------------------------------------------------------ 1 6 1 specifies non-recursive behavior (fn does not call itself). 2 specifies recursive behavior (fn does call itself). 3 also specified non-recursive behavior. 2 2 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 4 PrintIt(2) will print "Duh" and call PrintIt(1). PrintIt(1) will print "Duh" and call PrintIt(0). PrintIt(0) will simply print "byuh" and return. On return from PrintIt(0), PrintIt(1) will simply return. On return from PrintIt(1), PrintIt(2) will simply return. 7 5 PrintIt(2) will print nothing at first and call PrintIt(1). PrintIt(1) will print nothing at first and call PrintIt(0). PrintIt(0) will simply print "Duh" and return. On return from PrintIt(0), PrintIt(1) will print "byuh" and return. On return from PrintIt(1), PrintIt(2) will print "byuh" and return. 8 3 Consider an example: Sum(1, 4) == 1 + Sum(2, 4) == 1 + 2 + Sum(3, 4) == 1 + 2 + 3 + Sum(4, 4) Now what does the last call need to return to produce the correct value? The value of the second parameter, and that needs to happen when the parameters are equal. You can also see this by considering adding up a list containing only one number... but that's almost too trivial. 9 5 Calling Sum(5) results in return( 5 + Sum(5) ). That clearly will never terminate --- it's a logically infinite recursion. 10 5 Calling Quiz(2) results in writing: 0 and calling Quiz(1) which writes: 0 and calls Quiz(0) which returns to the call Quiz(1) which writes: 1 and calls Quiz(0) which returns to the call Quiz(1) which returns to the call Quiz(2) which writes: 1 and calls Quiz(1) which writes: 0 and calls Quiz(0) which returns to the call Quiz(1) which writes: 1 and calls Quiz(0) which returns to the call Quiz(1) which returns to the call Quiz(2) which returns 11 0 The next clause handles finding a match, and the third handles continuing the search further into the array. So, this clause must be to determine if we've run out of places to look. 12 1 Given the analysis in the previous question, this is obvious. 13 2 Given the analysis in question 11, this is obvious. 14 4 At this point we have eliminated cell Size - 1 from contention; it's clear the search must be proceeding backward in the array, so the next call must look at the array as if it were one cell smaller. 15 2 Well, when is there nothing to print? When the list is empty. 16 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. 17 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. 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. 18 1 Initially, nothing has been considered. 19 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! 20 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.