Help me check homework for write a recursive method that counts the number of nodes in a chain of linked nodes.

Question

I try many coding to solve the question bellow but also cannot find the answer. Can anyone help me solve my problem and tell me where is the wrong coding??

/** Task: Recusively counts the nodes in a chain.
* @param start the first node
* @returns the number of nodes in the linked chain */
public int countNodes(Node start)
{
if (start == null) 

// base case

{
  countNodes (Node start);

// recursive case
else

System.out.println (start.data);
return start.next;
}
} // end countNodes

Answer 1

Perhaps it helps to think of it like this: the number of nodes is 1 for the current node plus the result of counting the rest of the nodes.

Answer 2

In recursion you shouldn't use the same argument for the next equation, basically, you should do some simple calculation, in your case add one, and call your function again with the "next" value of the argument. Obviously, to be able to solve this problem using recursion, there should be possibility to move from the current node to the next one.

Answer 3

Lets create a Recursive function called countNodes(Node node)

1. If node is null, that means there are no more Nodes so count = 0
2. Else There are 1 + countNodes(node.next)

Say you have a list A->B->C->D->NULL

countNodes(NodeA) = 1 + countNodes(NodeB)
countNodes(NodeA) = 1 + (1 + countNodes(NodeC))
countNodes(NodeA) = 1 + (1 + (1 + countNodes(NodeD)))
countNodes(NodeA) = 1 + (1 + (1 + (1 + 0))))

So, 4 is our answer.