How does this recursive function with no parameters work?

October 31, 2022

This function calculates the length of a singly linked list recursively.

tail is an instance variable that points to the next object in the list.

    public int length() {
        if (tail == null) {
            return 1;
        }

        return 1 + tail.length();
    }

However it uses no parameters as shown. I’m struggling to understand the logic behind this code, could I get some help with understanding what’s actually going on here?

My first point of confusion is when the function reaches the last object in the list, that objects tail will be null, so why does the function not just end up returning 1?
And secondly, what does 1 + tail.length() actually do.

The most I understand is that 1 and tail.length() can be added due to the length function having a return type of int.

>Solution :

Let’s assume you have a list like [a, b, c, d] and you’re calling length() on it. this will be the element a and tail will be the next element b. So the flow of the code should be something like this:

this.length() // Element 'a'
Is tail == null? // No, tail is 'b'
return 1 + <result of length() of 'b'>
|
|   this.length() // Element 'b'
|   Is tail == null? // No, tail is 'c'
|   return 1 + <result of length() of 'c'>
|   |
|   |   this.length() // Element 'c'
|   |   Is tail == null? // No, tail is 'd'
|   |   return 1 + <result of length() of 'd'>
|   |   |
|   |   |   this.length() // Element 'd'
|   |   |   Is tail == null? // Yes, there's no element after 'd' so return 1
|   |   |   return 1 // return 1 from length() of 'd'
|   |   |
|   |   return 1 + 1 // return 2 from length() of 'c'
|   |
|   return 1 + 2 // return 3 from length() of 'b'
|
return 1 + 3 // return 4 from length() of 'a'

So in the end, length() will give you the correct result of 4