Traverse Through a Linked List Using Recursion - Java

Welcome, and thank you for choosing this instruction set, which will show you how to create a recursive function. Basic java knowledge is needed to understand the steps that will be run through.

Overall, this 12-step process should take no longer than 15 minutes. The only step that may take longer than one minute is step 4, which asks the user to create a sample test to run through. The amount of time to be used is up to the user, but I would estimate that it would take no more than 3 minutes.

What you will need on your computer: My testing file (that we will add code to). Any java IDE of your choice (we will be using drjava for this).

Step One: Open Up Your Java IDE of Choice.

For this instruction set, drjava is used.
Just have a new fresh file open.

Step Two: Download and Open My .txt File

This text contains the “Node” class we will be working with, as well as some tests to make sure the code we write works as intended. Download Here

Step Three: Copy and Paste From .txt File Into IDE

Copy the text from my file and paste it into the java IDE you have opened.

Step Four: Create a Test.

This will check to see if our recursive function works correctly. Follow the format of the example tests given.

Step Five: Create Recursive Function.

Where prompted to, type in the following:

public int size (){
}

Step Six: Create Recursive Helper Function

Where prompted to, type in the following:

public static int sizeH(Node x){
}

Step Seven: Call Helper Function in Main Recursive Function

This will get our function to traverse through the linked list from the beginning.

In the first of the functions we wrote, type in the following:

return sizeH(first);

Step Eight: Create Base Case for Helper Function

Every recursive function must have a way to end it. The "base case" will give have us stop traversing once we reach the end of the list.

In the "helper" function, type in the following:

if (x == null) return 0;

Step Nine: Add “+1” and Call the Helper Function Again.

We add one for every node that the recursive function visits.

In the "helper" function, type in the following:

return 1 + sizeH(x.next);

Step Ten: Compile / Save Your Code

The code needs to be compiled before we can run the program.

Step Eleven: Run the Program

Run your program! What was output? If something went wrong, look back and see if you entered the code exactly, and in the right spot.

Step Twelve: Congratulations!

If this is your final output, you have officially written a recursive function that iterates through a linked list.