A Simple Explanation of Recursion

Solution Preview

Hello,

Writing a recursive method to find an item in a linked list is actually very simple. Understanding how it works is the tricky part. Here's how it looks:

search(Integer itemToFind, linkedList frontOfLinkedList) {

if (frontOfLinkedList == null)
return null;

if (frontOfLinkedList.data == itemToFind)
return frontOfLinkedList;
else
return search(itemToFind, frontOfLinkedList.nextNode())

}

My assumptions in the above pseudo-code are: That the itemToFind is an integer; That the data type of frontOfLinkedList is a pointer of some kind to the front of a linked list (like the one in the example you provided with your post); That there is a method of some kind to obtain the data in a given node (like the "getData()" method in your example); And that there is a way to obtain the next node in the linked list (like the "getNext()" method in your example).

The first thing the "search" function does is to check if the item being searched for happens to be at the front of the list. If it is, it simply returns the front of the list, which is what is required by your assignment (to return a pointer to the node containing the data being searched for). If it is not, the recursion begins. The function simply calls itself, this time sending it the next item in the linked list.

At that point in the program's execution, the same function is called again, "search". Control begins as it normally does when a function is called, at the first line of code. The only thing different this time is that instead of actually having the first node in the linked list, it now has the second node in the linked list. You can see that in the recursive call, where the second parameter being sent is "frontOfLinkedList.nextNode()".

Don't be fooled by the name of the second parameter of the search function. It's called "frontOfLinkedList" because the intent is that you send it a list that you want searched. The second time it is called (the first recursive time), it has the second node in the linked list as the value for "frontOfLinkedList".

And that's what it then checks: Whether or not the value of that node matches the value that is being searched for. If it does, it returns that pointer to the first "image" of the function, which in turn returns that to the ...