AP Computer Science A Unit 10 Recursion

Unit 10: Recursion Recursion: A recursion method calls itself. A base case in a recursion method is an execution path that does not call itself, all recursive methods must have a base case or else the method will eventually cause an error due to being called too many times. Every recursive call has its own set of parameters and local variables. When a task is done recursively, the parameters are used to track the progress of the task. Ex: public class RecursionOne { public void run(int x) { out.println(x); run(x+1); } public static void main(String args[] ) { RecursionOne test = new RecursionOne(); test.run(1); } } The Output: 1 2 3 4 5 ..... stack overflow This occurs because there is no code or case that makes the recursion stop. So what does a recursive method need to run correctly? A recursive method must have a stop condition/ base case. Recursive calls will continue until the stop condition/ base case is met. Example with a base case: public class RecursionTwo { public void run(int x ) { out.println(x); if(x<5) //base case run(x+1); } public static void main(String args[] ) { RecursionTwo test = new RecursionTwo(); test.run(1); } } The Output: 1 2 3 4 5 A slightly different example from the previous one: public class RecursionThree { public void run(int x ) { if(x<5) //base case run(x+1); out.println(x); } public static void main(String args[] ) { RecursionThree test = new RecursionThree (); test.run(1); } } The Output: 5 4 3 2 1 Can also use a do while loop... Example below: class DoWhile { public void run( ) { int x=0; do{ x++; out.println(x); }while(x<10); //condition } public static void main(String args[] ) { DoWhile test = new DoWhile(); test.run( ); } } Example of tracing recursion: int fun(int x, int y) { if ( x == 0 ) return x; else return x+fun(y-1,x); } The call (4, 4) will return 16! Recursive Searching and Sorting: If an array or ArrayList is sorted, it can be searched using the binary search algorithm, which is more efficient than a linear search and works by keeping track of the beginning and ending positions of the section of the list that remains to be searched. By taking the average of these two positions, and then examining the item at the position calculated, half of the list can be eliminated in the next iteration. This continues until the item has been found, or until there is no part of the list remaining, in which case the conclusion is that the item does not exist in the list. “Binary Search: Step 1: Create three variables, low (the smallest index of the list left to search), high (the largest index of the list left to search), and middle (the middle index of the list with the decimal dropped if necessary) Step 2: Do the following until low is greater than high: If the middle item is the number, report middle. If the number is less than the middle, the value should be in the lower half of the remaining list so set high to middle minus one. Otherwise, the value should be in the upper half of the remaining list so set low to middle plus one. Then reset the middle to (low plus high) divided by two, the middle of the remaining half of the list. Step 3: If low becomes greater than high, then the number is not in the list, so report zero. Binary search is a logarithmic-time algorithm because every time the length of the list doubles, it adds one to the number of values that need to be checked in binary search. Binary Search only works for sorted lists. Binary Search in Java using Recursion: //Driver Method for binary search recursive function public static int binarySearchRecursive(int [] nums, int key) { return binarySearchRecursive(nums, key, 0, nums.length - 1); } public static int binarySearchRecursive(int [] nums, int key, int low, int high) { if(low > high) return -1; else { int mid = (high + low)/2; if(nums[mid] == key) return mid; else if(key < nums[mid]) //need to check the lower half return binarySearchRecursive(nums, key, low, mid - 1); else //need to check upper half return binarySearchRecursive(nums, key, mid + 1, high); } } Sort Algorithms Selection Sort: Step 1: Starting with the first thing in the list, find the minimum value in the list. Step 2: Swap the first value and the minimum value in the list Step 3: Move to the second item in the list and find the minimum value in the remaining unsorted list, then swap it with the second value. Step 4: Continue this process until there are no more values in the list to sort. Insertion Sort: Step 1: Start with the second item in the list and compare it to the first. If the item is smaller, swap them. Step 2: Move to the next item in the list. Compare it to the previous item. If the current one is smaller, swap them. Step 3: Continue swapping until the current item is greater than the previous or there are no more items in the list. Step 4: Move to the next item and continue the previous process. Step 5: Do this until all items in the list have been sorted.”[Wood] Sample Question: public static int mystery(int n) { if (n <= 1) { return n; } else { return mystery(n/2) + mystery(n/3); } } Question: What value is returned as a result of the call mystery(10);? A. 8 B. 13 C. 7 D. 4 E. 5 The correct answer is D. The call mystery(10) returns the expression mystery(5)+mystery(3), which in turn returns the expression (mystery(2)+mystery(1))+mystery(3), which is expanded to ((mystery(1)+mystery(0))+mystery(1))+(mystery(1)+mystery(1)), which evaluates to, via the base case of the recursion, 1+0+1+1+1 = 4.