yroc yroc - 4 months ago 45
Java Question

LinkedLIst indexOf recursive implementation

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?

Answer

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 forth node:

Recursion

The blue color indicates that we are entering recursion, the red color indicates that we are coming back from recursion.

Comments