LinkedLIst indexOf recursive implementation

Question

I'm having a hard time understanding how the recursion in following implementation of indexOf() of LinkedList works:

/**
 * Returns the position of the first occurrence of the 
 * given character in this list, or -1 if there is no 
 * such occurrence.
 */
public int indexOf(char c)
{
    if (this.head == null)
    {
        return -1;
    }
    else
    {
        return LinkedList.indexOf(c, this.head);
    }
}
private static int indexOf(char c, Node node)
{
    if (node.data == c)
    {
        return 0;
    }
    if (node.next == null)
    {
        return -1;
    }
    int index = LinkedList.indexOf(c, node.next);
    if (index == -1)
    {
        return -1;
    }
    else
    {
        return 1 + index;
    }
}

where head is the initial node ("link") in the list.

The static indexOf() method checks whether there's a data match in the head, and then whether there exists a next node. Assume both conditions are false (there's no data match and there exists a next node). Then indexOf() is called recursively on the next (second) node to perform the same checks. However, if both conditions are still false, what does it return to int index given that there's no else clause before index is declared? That doesn't seem legal.

When I stepped through it in the debugger, rather than returning anything it actually seems to do more recursive calls until one of the if conditions is met (either there's a data match or the end of the list is reached). But why would it do that? And then how is 1 being added to the index each time?

Hint: it might be a bit of work, but consider not using the debugger, but a piece of paper and a pen (on a "small scale" example). The best way to understand recursion is sometimes ... to do it manually for 5, 10 minutes. Just be sure that your starting data is well defined and meaningful. — GhostCat
– GhostCat, Commented Jul 10, 2016 at 14:51
@Jägermeister I agree that is very useful -- thank you -- though one must also understand some basic principles about how programs flow in order for that technique to work. — yroc
– yroc, Commented Jul 10, 2016 at 17:10

Loris Securo · Accepted Answer · 2016-07-10 17:59:27Z

3

However, if both conditions are still false, what does it return to int index given that there's no else clause before index is declared?

It will return nothing yet, it will enter another level of recursion:

indexOf(node) -> indexOf(node.next) -> indexOf(node.next.next) -> ...

Then when the conditions are met it finally returns a value and you start to come back from each recursion call you made before:

indexOf(node) <- indexOf(node.next) <- indexOf(node.next.next) <- ...

but doing so it will also add 1 to the index it is returning, therefore basically counting the recursion levels you reached which equal to the node number you reached which is the index you are looking for.

This diagram shows how the algorithm works when there is a match on the fourth node. The blue color indicates that we are entering recursion, the red color indicates that we are coming back from recursion (click the image to open it in its original size):

This other diagram shows the order of execution of the instructions in case of a match on the third node (click the image to open it in its original size):

edited Jul 10, 2016 at 17:59

answered Jul 10, 2016 at 15:00

Loris Securo

7,6282 gold badges19 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

yroc Over a year ago

I think I get it now. I was expecting there to be an error because neither of the if conditions (before index was declared) was met, but it seems that as long as there's an else clause at the end, it will keep entering another level of recursion until one of the if conditions are met.

Loris Securo Over a year ago

I'm not sure what you mean about the else, the reason it enters another level of recursion is because of int index = LinkedList.indexOf(c, node.next);. Only when a return is reached you actually start getting the values for index and start doing return 1 + index;

yroc Over a year ago

What I was thinking was that normally if you were to define a method with return type int that only had two if clauses, you would get a compiler error, so why is it that in this case there's no compiler error when there's nothing to return to index? What rule determines that the compiler decides to enter another level of recursion instead?

Loris Securo Over a year ago

The compiler sees that after int index = LinkedList.indexOf(c, node.next); it will return something, so it is valid. The method does not end after the first 2 if, after that it does a recursive call, and then it actually return the result with the last 2 if.

yroc Over a year ago

I'm still not sure I understand from your answer how the index value is properly set. Suppose the list holds 'H' 'E' 'L' 'L' 'O', and the passed argument is 'L'. Then on second recursion call, there is a data match, and 0 is returned. But on the first recursion call, nothing is returned. Can you explain in a little more detail (either as a comment or editing your answer) how the index variable accumulates 1 for each recursion call?

|

Collectives™ on Stack Overflow

LinkedLIst indexOf recursive implementation

1 Answer 1

9 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

9 Comments

Your Answer

Sign up or log in

Post as a guest

Related