EECE 230 Homework 8, Fall 2012

Common Mistakes in Recursion In this document we discuss two common mistakes when writing recursive functions. We will provide two examples of incorrect binary search. These examples may look useless and contrived, since you already have a correct version of binary search and other well-known algorithms (Merge Sort, QuickSort) in the slides. But you may be required to write some variant of these algorithms, and knowing about the common mistakes may help you to avoid them when you write a variant of these well-known algorithms. Mistake#1: Unreachable base case resulting in infinite recursion: Consider the following WRONG code for recursive binary search: int recursiveBinarySearch(int * A,int start,int end, int x) { if(start <=end) { int mid = (start+end)/2; if (A[mid] < x) return recursiveBinarySearch(A,mid,end,x); else if (A[mid] > x) return recursiveBinarySearch(A,start,mid-1,x); else if (A[mid] ==x) return mid; // this is a base case } else return -1;// another base case of the recursion } This code is almost identical to the one given in the slides except that we replaced return recursiveBinarySearch(A,mid+1,end,x); by: return recursiveBinarySearch(A,mid,end,x); At first sight, the code still appears correct. It is true that if A[mid]<x , then the value x must have an index between mid and end, if it appears at all in the array. Unfortunately this code isn't correct. Try it on the input A={0,1,2,3,4,5} and x= 5. It will fail. Why ? Because the base case is unreachable: First the function is called with arguments start= 0 and end=5, then it will call itself recursively with start = 2 and end = 5, then it will call itself recursively with start = 3 and end = 5, then it will call itself with start = 4 and end =5 and then... it will call itself again with start = 4 and end =5, and the program will be stuck in an infinite recursion. Sometimes this failure will manifest itself very weirdly, for example by keeping the screen blank for a few seconds and then printing “Press any key to continue” and stopping the program. Unlike an infinite loop, infinite recursion cannot really go on very long, because each of the “workspaces” used by the recursive calls consumes memory, and very quickly the program will run out of memory. Such an error is called a stack overflow. How do you do to avoid such errors ? The general strategy is very simple: You should make sure that the recursive calls ALWAYS handle subproblems strictly smaller than the original problem, and you should make sure that the base case all problem sizes smaller than a certain threshold. In the above case the size of the right subarray was not always strictly smaller than the entire array, and that was the cause of the error. Mistake #2: Making out-of-bounds recursive calls This kind of error is common when you write recursive algorithms on arrays. Very often, recursive algorithms on arrays are divide-and-conquer algorithms which work by dividing the original arrays in ever-smaller subarrays. For example, Binary Search, Quicksort, and Merge Sort work in this fashion. Subarrays are usually specified using their first index and their last index, and these two indexes are passed as arguments. You have to make sure that you don't pass out-of- bound indexes as arguments in your recursive calls, and if you can't or don't want to avoid it, you should make sure your code can handle such invalid arguments. Example: Suppose we slightly modify the Binary Search function by adding the statement: if(A[start]==x) return start; at the very beginning of the function, and that we write the following program: #include <iostream> using namespace std; int B[] = {0,1,2,3,4,5,6,7,8,9,10}; int C[] = {11,0}; int recursiveBinarySearch(int * A,int start,int end, int x) { if(A[start]==x) return start; //Line L1 if(start <=end) { int mid = (start+end)/2; if (A[mid] < x) return recursiveBinarySearch(A,mid+1,end,x); else if (A[mid] > x) return recursiveBinarySearch(A,start,mid-1,x); else return mid; // this is a base case } else return -1;// another base case of the recursion } int main(){ int a = recursiveBinarySearch(B,0,10,11); cout << a << endl << flush; return 0; } At first sight, the Binary Search function still appears to be correct, although the first line of the function is not necessary. But if you run the above program, the output will be wrong (It will return 11, when the last valid index in array B is only 10, and the function should have returned -1). Why ? Because at some point, the start index will be outside the array. This fact is often overlooked but even if the line we added (L1) is removed, it is still true that the start variable will be greater than 10 at some time. To verify this, add a cout statement at the beginning of the recursive function to check the value of the arguments. And if B={10,11,12} and x = -1, the recursiveBinarySearch function will at some point be recursively called with a negative end index. However if Line L1 is omitted, these out- of-bounds values will not cause any error because they will not be used to index any element in the array, as the condition if(start<=end) will filter out these cases: The first time either start or end will become an invalid index, the condition (start<=end) will become false (This may not be obvious at first but will become clear with a bit of thinking.) This is so because the function was written in a way that handles this problem. OK, now assume that you have written your own recursive function, and that it does not return the correct answer, and you suspect that the code contains an out-of-bounds error. How can you find this error ? One good way would be to add a cout statement at the beginning of the recursive function, to display its arguments, especially the ones corresponding to subarray bounds, and run the program to see if some of these bounds look wrong. for example : int recursiveBinarySearch(int * A,int start,int end, int x) { cout << “ start = “ << start << “ end = “ << end << endl << flush; if(A[start]==x) return start; //Line L1 if(start <=end) { int mid = (start+end)/2; if (A[mid] < x) return recursiveBinarySearch(A,mid+1,end,x); else if (A[mid] > x) return recursiveBinarySearch(A,start,mid-1,x); else return mid; // this is a base case } else return -1;// another base case of the recursion } Please note that the cout statement ends with << flush . This is necessary when you use cout for debugging purposes. This tells the computer to display the result as soon as the cout statement is executed. If flush is omitted, the computer will sometimes store the output in a buffer, and will wait until the function stops executing to display the contents of the buffer; but if the functions fails in a runtime error, the contents of the buffer will not be displayed at all. #include <iostream> using namespace std; int recursiveCallsA=0; int recursiveCallsB=0; int recursiveCallsC=0; double iterativeA(int n); double recursiveA(int n); int iterativeB(int n); int iterativeIIB(int n); int recursiveB(int n); double iterativeIC(int n,int x,int y,int z); double iterativeIIC(int n,int x,int y,int z); double recursiveC(int n,int x,int y,int z); void main(){ int n; cout << "Please enter a strictly positive integer n " << endl; cin >> n; cout << "iterativeA(" << n << ") = " << iterativeA(n) << endl; cout << "recursiveA(" << n << ") = " << recursiveA(n) << endl; cout << "The number of calls for function recursiveA is : " << recursiveCallsA << endl; cout << "iterativeB(" << n << ") = " << iterativeB(n) << endl; cout << "iterativeIIB(" << n << ") = " << iterativeIIB(n) << endl; cout << "recursiveB(" << n << ") = " << recursiveB(n) << endl; cout << "The number of calls for function recursive B is : " << recursiveCallsB << endl; cout << "Please enter three integers x,y,z separated by spaces " << endl; int x,y,z; cin >> x >> y >> z; cout << "iterativeIC(" << n << ", " << x << ", " << y << ", " << z << ") = " << iterativeIC(n,x,y,z) << endl; cout << "iterativeIIC(" << n << ", " << x << ", " << y << ", " << z << ") = " << iterativeIIC(n,x,y,z) << endl; cout << "recursiveC(" << n << ", " << x << ", " << y << ", " << z << ") = " << recursiveC(n,x,y,z) << endl; cout << "The number of calls for function recursive C is : " << recursiveCallsC << endl; } double iterativeA(int n){ double a=0; double previous = 0; for(double i=1;i<=n;i++){ a = 2 * previous + 1; previous = a; } return a; } double recursiveA(int n){ recursiveCallsA++; if(n==1) return 1; else return 2*recursiveA(n-1)+1; } int iterativeB(int n){ //the last entry has index n,to be able to start the array at index 1 int *b = new int[n+1]; b[1] = 1; for(int i=2;i<=n;i++){ b[i] = b[i/2] + b[(i+1)/2] + i; } int returnValue = b[n]; delete [] b; return returnValue; } int recursiveB(int n){ recursiveCallsB++; if(n==1) return 1; else { //This is MUCH faster than simply returning (recursiveB(n/2) + recursiveB((n+1)/2) + n; //try both methods with n=50000000 and see the difference! if(n%2==0) return 2*recursiveB(n/2) + n; else return (recursiveB(n/2) + recursiveB((n+1)/2) + n); } } double iterativeIC(int n, int x, int y, int z){ if(n==1) return x; if(n==2) return y; if(n==3) return z; double current = z; double previous = y; double beforePrevious = x; int count = 3; while(count<n){ double temp = current + previous + beforePrevious; beforePrevious = previous; previous = current; current = temp; count++; } return current; } double iterativeIIC(int n, int x, int y, int z){ if(n==1) return x; if(n==2) return y; if(n==3) return z; double *c = new double [n+1]; c[1] = x; c[2] = y; c[3] = z; for(int i=4;i<=n;i++) c[i] = c[i-1]+c[i-2]+c[i-3]; double returnValue = c[n]; delete [] c; return returnValue; } double recursiveC(int n, int x, int y, int z){ recursiveCallsC++; if(n==1) return x; else if(n==2) return y; else if(n==3) return z; else return (recursiveC(n-1,x,y,z)+recursiveC(n-2,x,y,z)+recursiveC(n- 3,x,y,z)); } //recursiveC is highly inefficient when compared to iterativeIC and iterativeIIC //because in the iterative version, the number of steps the program makes is //proportional to n, while in the recursive version it is proportional to the //number of recursive calls, which is much larger than n: suppose you want //to compute C(50). then ,say, C(45) will be called multiple times: //1: C(50)->C(49)->C(48)->C(47)->C(46)->C(45) //2: C(50)->C(49)->C(48)->C(47)->C(45) //3: C(50)->C(49)->C(48)->C(45) //4: C(50)->C(49)->C(47)->C(46)->C(45) //5: ....And so on and so forth. This effect increases as one goes deeper in the recursion //the base cases are called millions and millions of times. //For similar reasons, iterativeIIB is much faster than recursiveB. //As to iterativeB and recursiveB, recusiveB is much faster and requires //much less memory, but it would have been slower if we had used a //naive implementation that would not distinguish between odd and even n. //the reason why recursiveB is much faster than iterativeB is that //recursiveB computes only a fraction of the array entries, and //it is much less memory consuming (since recursion depth is bounded //by the logarithm of n) // OPTIONAL // iterative B without array //iterative solution without arrays. //The basic idea of iterativeIIB is that the only values of the sequence b //that will ever need to be calculated are the values b(floor(n/2^i)) and b(floor(n/2^i)+1) //where i goes from 0 to lg n . This is a bit tricky to prove, and not required for exam. //Actually it turns out that this recurrence has a closed form solution: //a(n) = n*(floor(log_2 n) + 3) - 2^((floor (log_2 n)) + 1) //see http://www.research.att.com/~njas/sequences/A033156 int iterativeIIB(int n){ int low = 1, high = 2; int bLow = 1, bHigh = 4,newLow,newHigh,newBLow,newBHigh; int n1; while(low<n){ n1 = n; while(n1/2>low){ n1 = n1/2; } newLow = n1; newHigh = n1+1; if(n1%2==0){ newBLow = 2*bLow + newLow; newBHigh = bLow+bHigh + newHigh; } else{ newBLow = bLow + bHigh + newLow; newBHigh = 2 * bHigh +newHigh; } bLow = newBLow; bHigh = newBHigh; low = newLow; high = newHigh; } return bLow; } #include<iostream> using namespace std; double power(int x, int y); double smartPower(int x, int y); void main(){ cout << power(2,10) << endl; cout << smartPower(2,10) << endl; cout << power(10,-5) << endl ; cout << smartPower(10,-5) << endl; } //for simplicity we do not check for the case where x = 0 and y = 0; double power(int x, int y){ if(y<0) return 1/power(x,-y); else if (y==0) return 1; else return x*power(x,y-1); } double smartPower(int x, int y){ if(y<0) return 1/power(x,-y); else if(y==0) return 1; else { double val = power(x,y/2) ; if(y%2==1) return val * val * x; else return val * val; } } //the recurrence is: //u(y) = u(y/2)^2 if y is even and > 0 //u(y) = u(floor(y/2))^2 * x if y is odd and > 0 //u(y) = x if y=0 //u(y) = 1/u(-y) if y<0 #include <iostream> using namespace std; void swap(int &, int &) ; int arraySmallest(int* , int , int ); void recursiveSelectionSort( int* , int , int ); void main() { int A[100]; cout << "Enter ur integers ( -999 to end ):" << endl; int x; cin >> x; int n=0; while( x!=-999 ) { A[n]=x; n++; cin >> x; } recursiveSelectionSort(A,0,n-1); for(int i=0 ; i<n ; i++ ) cout << A[i] << " "; cout <<endl; } void recursiveSelectionSort( int* A , int start , int end ) { if( start<end ) { int minIndex= arraySmallest(A,start,end); swap( A[minIndex],A[start] ); recursiveSelectionSort(A,start+1,end ); } } void swap(int &x, int &y) { int temp = x; x = y; y = temp; } int arraySmallest(int* A , int start , int end ) { int minIndex =start; for(int i=start+1; i<=end ; i++) if (A[i]<=A[minIndex]) minIndex = i; return minIndex ; } #include <iostream> using namespace std; int sequentialModeFinder(int* A, int n); int recursiveModeFinder(int* A, int start, int end); int fastIterativeModeFinder(int* A, int start, int end); void main(){ int A[] = {1,2,4,7,11,10,8,4,-9}; int n = sizeof(A)/sizeof(int); //array size; cout << "The answer of the sequential mode finder is : " << sequentialModeFinder(A,n) << endl; cout << "The answer of the recursive mode finder is : " << recursiveModeFinder(A,0,n-1) << endl; cout << "The answer of the fast iterative mode finder is : " << recursiveModeFinder(A,0,n-1) << endl; } int sequentialModeFinder(int *A,int n){ for(int i=0;i<n-1;i++){ if(A[i]>A[i+1]) return i; } return n-1; } int recursiveModeFinder(int *A, int start, int end){ if((end==start) || (end==start+1)){ if(A[start]<A[end]) return end; else return start; } int mid = (start + end)/2; if(A[mid]>A[mid+1]) //mid is either the mode or is already past the mode return recursiveModeFinder(A,start,mid); else //We did not reach the mode yet return recursiveModeFinder(A,mid,end); } int fastIterativeModeFinder(int* A, int start, int end){ while((start!=end)&&(start+1!=end)){ int mid = (start+end)/2; if(A[mid]>A[mid+1]) end = mid; else start = mid; } if(A[start]>A[end]) return start; else return end; } #include <iostream> #include <ctime> using namespace std; int partition(int *,int,int); void printArray(const int *A,int n); void randQuickSort(int A[], int low, int high); void quickSort(int A[], int low, int high); void testQuickSort(); void testRandQuickSort(); void main() { //srand is called only *once* at the beginning of the program. //Do not call srand repeatedly, for instance within a loop, because if the time interval //between 2 consecutive calls is too small, the random number generator will be seeded with the //same value. srand((unsigned)time(NULL)); testQuickSort(); testRandQuickSort(); } void testQuickSort(){ int A[]= {14,2, 11,13,6,5,15,9,8, 12, 3, 10, 4, 1, 7}; cout<<"orginal array:"<<endl; printArray(A,15); quickSort(A,0,14); cout<<"after calling quicksort:"<<endl; printArray(A,15); } void testRandQuickSort(){ int A[]= {14,2, 11,13,6,5,15,9,8, 12, 3, 10, 4, 1, 7}; cout<<"orginal array:"<<endl; printArray(A,15); randQuickSort(A,0,14); cout<<"after calling randquicksort:"<<endl; printArray(A,15); } void quickSort(int A[], int low, int high){ if(high>low){ int q = partition(A,low,high); quickSort(A,low,q-1); quickSort(A,q+1,high); } } void randQuickSort(int A[], int low, int high){ if(high>low){ int randomIndex = low + rand()%(high-low+1); swap(A[randomIndex],A[high]); int q = partition(A,low,high); randQuickSort(A,low,q-1); randQuickSort(A,q+1,high); } } //to see why this implementation of partitioning works , observe that the following //properties hold: //1-At every step of the outer while loop i and j are between low and high included, because the initial // value of i is a lower bound on j and the initial value of j is an upper bound on i.This means that // no out of bounds error is possible. //2-At every step of the outer while loop, all elements of index strictly smaller than i, if any exists, are smaller //or equal to A[high]. //3-At every step of the outer while loop, all elements of index strictly larger than j are larger or equal to A[high], //and at least one such element exists (namely A[high]); //4-When the outer while loop exits, we have i==j. Exactly one of three cases must hold: //1-A[i]>A[high] //2-A[i]= A[high] //3-A[i]<A[high] //In the first 2 cases, we can just swap A[i] with A[high], and we're done. //In the last case, since we have i==j, and since at any time A[j+1]>=A[high], //we can swap A[j+1] with A[high] (A[j+1] is not out of bounds, since the maximum //value of j, which happens to be its initial value,is high-1) int partition(int A[],int low,int high) { int i=low; if(high-low<1) return 0; int j=high-1; while (i<j) { while (A[i]<=A[high] && i<j) i++; while (A[j]>=A[high] && i<j) j--; swap(A[i],A[j]); } if(A[i]>=A[high]) { swap(A[i],A[high]); return i; } else { swap(A[i+1],A[high]); return i+1; } } void printArray(const int *A,int n) { for (int i=0;i<n;i++) cout<<A[i]<<" "; cout<<endl; } #include <iostream> using namespace std; const int fixedStringLength = 4; void printArray(const int *A,int n); void printAll(char s[],int currentIndex,int stringLength); void printAllC(char s[], int currentIndex,int stringLength,int maxWeight); void printAllPermutations(int currentPerm[],int unavailable[],int currentIndex, int permLength); void storeAll(char s[],int currentIndex,char M[][fixedStringLength+1], int& counter); void testPrintAll(); void testPrintAllC(); void testPrintAllPermutations(); void testStoreAll(); //To design a recursive algorithm, we assume we have a function that solves a problem //of the same kind, but of smaller size, and then we try to use this function to help us //solve the larger problem. As you might have noticed from previous programming assignments, //this process bears a strong similarity to mathematical induction. We will try to illustrate //this point of view using this exercise. void main() { testPrintAll(); testStoreAll(); testPrintAllC(); testPrintAllPermutations(); } void testPrintAll(){ char s[100]; printAll(s,0,6); } void testStoreAll(){ char s[fixedStringLength+1]; char M[10000][fixedStringLength+1]; int counter = 0; storeAll(s,0,M,counter); for(int i=0;i<counter;i++) cout << M[i] << endl; } void testPrintAllC(){ char s[2000]; // the prototype of printAllC is : //void printAllC(char s[], int currentIndex,int stringLength,int curWeight,int maxWeight) printAllC(s,0,8,2); } void testPrintAllPermutations(){ int av[4]={0}; int A[4]; printAllPermutations(A,av,0,4); } //As mentioned previously, when we are trying to design a recursive algorithm, we assume that //we already have a function that works on problems of smaller size. However, on this problem, //this approach does not seem to work at first sight : even if one has a function ,say, that prints //all abc strings of length 3, that doesn't make it easier to make a function that prints //all abc strings of length 4. So we have to define our subproblems in a way that makes it easy //for us to solve the original problem. That's why, instead of defining a subproblem as printing //abc strings of smaller sizes, we define a subproblem to consist in printing all abc-strings of //full size stringLength *such that their first n characters are fixed*. (currentIndex represents the //number of fixed characters,which can also be considered as the index of the first non-fixed array entry, //because arrays are 0-based). //So, let's assume we have a function that lets us print all abc strings of length stringLength having their //first n+1 characters fixed. Now,it is easy to use this function to print all abc strings of length stringLength //having their first n characters fixed : just put 'a' at the nth position and call the function that //leaves the first n+1 characters fixed, then put 'b' at the nth position and call the function again, //and then put 'c' at the nth position and call the function again. So we now have our recursive formulation. //The base case of the function is extremely easy to understand: When all the array is fixed, we only have //to print it. //This is what we're doing in the printAll function. void printAll(char s[],int currentIndex,int stringLength){ if(currentIndex==stringLength){ s[currentIndex]='\0'; cout << s << endl; return; } s[currentIndex]='a'; printAll(s,currentIndex+1,stringLength); s[currentIndex]='b'; printAll(s,currentIndex+1,stringLength); s[currentIndex]='c'; printAll(s,currentIndex+1,stringLength); } //We removed the argument stringLength, since the length is assumed to be 4 //storeAll is a very simple modification of the previous problem: instead of printing //to the screen, it prints to an array. void storeAll(char s[],int currentIndex,char M[][fixedStringLength+1], int& counter){ if(currentIndex==fixedStringLength){ for(int i=0;i<fixedStringLength;i++) M[counter][i]=s[i]; M[counter][fixedStringLength]='\0'; counter++; return; } s[currentIndex]='a'; storeAll(s,currentIndex+1,M,counter); s[currentIndex]='b'; storeAll(s,currentIndex+1,M,counter); s[currentIndex]='c'; storeAll(s,currentIndex+1,M,counter); } //printAllC is a bit more difficult. //The function printAllC prints all binary strings of length stringLength, having their first n //characters fixed, and containing not more than maxWeight '1' characters between index n and //index stringLength included. With this general idea in mind, it is relatively easy to give a sketch of //a proof of correctness for printAllC, by induction on stringLength-n: //for a value of stringLength-n=0, all the characters are fixed , and this function is obviously //correct. Suppose now this function is correct for stringLength-n = z (n>0). Let's prove it correct //stringLength-n=z+1; the function first sets the nth element to '0' and calls itself recursively //on a larger n,and therefore a smaller value of stringLength -n. But we assumed it was correct for smaller values //of stringLength-n, and therefore it will print correctly all output strings having a '0' in the nth //place. //after having taken care of the case where the nth character is a '0' ,we now consider the case //where the nth character is a '1'. First we check if ones are at all allowed, then we set the nth //character to '1' , we freeze the n+1 first characters, and we call the function recursively, without //forgetting to decrease the number of allowable '1' characters by one. Since the function will //work correctly on this subproblem (by induction), the function will work correctly when the //nth character is set to '1'. Therefore printAllC will always work correctly. void printAllC(char s[], int n,int stringLength,int maxWeight){ if(n==stringLength){ s[n]='\0'; cout << s << endl; return; } s[n]='0'; printAllC(s,n+1,stringLength,maxWeight); if(maxWeight>0) { s[n]='1'; printAllC(s,n+1,stringLength,maxWeight-1); } } void printArray(const int *A,int n) { for (int i=0;i<n;i++) cout<<A[i]<<" "; cout<<endl; } //printAllPermutations will print all permutations of length permLength which first currentIndex //positions are fixed. Since a given number can appear only once in a given permutation, //the numbers have already been used are flagged in the array unavailable. Of course, this //information is redundant, it is only there for efficiency purposes. void printAllPermutations(int currentPerm[],int unavailable[],int currentIndex, int permLength){ if(currentIndex==permLength){ printArray(currentPerm,permLength); return; } for(int i=1;i<=permLength;i++){ if(unavailable[i-1]==0){ currentPerm[currentIndex]=i; unavailable[i-1]=1; printAllPermutations(currentPerm,unavailable,currentIndex+1, permLength); unavailable[i-1]=0; } } }