Home > Net >  How does this recursive function with no parameters work?
How does this recursive function with no parameters work?

Time:11-01

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.

CodePudding user response:

Let's assume you have a list like [a, b, c, d] and you're calling length() on it. this will initially be the first 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

CodePudding user response:

There is always 1 parameter to a member function ... the object you called the function on (represented by this in the function.

When you call

return 1   tail.length();

The function length will have a this that refers to the tail here. The tail in that function is tail.tail

CodePudding user response:

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?

It does -- when called on the last object in the list.

what does 1 tail.length() actually do.

It calls length on the tail object. When you say this has "no parameters," you're not quite right -- the parameter is which object it's being called on. So if you call node.length() where node.tail == tail1 and tail1.tail == null, then node.length() is 1 tail1.length() is 1 1 is 2, for a total length of 2 -- which is what we'd expect.

  • Related