My book is asking me to make a recursive definition of a singly linked list. I have no idea at all how to do that. Can someone please help me out with a sample? Thanks
It's just like a normal linked list except the iteration is performed by recursion rather than loops.
First, a little light reading: What is recursion and when should I use it?
For example, a loop-based function to find the last node could be:
Node * getLast(Node * current)
{
while (current->next)
{ // loop until no more nodes
current = current.next;
}
return current; // return last node
}
While the recursive version only checks if the current node is the last and calls itself with the next node if there is a next node.
Node * getLast(Node * current)
{
if (current->next)
{ // see if next node is last node
return getLast(current->next);
}
else
{ // found last node. return it
return current;
}
}
Note that both approaches require that the list at current
not be empty.