The C++Course provides a general introduction to programming in C++. 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: Recursion  
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:
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. printBackward (Node *list) {if (list == null) return; Node *head = list; Node *tail = list>next; printBackward (tail); cout << head>cargo; } 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 