CMIS 241 Recursion We'll do recursion this week. Chapter 4 is devoted to recursion. A method or 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) method 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 methods into iterative ones. Actually, I don't think recursion is all that important to learn. It's more of a computer-sciency theoretical idea. Skip the Towers of Hanoi example. The factorial function: N! = N*(N-1)! is "naturally" recursive (by it's very definition: it's defined in (smaller) terms of itself). A Java method 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)! } Page 242 shows that there are 10 calls of the method when the original argument is 9: when it's 9, then when it's 8, then when 7, and so on "down" to when 1, then 0. For the fac method, the argument 0 is the "base case" which does not have a recursive call, "bottoming out" the "recursing down". A recursive method must have one (or more) base cases. For the fac method, each recursive call has a smaller value than the "problem" the current call is working on. A recursive method'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. It helps to learn recursion by applying it to problems for which you know an iterative solution. Searching a list for a particular value can be done recursively. View the list as a recursive data structure (i.e. defined in terms of smaller versions of itself): a list is an element followed by a (sub)list. Page 485 ff. has the recursive search method. 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 list is reached). Note that the smaller version requirement is met: the recursive call is on the remaining list, i.e. the sublist following the current element. Determining the number of combinations of N items taken R at a time is another naturally recursive definition. Writing a Java method 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. Accessing the nodes of a singly linked list in reverse order (RevPrint p. 264 ff.) can be done recursively: access the nodes in the remainder of the list, then access the current node. Notice in the Java method that the base case is when listRef is NULL, the method does nothing but exit (i.e. the recursion stops). The binary search is actually a recursive algorithm that was implemented iteratively. It's on page 412. 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 method and associated code is overly complex (gee, what a surprise). returns the boolean result of the search, but the method 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 method returns the value of the recursive function calls (a common error is to leave out the "return" of the recursive calls.) I recommend the exercises 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 (21.) 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 method, containing the arguments and local variables of that call, thus allowing recursion. An incorrect recursive method 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 method. It doesn't have a base case. Have fun with it. It will eventually throw a StackOverflowError exception when the runtime stack becomes full. void inf_recurse (int x) { System.out.println("hello: " + x); inf_recurse(x-1); } Here's another bad method. It doesn't recurse on a smaller version. void inf_recurse2 (int x) { if (x > 0) { System.out.println("hello: " + x); inf_recurse2(x); } } Comment out the output and add a counter that increments each call. For each 1000 calls output a message so you can estimate how many calls occur before the program is terminated. Use the BadRecursions.java program on the class web site. A recursive method 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 method, in which the single recursive call is the last statement executed in the method, can be easily converted into an iterative method. 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 method, or that have more than one recursive call, can be converted into iterative methods 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 method is invariably more complicated than the recursive version. The book provides good guidelines of section 4.7 for when to use recursion in practical programs. Actually, it doesn't come up often.