The Java Course provides a general introduction to programming in Java. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details. 
Home Linked Lists Lists and Recursion  
See also: More Recursion  
Search the VIAS Library  Index  
Lists and Recursion
Recursion and lists go together like fava beans and a nice Chianti. For example, here is a recursive algorithm for printing a list backwards:
Of course, Step 2, the recursive call, assumes that we have a way of printing a list backwards. But if we assume that the recursive call worksthe leap of faiththen we can convince ourselves that this algorithm works. All we need is a base case, and a way of proving that for any list we will eventually get to the base case. A natural choice for the base case is a list with a single element, but an even better choice is the empty list, represented by null. public static void printBackward (Node list) {if (list == null) return; Node head = list; Node tail = list.next; printBackward (tail); System.out.print (head); } The first line handles the base case by doing nothing. The next two lines split the list into head and tail. The last two lines print the list. We invoke this method exactly as we invoked printList: printBackward (node1);The result is a backwards list. Can we prove that this method will always terminate? In other words, will it always reach the base case? In fact, the answer is no. There are some lists that will make this method crash.


Home Linked Lists Lists and Recursion 