Description

3 Recursion 5 Linked Structures Based on Levent Akın s CmpE160 Lecture Slides What Is Recursion? Recursive call A method call in which the method being called is the same as the one making the call Direct

Information

Category:
## Slides

Publish on:

Views: 315 | Pages: 8

Extension: PDF | Download: 0

Share

Transcript

3 Recursion 5 Linked Structures Based on Levent Akın s CmpE160 Lecture Slides What Is Recursion? Recursive call A method call in which the method being called is the same as the one making the call Direct recursion Recursion in which a method directly calls itself Indirect recursion Recursion in which a chain of two or more method calls returns to the method that originated the chain 1 Recursion Some Definitions You must be careful when using recursion. Recursive solutions can be less efficient than iterative solutions. Still, many problems lend themselves to simple, elegant, recursive solutions. Base case The case for which the solution can be stated nonrecursively General (recursive) case The case for which the solution is expressed in terms of a smaller version of itself Recursive algorithm A solution that is expressed in terms of (a) smaller instances of itself and (b) a base case Recursive Function Call Finding a Recursive Solution A recursive call is a function call in which the called function is the same as the one making the call. In other words, recursion occurs when a function calls itself! We must avoid making an infinite sequence of function calls (infinite recursion). Each successive recursive call should bring you closer to a situation in which the answer is known. A case for which the answer is known (and can be expressed without recursion) is called a base case. Each recursive algorithm must have at least one base case, as well as the general (recursive) case General format for many recursive functions Writing a recursive function to find n factorial if (some condition for which answer is known) // base case solution statement else // general case recursive function call SOME EXAMPLES... DISCUSSION The function call Factorial(4) should have value 24, because that is 4 * 3 * 2 * 1. For a situation in which the answer is known, the value of 0! is 1. So our base case could be along the lines of if ( number == 0 ) return 1; Writing a recursive function to find Factorial(n) Recursive Solution Now for the general case... The value of Factorial(n) can be written as n * the product of the numbers from (n - 1) to 1, that is, n * (n - 1) *... * 1 or, n * Factorial(n - 1) And notice that the recursive call Factorial(n - 1) gets us closer to the base case of Factorial(0). int Factorial ( int number ) // Pre: number is assigned and number = 0. if ( number == 0) // base case return 1 ; else // general case return number + Factorial ( number - 1 ) ; Three-Question Method of verifying recursive functions Base-Case Question: Is there a nonrecursive way out of the function? Smaller-Caller Question: Does each recursive function call involve a smaller case of the original problem leading to the base case? General-Case Question: Assuming each recursive call works correctly, does the whole function work correctly? Another example where recursion comes naturally From mathematics, we know that 2 0 = 1 and 2 5 = 2 * 2 4 In general, x 0 = 1 and x n = x * x n-1 for integer x, and integer n 0. Here we are defining x n recursively, in terms of x n-1 struct ListType // Recursive definition of power function int Power ( int x, int n ) // Pre: n = 0. x, n are not both zero // Post: Function value = x raised to the power n. if ( n == 0 ) return 1; // base case else // general case return ( x * Power ( x, n-1 ) ) ; struct ListType int length ; // number of elements in the list int info[ MAX_ITEMS ] ; ; ListType list ; Of course, an alternative would have been to use looping instead of a recursive call in the function body. 13 Recursive function to determine if value is in list PROTOTYPE bool ValueInList( ListType list, int value, int startindex ) ; list[0] [1] [startindex] Already searched index of current element to examine [length -1] Needs to be searched bool ValueInList ( ListType list, int value, int startindex ) // Searches list for value between positions startindex // and list.length-1 // Pre: list.info[ startindex ].. list.info[ list.length - 1 ] // contain values to be searched // Post: Function value = // ( value exists in list.info[ startindex ].. // list.info[ list.length - 1 ] ) if ( list.info[startindex] == value ) // one base case return true ; else if (startindex == list.length -1 ) // another base case return false ; else // general case return ValueInList( list, value, startindex + 1 ) ; 16 Why use recursion? struct ListType Those examples could have been written without recursion, using iteration instead. The iterative solution uses a loop, and the recursive solution uses an if statement. However, for certain problems the recursive solution is the most natural solution. This often occurs when pointer variables are used. struct NodeType int info ; NodeType* next ; class SortedType public : private : ;... // member function prototypes NodeType* listdata ; RevPrint(listData); Base Case and General Case listdata A B C D THEN, print this element FIRST, print out this section of list, backwards E A base case may be a solution in terms of a smaller list. Certainly for a list with 0 elements, there is no more processing to do. Our general case needs to bring us closer to the base case situation. That is, the number of list elements to be processed decreases by 1 with each recursive call. By printing one element in the general case, and also processing the smaller remaining list, we will eventually reach the situation where 0 list elements are left to be processed. In the general case, we will print the elements of the smaller remaining list in reverse order, and then print the current pointed to element. Using recursion with a linked list Function BinarySearch( ) void RevPrint ( NodeType* listptr ) // Pre: listptr points to an element of a list. // Post: all elements of list pointed to by listptr // have been printed out in reverse order. if ( listptr!= NULL ) // general case RevPrint ( listptr- next ) ; //process the rest std::cout listptr- info std::endl ; // print this element // Base case : if the list is empty, do nothing 21 BinarySearch takes sorted array info, and two subscripts, fromloc and toloc, and item as arguments. It returns false if item is not found in the elements info[fromloc toloc]. Otherwise, it returns true. BinarySearch can be written using iteration, or using recursion. indexes found = BinarySearch(info, 25, 0, 14 ); item fromloc toloc template class ItemType bool BinarySearch ( ItemType info[ ], ItemType item, int fromloc, int toloc ) // Pre: info [ fromloc.. toloc ] sorted in ascending order // Post: Function value = ( item in info [ fromloc.. toloc] ) info NOTE: denotes element examined int mid ; if ( fromloc toloc ) // base case -- not found return false ; else mid = ( fromloc + toloc ) / 2 ; if ( info [ mid ] == item ) //base case-- found at mi return true ; else if ( item info [ mid ] ) // search lower half return BinarySearch ( info, item, fromloc, mid-1 ) ; else // search upper half return BinarySearch( info, item, mid + 1, toloc ) ; 24 When a function is called... Tail Recursion A transfer of control occurs from the calling block to the code of the function. It is necessary that there be a return to the correct place in the calling block after the function code is executed. This correct place is called the return address. When any function is called, the run-time stack is used. On this stack is placed an activation record (stack frame) for the function call. The case in which a function contains only a single recursive call and it is the last statement to be executed in the function. Tail recursion can be replaced by iteration to remove recursion from the solution as in the next example. // USES TAIL RECURSION bool ValueInList ( ListType list, int value, int startindex ) // Searches list for value between positions startindex // and list.length-1 // Pre: list.info[ startindex ].. list.info[ list.length - 1 ] // contain values to be searched // Post: Function value = // ( value exists in list.info[ startindex ].. // list.info[ list.length - 1 ] ) if ( list.info[startindex] == value ) // one base case return true ; else if (startindex == list.length -1 ) // another base case return false ; else // general case return ValueInList( list, value, startindex + 1 ) ; 36 // ITERATIVE SOLUTION bool ValueInList ( ListType list, int value, int startindex ) // Searches list for value between positions startindex // and list.length-1 // Pre: list.info[ startindex ].. list.info[ list.length - 1 ] // contain values to be searched // Post: Function value = // ( value exists in list.info[ startindex ].. // list.info[ list.length - 1 ] ) bool found = false ; while (!found && startindex list.length ) if ( value == list.info[ startindex ] ) found = true ; else startindex++ ; return found ; 37 Use a recursive solution when: The depth of recursive calls is relatively shallow compared to the size of the problem. The recursive version does about the same amount of work as the nonrecursive version. The recursive version is shorter and simpler than the nonrecursive solution. SHALLOW DEPTH EFFICIENCY CLARITY

Related Search

Similar documents

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks