CODEWITHSUNDEEP
javarecursion
Dan_ENZ
Dan_ENZ

Reputation: 49

Return the number of elements in a linked list recursively

I have the following recursive method in a class called ImageNode which is passed the head(this - the start of the linked list) from a class called Image. I thought my code would recursively go through each node, increase the count then when its at the end return the count, unfortunatly not. Where am I going wrong?

private int countRec() {
    int count = 1;
    ImageNode node = this;

    if (node.next != null ){
        node = node.next;
        count++;
        countRec();
    }

    return count;
}

Upvotes: 1

Views: 6556

Answers (3)

Fernando Aires
Fernando Aires

Reputation: 531

A recursive function is useful when it uses the result of the further calls to solve his problem (like an inductive step on mathematics). Your function are not using the return for the countRec() call for anything, and you're still trying to solve the issue without the recursion help. You can solve it by using it, as:

if(node.next != null)
{
    node = node.next;
    count = countRec()+1;
}
return count;

Of course, since we're telling about getting your code better, you wouldn't even need to use this node var, just doing:

private int countRec() {

    if (this.next != null )
        return (this.next.countRec())+1;
    return 1;
}

Hope that helps.

Upvotes: 0

Francis Harbison
Francis Harbison

Reputation: 211

The definition of a recursive function is it is defined in terms of itself: i.e. the count of elements in a list is equal to 0 if an empty list; otherwise it is equal to 1 + the count of the rest of the elements of the list.

The italicized portion of the above definition is where the function call gets made.

private int countRec(ImageNode node) {
    if (node == null) {
        return 0;
    } else {
        return 1 + countRec(node);
    }
}

Upvotes: 0

Jon Skeet
Jon Skeet

Reputation: 1500805

You're ignoring the result of countRec() - and you're iterating within the recursive call, defeating the purpose. (You're also making a recursive call on the same object, with no parameters and no change in state... so that can't do any good.) My recursive approach would be based on a design of:

  • If the next node is null, then the size of the list is 1
  • Otherwise, the size is 1 + the size from the next node onwards.

So:

private int countRec() {
    return next == null ? 1 : 1 + next.countRec();
}

Now that doesn't allow for a list of length 0 of course... you probably want to separate the idea of the list from the node, in which case the list class would have something like:

public int count() {
    return head == null ? 0 : head.countRec();
}

where the value of head is a reference to the head node if there is one, or null otherwise.

Of course, this will be O(n) in time and space. You can get O(1) space using iteration instead of recursion, and O(1) time by just keeping the size of the list as an instance variable in the list, updating it when you need to. I'm hoping that this question was based on an educational requirement rather than real code though - in production code, you'd just use the collections provided already.

Upvotes: 11

Related Questions