Recursion on Lists

Generally, one can use either iteration (loops) or recursion to process lists such as linked lists. Usually, iteration is preferred because is it faster (not requiring so many recursive calls) and simpler. But in the example presented here, a recursive function is easier to develop.

Reversing a singly linked list

Paul Gries develops a recursive function to reverse a linked list (just over 4 minutes). Important here is not just the little poem that emerges but the careful use of assertions within the function body to keep track of what has been done and what remains to be done. Read it here: ReverseLinkedList.pdf.