CMIS 240 Week 10 We need to have a crash course in recursion this week. Chapter 7 is devoted to recursion. A function that calls itself is recursive. There's nothing magical about recursion, although it sometimes seems that there is. It's another way of repetition (the repetition that you're familiar with is looping, i.e. iteration). Some problems lend themselves to recursive solutions that are easier to do than a corresponding iterative solution. Every iterative algorithm can be recast as a recursive one, and vice versa. Recursion is generally less efficient than looping because of all the (recursive) function calls, each of which takes some system overhead that is absent in a loop, but a good compiler will automatically turn certain kinds of recursive functions into iterative ones. The factorial function: N! = N*(N-1)! is "naturally" recursive (by it's very definition: it's defined in (smaller) terms of itself). A C function follows directly from the definition: int fac (int N) { if (N==0) //0!=1, by definition return 1; else return N * fac(N-1); //N!=N*(N-1)! } Table 7.1 shows that there are 5 calls of the function when the original argument is 4: when it's 4, then when it's 3, then when 2, then when 1, then 0. For the fac function, the argument 0 is the "base case" which does not have a recursive call, "bottoming out" the "recursing down". A recursive function must have one (or more) base cases. For the fac function, each recursive call has a smaller value than the "problem" the current call is working on. A recursive function's recursive call (or calls) must be on smaller versions of the data, thus leading inexorably to the base case. When a base case is reached the recursive calls "come back up", returning to where they were called from. Verifying existence of base case(s) and recursion on smaller version(s) is mechanical. It's the general case situation of verifying that the whole thing works correctly that is difficult and non-mechanical and that takes human ingenuity. I've put a program that lists the N! permutations of N items in the class web site in Chapter7/. It's a bit complicated though... Chapter7/ of the class web site has a fibo.cpp program that computes the Fibonacci numbers. This is a recursive function that has two recursive calls. Download and experiment with it. It helps to learn recursion by applying it to problems for which you know an iterative solution. Searching an array for a particular value can be done recursively. View the array as a recursive data structure (i.e. defined in terms of smaller versions of itself): an array is an element followed by a (sub)array. Page 400 has the recursive search function. Note that it has two base cases: one when the search is successful, and the other when the search is unsuccessful (i.e. when the end of the array is reached). Note that the smaller version requirement is met: the recursive call is on the remaining array, i.e. the subarray following the current element. Determining the number of combinations of N items taken R at a time is another naturally recursive definition. Writing a C function for such naturally recursive definitions is straightforward. You might have seen another formula to calculate the number of combinations: C(N,R)=N!/(R!(N-R)!). This formula wouldn't use the recursive definition of combinations, although it could use the one for factorial. Listing the combinations is more interesting. See the combos.cpp program in class web site Chapter7/; it lists the combinations of N things taken R at a time. Accessing the nodes of a singly linked list in reverse order (RevPrint p. 406) can be done recursively: access the nodes in the remainder of the list, then access the current node. Notice in the C function that the base case is when listPtr is NULL, the function does nothing but exit (i.e. the recursion stops). The binary search that we learned in chapter 3 is actually a recursive algorithm that we implemented iteratively. Now (p. 408) we see the truer nature of it. As a search, it's got two base cases: one for success and one for failure when all items (that could possibly be the sought-for item) have been looked at. The book's function returns the Boolean result of the search, but the function could be modified to return the index of the found item, or -1 (i.e. an impossible index) to indicate unsuccessful search. Notice that the function returns the value of the recursive function calls (a common error is to leave out the "return" of the recursive calls.) Inserting and deleting into a linked list can also be done recursively. The code is simpler than the looping ways we've seen, but more difficult to understand and subtler. I recommend exercises 7-17 as a way to work with recursion. It takes practice to get the hang of it. You should definitely code the Fibonacci function, Newton's method for square rooting (14.) and Ulam's function as practice. The section on How Recursion Works can be lightly skimmed. It's not critical to know how recursion is implemented by the compiler in order to use recursion, although it might help. Have a vague notion of the existence of the runtime stack that stacks the activation records, one for each call of a function, containing the arguments and local variables of that call, thus allowing recursion. An incorrect recursive function can lead to infinite recursion, where the recursing never ends. It's similar to infinite looping. Infinite recursion will eventually use up all the memory available for the runtime stack and then the program will be terminated. Here's a bad function. It doesn't have a base case. Have fun with it. It will be terminated by the OS (or maybe it will terminate a lousy OS). void inf_recurse (int x) { cout << "hello: " << x << endl; inf_recurse(x-1); } Comment out the cout and add a counter that increments each call. For each 100000 calls output a message so you can estimate how many calls occur before the program is terminated. Use the badrecursion.cpp program on the class web site. Here's another bad function. It doesn't recurse on a smaller version. void inf_recurse2 (int x) { if (x > 0) { cout << "hello: " << x << endl; inf_recurse2(x); } } A recursive function will be less efficient than the corresponding iterative one. For a large-sized problem it might be necessary to use the iterative version. A tail recursive function, in which the single recursive call is the last statement executed in the function, can be easily converted into an iterative function. So easily that the compiler can do so automatically (and good compilers do). (Binary search, factorial, and sequential search are tail recursive functions.) Recursive functions whose recursive call is not the last statement executed in the function, or that have more than one recursive call, can be converted into iterative functions that use a stack. (RevPrint, fibonacci, and quicksort are not tail recursive.) In these cases the implicit use of the runtime stack is changed to the explicit use of the programmer's own stack. The resulting iterative function is invariably more complicated than the recursive version. The book provides good guidelines on pages 426-428 for when to use recursion in practical programs. The Case Study about Quicksort will be included as part of chapter 10. You don't need to study it now. ---------------------------------------------------------------- Homework Due: 24 Nov Write a program for a modified exercise 16 on page 442. The user enters the number of rows and the number of columns. The grid is rectangular, not necessarily square. The program reports how many ways there are to go from the start at the lowerleft corner to every other position (including the finish at the upperright corner) moving either up or rightwards. Moving down or left or diagonally isn't allowed. Use a 2D array of integers that records this information; display it as a 2D grid when the information has been calculated. We want to find all paths in this "maze" of no walls. The book has a partial solution that deliberately does not work, but you'll still have to think about how to do the problem; randomly changing the code probably won't yield the correct version. You must use the recursive method. Hint: There are 48620 ways to get to 10,10. There's about four billion ways to get to 20,17. You might notice the similarity to combinations. ---------------------------------------------------------------- The proctored exam is week 12: 24 Nov - 26 Nov. You must schedule a time at your UMUC site to take the exam. It's format is "short answer", meaning coding mostly. There will be some tracing of code, in particular recursive functions. You need to know the big-O functions for the algorithms and data structures we've covered. You'll need to be able to write linked list code, member functions including copy ctor, and recursive functions. You'll need to know binary search.